Polynomial Time Probabilistic Learning of a Subclass of Linear Languages with Queries

DOI10.1007/978-3-540-88009-7_15zbMath1177.68123OpenAlexW1518563546MaRDI QIDQ3528418

Yoshiyuki Kotani, Yasuhiro Tajima

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_15

zbMATH Keywords

PAC learningrepresentative samplelinear languagelearning via queries

Mathematics Subject Classification ID

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

Related Items (1)

Probabilistic learnability of context-free grammars with basic distributional properties from positive examples

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial time learning of simple deterministic languages via queries and a representative sample
• Teaching a smarter learner.
• Learning regular sets from queries and counterexamples
• Characteristic sets for polynomial grammatical inference
• 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

This page was built for publication: Polynomial Time Probabilistic Learning of a Subclass of Linear Languages with Queries