Polynomial time learning of simple deterministic languages via queries and a representative sample

DOI10.1016/J.TCS.2004.08.012zbMath1086.68078OpenAlexW2018601197MaRDI QIDQ706625

Etsuji Tomita, Matsuaki Terada, Yasuhiro Tajima, Mitsuo Wakatsuki

Publication date: 9 February 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.08.012

zbMATH Keywords

Context-free languageGrammatical inferenceLearning via queriesRepresentative sampleSimple deterministic grammar

Mathematics Subject Classification ID

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

Related Items (2)

Efficiency in the Identification in the Limit Learning Paradigm ⋮ Polynomial Time Probabilistic Learning of a Subclass of Linear Languages with Queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Learning context-free grammars from structural data in polynomial time
• Learning regular sets from queries and counterexamples
• Queries and concept learning
• A hierarchy of language families learnable by regular language learning
• A theory of the learnable
• A note on the number of queries needed to identify regular languages
• Properties of deterministic top-down grammars

This page was built for publication: Polynomial time learning of simple deterministic languages via queries and a representative sample