Identification in the Limit of $k,l$-Substitutable Context-Free Languages TeX Export

@incollection{yoshinaka08, 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 = {Yoshinaka, Ryo}, citeulike-article-id = {5945849}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-88009-7_21}, citeulike-linkout-1 = {http://www.springerlink.com/content/x151vk796j72p254}, doi = {10.1007/978-3-540-88009-7_21}, journal = {Grammatical Inference: Algorithms and Applications}, keywords = {grammatical-inference, parsing, unsupervised}, pages = {266--279}, posted-at = {2009-10-15 20:04:07}, priority = {2}, title = {Identification in the Limit of \$k,l\$-Substitutable Context-Free Languages}, url = {http://dx.doi.org/10.1007/978-3-540-88009-7_21}, year = {2008} }

TY - CHAP ID - yoshinaka08 L3 - citeulike-article-id:5945849 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. JF - Grammatical Inference: Algorithms and Applications EP - 279 TI - Identification in the Limit of $k,l$-Substitutable Context-Free Languages SP - 266 KW - grammatical-inference KW - parsing KW - unsupervised AU - Yoshinaka, Ryo PY - 2008/// UR - http://dx.doi.org/10.1007/978-3-540-88009-7_21 ER -