Learning a Random DFA from Uniform Strings and State Information

DOI10.1007/978-3-319-24486-0_8zbMATH Open1471.68099OpenAlexW2260314326MaRDI QIDQ2835622FDOQ2835622

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

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

zbMATH Keywords

regular languagesPAC learningdeterministic finite automatonstatistical queriesrandom DFA

Mathematics Subject Classification ID

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

Cites Work

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

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)