ML Anthology

Identification in the Limit of Substitutable Context-Free Languages

Alexander Clark, Rémi Eyraud
ALT 2005 pp. 283-296
doi:10.1007/11564089_23 /alt/2005/clark2005alt-identification/

Abstract

This paper formalisms the idea of substitutability introduced by Zellig Harris in the 1950s and makes it the basis for a learning algorithm from positive data only for a subclass of context-free grammars. We show that there is a polynomial characteristic set, and thus prove polynomial identification in the limit of this class. We discuss the relationship of this class of languages to other common classes discussed in grammatical inference. We also discuss modifications to the algorithm that produces a reduction system rather than a context-free grammar, that will be much more compact. We discuss the relationship to Angluin’s notion of reversibility for regular languages.

PDF ALT Semantic Scholar

Cite

Text

Clark and Eyraud. "Identification in the Limit of Substitutable Context-Free Languages." International Conference on Algorithmic Learning Theory, 2005. doi:10.1007/11564089_23

Markdown

[Clark and Eyraud. "Identification in the Limit of Substitutable Context-Free Languages." International Conference on Algorithmic Learning Theory, 2005.](https://mlanthology.org/alt/2005/clark2005alt-identification/) doi:10.1007/11564089_23

BibTeX

@inproceedings{clark2005alt-identification,
  title     = {{Identification in the Limit of Substitutable Context-Free Languages}},
  author    = {Clark, Alexander and Eyraud, Rémi},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2005},
  pages     = {283-296},
  doi       = {10.1007/11564089_23},
  url       = {https://mlanthology.org/alt/2005/clark2005alt-identification/}
}