Learning regular languages from counterexamples

DOI10.1016/0022-0000(91)90016-XzbMath0769.68108WikidataQ125034679 ScholiaQ125034679MaRDI QIDQ1176104

Oscar H. Ibarra, Tao Jiang

Publication date: 25 June 1992

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

zbMATH Keywords

regular languagescounterexamplespattern languageslearnability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Formal languages and automata (68Q45)

Related Items

Pattern languages with and without erasing ⋮ On the equivalence problem for E-pattern languages ⋮ A Myhill-Nerode theorem for finite state matrix automata and finite matrix languages ⋮ Inclusion is undecidable for pattern languages ⋮ Automatic symbolic compositional verification by learning assumptions ⋮ Learnability of automatic classes ⋮ Automatic learning from positive data and negative counterexamples ⋮ Even linear simple matrix languages: formal language properties and grammatical inference.

Cites Work

• Unnamed Item
• Identification of pattern languages from examples and queries
• Learning regular sets from queries and counterexamples
• Finding patterns common to a set of strings
• Learning automata from ordered examples
• A theory of the learnable
• A note on the number of queries needed to identify regular languages