Identification in the limit of k,l-substitutable context-free languages

Ryo Yoshinaka

doi:10.1007/978-3-540-88009-7_21

Identification in the limit of k,l-substitutable context-free languages

Ryo Yoshinaka

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

27 Citations (Scopus)

Abstract

Recently Clark and Eyraud (2005, 2007) have shown that substitutable context-free languages are polynomial-time identifiable in the limit from positive data. Substitutability in context-free languages can be thought of as the analogue of reversibility in regular languages. While reversible languages admit a hierarchy, namely k-reversible regular languages for each nonnegative integer k, Clark and Eyraud targeted the subclass of context-free languages that corresponds to zero-reversible regular languages only. Following Clark and Eyraud's proposal, this paper introduces a hierarchy of substitutable context-free languages as the analogue of that of k-reversible regular languages and shows that each class in the hierarchy is also polynomial-time identifiable in the limit from positive data.

Original language	English
Title of host publication	Grammatical Inference
Subtitle of host publication	Algorithms and Applications - 9th International Colloquium, ICGI 2008, Proceedings
Pages	266-279
Number of pages	14
DOIs	https://doi.org/10.1007/978-3-540-88009-7_21
Publication status	Published - 2008 Nov 28
Externally published	Yes
Event	9th International Colloquium on Grammatical Inference, ICGI 2008 - Saint-Malo, France Duration: 2008 Sept 22 → 2008 Sept 24

Publication series

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

Other

Other	9th International Colloquium on Grammatical Inference, ICGI 2008
Country/Territory	France
City	Saint-Malo
Period	08/9/22 → 08/9/24

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-88009-7_21

Cite this

Yoshinaka, R. (2008). Identification in the limit of k,l-substitutable context-free languages. In Grammatical Inference: Algorithms and Applications - 9th International Colloquium, ICGI 2008, Proceedings (pp. 266-279). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5278 LNAI). https://doi.org/10.1007/978-3-540-88009-7_21

Identification in the limit of k,l-substitutable context-free languages. / Yoshinaka, Ryo.
Grammatical Inference: Algorithms and Applications - 9th International Colloquium, ICGI 2008, Proceedings. 2008. p. 266-279 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5278 LNAI).

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

Yoshinaka, R 2008, Identification in the limit of k,l-substitutable context-free languages. in Grammatical Inference: Algorithms and Applications - 9th International Colloquium, ICGI 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5278 LNAI, pp. 266-279, 9th International Colloquium on Grammatical Inference, ICGI 2008, Saint-Malo, France, 08/9/22. https://doi.org/10.1007/978-3-540-88009-7_21

Yoshinaka R. Identification in the limit of k,l-substitutable context-free languages. In Grammatical Inference: Algorithms and Applications - 9th International Colloquium, ICGI 2008, Proceedings. 2008. p. 266-279. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-88009-7_21

@inproceedings{21773fd7e19149aca4f861426a1f2ffc,

title = "Identification in the limit of k,l-substitutable context-free languages",

abstract = "Recently Clark and Eyraud (2005, 2007) have shown that substitutable context-free languages are polynomial-time identifiable in the limit from positive data. Substitutability in context-free languages can be thought of as the analogue of reversibility in regular languages. While reversible languages admit a hierarchy, namely k-reversible regular languages for each nonnegative integer k, Clark and Eyraud targeted the subclass of context-free languages that corresponds to zero-reversible regular languages only. Following Clark and Eyraud's proposal, this paper introduces a hierarchy of substitutable context-free languages as the analogue of that of k-reversible regular languages and shows that each class in the hierarchy is also polynomial-time identifiable in the limit from positive data.",

author = "Ryo Yoshinaka",

year = "2008",

month = nov,

day = "28",

doi = "10.1007/978-3-540-88009-7_21",

language = "English",

isbn = "3540880089",

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

pages = "266--279",

booktitle = "Grammatical Inference",

note = "9th International Colloquium on Grammatical Inference, ICGI 2008 ; Conference date: 22-09-2008 Through 24-09-2008",

}

TY - GEN

T1 - Identification in the limit of k,l-substitutable context-free languages

AU - Yoshinaka, Ryo

PY - 2008/11/28

Y1 - 2008/11/28

N2 - Recently Clark and Eyraud (2005, 2007) have shown that substitutable context-free languages are polynomial-time identifiable in the limit from positive data. Substitutability in context-free languages can be thought of as the analogue of reversibility in regular languages. While reversible languages admit a hierarchy, namely k-reversible regular languages for each nonnegative integer k, Clark and Eyraud targeted the subclass of context-free languages that corresponds to zero-reversible regular languages only. Following Clark and Eyraud's proposal, this paper introduces a hierarchy of substitutable context-free languages as the analogue of that of k-reversible regular languages and shows that each class in the hierarchy is also polynomial-time identifiable in the limit from positive data.

AB - Recently Clark and Eyraud (2005, 2007) have shown that substitutable context-free languages are polynomial-time identifiable in the limit from positive data. Substitutability in context-free languages can be thought of as the analogue of reversibility in regular languages. While reversible languages admit a hierarchy, namely k-reversible regular languages for each nonnegative integer k, Clark and Eyraud targeted the subclass of context-free languages that corresponds to zero-reversible regular languages only. Following Clark and Eyraud's proposal, this paper introduces a hierarchy of substitutable context-free languages as the analogue of that of k-reversible regular languages and shows that each class in the hierarchy is also polynomial-time identifiable in the limit from positive data.

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

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

U2 - 10.1007/978-3-540-88009-7_21

DO - 10.1007/978-3-540-88009-7_21

M3 - Conference contribution

AN - SCOPUS:56649097224

SN - 3540880089

SN - 9783540880080

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

SP - 266

EP - 279

BT - Grammatical Inference

T2 - 9th International Colloquium on Grammatical Inference, ICGI 2008

Y2 - 22 September 2008 through 24 September 2008

ER -

Identification in the limit of k,l-substitutable context-free languages

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this