Identification of pattern languages from examples and queries

DOI10.1016/0890-5401(87)90026-5zbMath0635.68096MaRDI QIDQ1097709

Assaf Marron, Ker-I. Ko

Publication date: 1987

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(87)90026-5

zbMATH Keywords

learning; inductive inference; polynomial-time; pattern language; pattern-finding problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68T05: Learning and adaptive systems in artificial intelligence

68T10: Pattern recognition, speech recognition

68T99: Artificial intelligence

03D15: Complexity of computation (including implicit computational complexity)

Related Items

Learning one-variable pattern languages very efficiently on average, in parallel, and by asking queries, Learning regular languages from counterexamples, Learning erasing pattern languages with queries, Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the two-variable pattern-finding problem
• Finding patterns common to a set of strings
• System identification via state characterization
• A theory of the learnable
• A solution of the syntactical induction-inference problem for regular languages
• Complexity of automaton identification from given data
• On the complexity of minimum inference of regular sets
• A note on the number of queries needed to identify regular languages
• Language identification in the limit