Polynomial Identification in the Limit of Substitutable Context-free Languages Export

@article{clark07b, abstract = {This paper formalises 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 languages. 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. It transpires that it is not necessary to identify constituents in order to learn a context-free language—it is sufficient to identify the syntactic congruence, and the operations of the syntactic monoid can be converted into a context-free grammar. 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. We also demonstrate that an implementation of this algorithm is capable of learning a classic example of structure dependent syntax in English: this constitutes a refutation of an argument that has been used in support of nativist theories of language.}, author = {Clark, Alexander and Eyraud, R\'{e}mi}, citeulike-article-id = {5945905}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1314556}, issn = {1532-4435}, journal = {J. Mach. Learn. Res.}, keywords = {grammatical-inference, parsing, unsupervised}, pages = {1725--1745}, posted-at = {2009-10-15 20:17:38}, priority = {0}, publisher = {JMLR.org}, title = {Polynomial Identification in the Limit of Substitutable Context-free Languages}, url = {http://portal.acm.org/citation.cfm?id=1314556}, volume = {8}, year = {2007} }

TY - JOUR ID - clark07b L3 - citeulike-article-id:5945905 N2 - This paper formalises 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 languages. 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. It transpires that it is not necessary to identify constituents in order to learn a context-free language—it is sufficient to identify the syntactic congruence, and the operations of the syntactic monoid can be converted into a context-free grammar. 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. We also demonstrate that an implementation of this algorithm is capable of learning a classic example of structure dependent syntax in English: this constitutes a refutation of an argument that has been used in support of nativist theories of language. JF - J. Mach. Learn. Res. SN - 1532-4435 EP - 1745 TI - Polynomial Identification in the Limit of Substitutable Context-free Languages PB - JMLR.org VL - 8 SP - 1725 KW - grammatical-inference KW - parsing KW - unsupervised AU - Clark, Alexander AU - Eyraud, Rémi PY - 2007/// UR - http://portal.acm.org/citation.cfm?id=1314556 ER -