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

DOI10.1007/978-3-540-88009-7_21MaRDI QIDQ3528426zbMATH OpenOpenAlexFDO

Authors Ryo Yoshinaka

Publication date 16 October 2008

Published in Grammatical Inference: Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-88009-7_21

Mathematics Subject Classification ID

Computational learning theory (68Q32) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• Algorithmic Learning Theory
• Polynomial identification in the limit of substitutable context-free languages
• An inverse limit of context-free grammars -- a new approach to identifiability in the limit
• scientific article; zbMATH DE number 996379
• On the complexity of consistent identification of some classes of structure languages
• Identifiability of subspaces and homomorphic images of zero-reversible languages
• Polynomial-time identification of multiple context-free languages from positive data and membership queries
• On sufficient conditions to identify in the limit classes of grammars from polynomial time and data
• Some subclasses of context-free languages in NC^ 1
• Identification in the limit of categorial grammars

Cites work

• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Algorithmic Learning Theory
• An elementary proof of double Greibach normal form
• Characteristic sets for polynomial grammatical inference
• Identifiability of subspaces and homomorphic images of zero-reversible languages
• Inference of Reversible Languages
• Iterated transductions and efficient learning from positive data: A unifying view
• Language identification in the limit
• Learning approximately regular languages with reversible languages
• Learning indexed families of recursive languages from positive data: A survey
• Matrix Equations and Normal Forms for Context-Free Grammars
• NTS languages are deterministic and congruential
• On inferring zero-reversible languages
• PAC-Learning Unambiguous NTS Languages
• Polynomial identification in the limit of substitutable context-free languages
• Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries
• Polynomial-time identification of very simple grammars from positive data.
• The equivalence and inclusion problems for NTS languages

Cited in

(13)

• Beyond operator-precedence grammars and languages
• Efficient learning of multiple context-free languages with multidimensional substitutability from positive data
• On the complexity of consistent identification of some classes of structure languages
• An inverse limit of context-free grammars -- a new approach to identifiability in the limit
• Polynomial identification in the limit of substitutable context-free languages
• Learning mildly context-sensitive languages with multidimensional substitutability from positive data
• Identifiability of subspaces and homomorphic images of zero-reversible languages
• Fragmentation: Enhancing identifiability
• Inductive inference of monogenic pure context-free languages
• Higher-order operator precedence languages
• Algorithmic Learning Theory
• Probabilistic learnability of context-free grammars with basic distributional properties from positive examples
• An elementary proof of a generalization of double Greibach normal form

This page was built for publication: Identification in the Limit of k,l-Substitutable Context-Free Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3528426)