Learning a Random DFA from Uniform Strings and State Information

DOI10.1007/978-3-319-24486-0_8zbMath1471.68099OpenAlexW2260314326MaRDI QIDQ2835622

Dongqu Chen, Dana Angluin

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

PAC learningregular languagesdeterministic finite automatonstatistical queriesrandom DFA

Mathematics Subject Classification ID

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

Related Items (2)

Unnamed Item ⋮ Diameter and stationary distribution of random \(r\)-out digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Component-wise perturbation analysis and error bounds for linear least squares solutions
• Learning regular sets from queries and counterexamples
• Laplacians and the Cheeger inequality for directed graphs
• Limit distributions of certain characteristics of random automaton graphs
• Efficient noise-tolerant learning from statistical queries
• Learning Random Monotone DNF
• A theory of the learnable
• The minimum consistent DFA problem cannot be approximated within any polynomial
• Cryptographic limitations on learning Boolean formulae and finite automata
• Lower Bounds on Learning Random Structures with Statistical Queries
• Exact learning of random DNF over the uniform distribution
• Efficient learning of typical finite automata from random walks
• Learning Random Log-Depth Decision Trees under Uniform Distribution
• Permutation automata

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