A Polynomial Algorithm for the Inference of Context Free Languages

DOI10.1007/978-3-540-88009-7_3MaRDI QIDQ3530184zbMATH OpenOpenAlexFDO

Authors Alexander Clark, Rémi Eyraud, Amaury Habrard

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_3

Mathematics Subject Classification ID

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

Recommendations

• Using contextual representations to efficiently learn context-free languages
• Inductive inference of context-free languages based on context-free expressions
• Polynomial identification in the limit of substitutable context-free languages
• Inferring Grammars for Mildly Context Sensitive Languages in Polynomial-Time
• Learning context-free grammars from structural data in polynomial time

Cited in

(25)

• A quasi-polynomial-time algorithm for sampling words from a context-free language
• Grammatical inference of directed acyclic graph languages with polynomial time complexity
• \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity
• A polynomial-time parsing algorithm for \(K\)-depth languages
• Synthesizing context-free grammars from recurrent neural networks
• Efficient learning of multiple context-free languages with multidimensional substitutability from positive data
• Polynomial Time Learning of Some Multiple Context-Free Languages with a Minimally Adequate Teacher
• Polynomial identification in the limit of substitutable context-free languages
• scientific article; zbMATH DE number 7228439 (Why is no real title available?)
• Inferring Grammars for Mildly Context Sensitive Languages in Polynomial-Time
• A local search algorithm for grammatical inference
• Learning mildly context-sensitive languages with multidimensional substitutability from positive data
• scientific article; zbMATH DE number 4051037 (Why is no real title available?)
• Inductive inference of context-free languages based on context-free expressions
• A strongly polynomial algorithm for criticality of branching processes and consistency of stochastic context-free grammars
• scientific article; zbMATH DE number 177455 (Why is no real title available?)
• scientific article; zbMATH DE number 517032 (Why is no real title available?)
• scientific article; zbMATH DE number 2077185 (Why is no real title available?)
• scientific article; zbMATH DE number 1796949 (Why is no real title available?)
• Polynomial time algorithm for inferring subclasses of parallel internal column contextual array languages
• The inherent ambiguity partial algorithm problem for context free languages
• Grammatical Inference: Algorithms and Applications
• scientific article; zbMATH DE number 2209444 (Why is no real title available?)
• A polynomial algorithm for the membership problem with categorial grammars
• Polynomial inference of universal automata from membership and equivalence queries

This page was built for publication: A Polynomial Algorithm for the Inference of Context Free Languages

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