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

DOI10.1016/J.TCS.2004.08.012zbMATH Open1086.68078OpenAlexW2018601197MaRDI QIDQ706625FDOQ706625

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

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

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)

Cites Work

• Title not available (Why is that?)
• Learning regular sets from queries and counterexamples
• Queries and concept learning
• A theory of the learnable
• Title not available (Why is that?)
• Learning context-free grammars from structural data in polynomial time
• A note on the number of queries needed to identify regular languages
• Properties of deterministic top-down grammars
• Title not available (Why is that?)
• A hierarchy of language families learnable by regular language learning
• Title not available (Why is that?)

Cited In (11)

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

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)