Learning context-free grammars from structural data in polynomial time
From MaRDI portal
Publication:917318
DOI10.1016/0304-3975(90)90017-CzbMath0704.68067MaRDI QIDQ917318
Publication date: 1990
Published in: Theoretical Computer Science (Search for Journal in Brave)
context-free grammarscontext-free languagesmembership queriesequivalence queriesgrammatical inference problemStructural descriptionsunlabelled derivation trees
Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)
Related Items
Computing the relative entropy between regular tree languages ⋮ Learning tree languages from positive examples and membership queries ⋮ LARS: a learning algorithm for rewriting systems ⋮ On the regularity and learnability of ordered DAG languages ⋮ A framework for polynomial-time query learnability ⋮ Four one-shot learners for regular tree languages and their polynomial characterizability ⋮ Recent advances of grammatical inference ⋮ Grammatical inference: An old and new paradigm ⋮ Language learning from membership queries and characteristic examples ⋮ Active learning for deterministic bottom-up nominal tree automata ⋮ Inferring Symbolic Automata ⋮ Learning picture sets from examples ⋮ Learning failure-free PRISM programs ⋮ Learning and characterizing fully-ordered lattice automata ⋮ Unnamed Item ⋮ Learning tree languages from text ⋮ Distributional Learning of Context-Free and Multiple Context-Free Grammars ⋮ Learning Tree Languages ⋮ Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries ⋮ On Learning Regular Expressions and Patterns Via Membership and Correction Queries ⋮ The grammatical inference problem for the Szilard languages of linear grammars ⋮ Learning pomset automata ⋮ Efficient learning of context-free grammars from positive structural examples ⋮ Grammatical inference of directed acyclic graph languages with polynomial time complexity ⋮ On the structural grammatical inference problem for some classes of context-free grammars ⋮ Remarks on the structural grammatical inference problem for context-free grammars ⋮ Learning context-free grammars using tabular representations ⋮ Evolutionary induction of stochastic context free grammars ⋮ Polynomial time learning of simple deterministic languages via queries and a representative sample ⋮ On learning from queries and counterexamples in the presence of noise ⋮ MAT learners for tree series: an abstract data type and two realizations ⋮ Necessary and sufficient conditions for learning with correction queries ⋮ Learning algorithms ⋮ An inductive method with genetic algorithm for learning phrase-structure-rule of natural language ⋮ A categorical framework for learning generalised tree automata
Cites Work
