Polynomial-time identification of multiple context-free languages from positive data and membership queries

Ryo Yoshinaka

doi:10.1007/978-3-642-15488-1_19

Polynomial-time identification of multiple context-free languages from positive data and membership queries

Ryo Yoshinaka

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Citations (Scopus)

Abstract

This paper presents an efficient algorithm that identifies a rich subclass of multiple context-free languages in the limit from positive data and membership queries by observing where each tuple of strings may occur in sentences of the language of the learning target. Our technique is based on Clark et al.'s work (ICGI 2008) on learning of a subclass of context-free languages. Our algorithm learns those context-free languages as well as many non-context-free languages.

Original language	English
Title of host publication	Grammatical Inference
Subtitle of host publication	Theoretical Results and Applications - 10th International Colloquium, ICGI 2010, Proceedings
Pages	230-244
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-15488-1_19
Publication status	Published - 2010 Nov 12
Externally published	Yes
Event	10th International Colloquium on Grammatical Inference, ICGI 2010 - Valencia, Spain Duration: 2010 Sept 13 → 2010 Sept 16

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	6339 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	10th International Colloquium on Grammatical Inference, ICGI 2010
Country/Territory	Spain
City	Valencia
Period	10/9/13 → 10/9/16

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-15488-1_19

Cite this

Yoshinaka, R. (2010). Polynomial-time identification of multiple context-free languages from positive data and membership queries. In Grammatical Inference: Theoretical Results and Applications - 10th International Colloquium, ICGI 2010, Proceedings (pp. 230-244). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6339 LNAI). https://doi.org/10.1007/978-3-642-15488-1_19

Polynomial-time identification of multiple context-free languages from positive data and membership queries. / Yoshinaka, Ryo.
Grammatical Inference: Theoretical Results and Applications - 10th International Colloquium, ICGI 2010, Proceedings. 2010. p. 230-244 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6339 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Yoshinaka, R 2010, Polynomial-time identification of multiple context-free languages from positive data and membership queries. in Grammatical Inference: Theoretical Results and Applications - 10th International Colloquium, ICGI 2010, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6339 LNAI, pp. 230-244, 10th International Colloquium on Grammatical Inference, ICGI 2010, Valencia, Spain, 10/9/13. https://doi.org/10.1007/978-3-642-15488-1_19

Yoshinaka R. Polynomial-time identification of multiple context-free languages from positive data and membership queries. In Grammatical Inference: Theoretical Results and Applications - 10th International Colloquium, ICGI 2010, Proceedings. 2010. p. 230-244. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-15488-1_19

Yoshinaka, Ryo. / Polynomial-time identification of multiple context-free languages from positive data and membership queries. Grammatical Inference: Theoretical Results and Applications - 10th International Colloquium, ICGI 2010, Proceedings. 2010. pp. 230-244 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{602189eaddcc47fe9b545f84d79d3509,

title = "Polynomial-time identification of multiple context-free languages from positive data and membership queries",

abstract = "This paper presents an efficient algorithm that identifies a rich subclass of multiple context-free languages in the limit from positive data and membership queries by observing where each tuple of strings may occur in sentences of the language of the learning target. Our technique is based on Clark et al.'s work (ICGI 2008) on learning of a subclass of context-free languages. Our algorithm learns those context-free languages as well as many non-context-free languages.",

author = "Ryo Yoshinaka",

year = "2010",

month = nov,

day = "12",

doi = "10.1007/978-3-642-15488-1_19",

language = "English",

isbn = "3642154875",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "230--244",

booktitle = "Grammatical Inference",

note = "10th International Colloquium on Grammatical Inference, ICGI 2010 ; Conference date: 13-09-2010 Through 16-09-2010",

}

TY - GEN

T1 - Polynomial-time identification of multiple context-free languages from positive data and membership queries

AU - Yoshinaka, Ryo

PY - 2010/11/12

Y1 - 2010/11/12

N2 - This paper presents an efficient algorithm that identifies a rich subclass of multiple context-free languages in the limit from positive data and membership queries by observing where each tuple of strings may occur in sentences of the language of the learning target. Our technique is based on Clark et al.'s work (ICGI 2008) on learning of a subclass of context-free languages. Our algorithm learns those context-free languages as well as many non-context-free languages.

AB - This paper presents an efficient algorithm that identifies a rich subclass of multiple context-free languages in the limit from positive data and membership queries by observing where each tuple of strings may occur in sentences of the language of the learning target. Our technique is based on Clark et al.'s work (ICGI 2008) on learning of a subclass of context-free languages. Our algorithm learns those context-free languages as well as many non-context-free languages.

UR - http://www.scopus.com/inward/record.url?scp=78149240932&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=78149240932&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-15488-1_19

DO - 10.1007/978-3-642-15488-1_19

M3 - Conference contribution

AN - SCOPUS:78149240932

SN - 3642154875

SN - 9783642154874

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 230

EP - 244

BT - Grammatical Inference

T2 - 10th International Colloquium on Grammatical Inference, ICGI 2010

Y2 - 13 September 2010 through 16 September 2010

ER -

Polynomial-time identification of multiple context-free languages from positive data and membership queries

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this