Efficient learning of typical finite automata from random walks
From MaRDI portal
Publication:1373138
DOI10.1006/inco.1997.2648zbMath0889.68131OpenAlexW2043635106MaRDI QIDQ1373138
Dana Ron, Yoav Freund, Michael Kearns, Robert E. Schapire, Ronitt Rubinfeld, Linda M. Sellie
Publication date: 2 June 1998
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/inco.1997.2648
Learning and adaptive systems in artificial intelligence (68T05) Formal languages and automata (68Q45)
Related Items
Locality and checkability in wait-free computing, Natural Language Processing, Moving from Rules to Data, Locality and Checkability in Wait-Free Computing, Learning Finite Automata Using Label Queries, The power of a pebble: Exploring and mapping directed graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Prediction-preserving reducibility
- Generating quasi-random sequences from semi-random sources
- Learning regular sets from queries and counterexamples
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- Predicting \(\{ 0,1\}\)-functions on randomly drawn points
- Biased random walks
- Inference of finite automata using homing sequences
- System identification via state characterization
- On the learnability of discrete distributions
- A theory of the learnable
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Computational limitations on learning from examples
- Universal prediction of individual sequences
- The minimum consistent DFA problem cannot be approximated within any polynomial
- Complexity of automaton identification from given data
- On the complexity of minimum inference of regular sets
- Cryptographic limitations on learning Boolean formulae and finite automata
- New approximation algorithms for graph coloring
- Diversity-based inference of finite automata
