Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries

DOI10.1007/978-3-540-75225-7_23zbMath1142.68409OpenAlexW1789613047MaRDI QIDQ3520065

Cristina Tîrnăucă, Timo Knuutila

Publication date: 19 August 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-75225-7_23

zbMATH Keywords

polynomial algorithmspattern languages\(k\)-reversible languagescorrection queries

Mathematics Subject Classification ID

Computational learning theory (68Q32) Formal languages and automata (68Q45)

Related Items (5)

A model of language learning with semantics and meaning-preserving corrections ⋮ Learning quantum finite automata with queries ⋮ A Note on the Relationship between Different Types of Correction Queries ⋮ Identification in the Limit of k,l-Substitutable Context-Free Languages ⋮ One-shot learners using negative counterexamples and nearest positive examples

Cites Work

• Unnamed Item
• Unnamed Item
• Query learning of regular tree languages: How to avoid dead states
• Learning context-free grammars from structural data in polynomial time
• Identification of pattern languages from examples and queries
• Learning regular sets from queries and counterexamples
• Learning DFA from Correction and Equivalence Queries
• A theory of the learnable
• Inference of Reversible Languages
• A note on the number of queries needed to identify regular languages
• Learning two-tape automata from queries and counterexamples
• A Characterization of the Language Classes Learnable with Correction Queries
• Language identification in the limit

This page was built for publication: Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries