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

DOI10.1016/J.TCS.2004.08.012MaRDI QIDQ706625zbMATH OpenOpenAlexFDO

Authors Yasuhiro Tajima, Etsuji Tomita, Mitsuo Wakatsuki, Matsuaki Terada

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

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

Recommendations

• scientific article; zbMATH DE number 1670730
• scientific article; zbMATH DE number 67617
• Learning regular sets from queries and counterexamples
• scientific article; zbMATH DE number 2019609
• Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries

Cites work

• scientific article; zbMATH DE number 1670730 (Why is no real title available?)
• scientific article; zbMATH DE number 3490487 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A hierarchy of language families learnable by regular language learning
• A note on the number of queries needed to identify regular languages
• A theory of the learnable
• Learning context-free grammars from structural data in polynomial time
• Learning regular sets from queries and counterexamples
• Properties of deterministic top-down grammars
• Queries and concept learning

Cited in

(11)

• On polynomial-time learnability in the limit of strictly deterministic automata
• scientific article; zbMATH DE number 1670730 (Why is no real title available?)
• scientific article; zbMATH DE number 2089362 (Why is no real title available?)
• A quasi-polynomial-time algorithm for sampling words from a context-free language
• Language learning from membership queries and characteristic examples
• Polynomial Time Learning of Some Multiple Context-Free Languages with a Minimally Adequate Teacher
• scientific article; zbMATH DE number 67617 (Why is no real title available?)
• A family of languages which is polynomial-time learnable from positive data in pitt's sense
• scientific article; zbMATH DE number 2019609 (Why is no real title available?)
• Polynomial Time Probabilistic Learning of a Subclass of Linear Languages with Queries
• Efficiency in the identification in the limit learning paradigm

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

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