Learning a Random DFA from Uniform Strings and State Information

DOI10.1007/978-3-319-24486-0_8MaRDI QIDQ2835622zbMATH OpenOpenAlexFDO

Authors Dana Angluin, Dongqu Chen

Publication date 30 November 2016

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

Full work available at URL https://doi.org/10.1007/978-3-319-24486-0_8

zbMATH Keywords

regular languagesPAC learningdeterministic finite automatonstatistical queriesrandom DFA

Mathematics Subject Classification ID

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

Recommendations

• The state complexity of random DFAs
• On learning random DNF formulas under the uniform distribution
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Learning deterministic finite automata from interleaved strings
• Exact learning of random DNF over the uniform distribution
• Efficient learning of typical finite automata from random walks
• Learning probabilistic automata: a study in state distinguishability
• Learning Languages from Bounded Resources: The Case of the DFA and the Balls of Strings
• scientific article; zbMATH DE number 5957212
• Grammatical Inference: Algorithms and Applications

Cites work

• scientific article; zbMATH DE number 3427224 (Why is no real title available?)
• scientific article; zbMATH DE number 733519 (Why is no real title available?)
• A theory of the learnable
• Component-wise perturbation analysis and error bounds for linear least squares solutions
• Cryptographic limitations on learning Boolean formulae and finite automata
• Efficient learning of typical finite automata from random walks
• Efficient noise-tolerant learning from statistical queries
• Exact learning of random DNF over the uniform distribution
• Laplacians and the Cheeger inequality for directed graphs
• Learning Random Log-Depth Decision Trees under Uniform Distribution
• Learning Random Monotone DNF
• Learning regular sets from queries and counterexamples
• Limit distributions of certain characteristics of random automaton graphs
• Lower bounds on learning random structures with statistical queries
• On the learnability of shuffle ideals
• Permutation automata
• The minimum consistent DFA problem cannot be approximated within any polynomial

Cited in

(4)

• Approximate learning of limit-average automata
• On the meeting of random walks on random DFA
• Active coevolutionary learning of deterministic finite automata
• Diameter and stationary distribution of random \(r\)-out digraphs

This page was built for publication: Learning a Random DFA from Uniform Strings and State Information

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