The query complexity of learning DFA

DOI10.1007/BF03037351zbMATH Open0812.68107MaRDI QIDQ1336037FDOQ1336037

Authors: José L. Balcázar, Ricard Gavaldà, Osamu Watanabe, J. Díaz 

Publication date: 20 November 1994

Published in: New Generation Computing (Search for Journal in Brave)

Recommendations

• scientific article; zbMATH DE number 1008506
• New bounds for the query complexity of an algorithm that learns DFAs with correction and equivalence queries
• scientific article; zbMATH DE number 1281920
• scientific article; zbMATH DE number 1303603
• How many queries are needed to learn?

zbMATH Keywords

finite automatarandomized learning algorithms

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Cites Work

• Title not available (Why is that?)
• Learning regular sets from queries and counterexamples
• Language identification in the limit
• A theory of the learnable
• When won't membership queries help?
• A framework for polynomial-time query learnability
• Cryptographic limitations on learning Boolean formulae and finite automata
• Asking questions to minimize errors
• Prediction-preserving reducibility
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (8)

• Learning fallible deterministic finite automata
• Learning deterministic finite automata from smallest counterexamples
• Title not available (Why is that?)
• New bounds for the query complexity of an algorithm that learns DFAs with correction and equivalence queries
• The complexity of learning SUBSEQ(A)
• Title not available (Why is that?)
• Types of trusted information that make DFA identification with correction queries feasible
• Even linear simple matrix languages: formal language properties and grammatical inference.

This page was built for publication: The query complexity of learning DFA

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