Efficient learning of typical finite automata from random walks

DOI10.1145/167088.167191zbMath1310.68131OpenAlexW2045291344MaRDI QIDQ5248500

Yoav Freund, Dana Ron, Michael Kearns, Robert E. Schapire, Ronitt Rubinfeld, Linda M. Sellie

Publication date: 7 May 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.186.6469

Mathematics Subject Classification ID

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

Related Items

Learning fallible deterministic finite automata, The power of amnesia: Learning probabilistic automata with variable memory length, Kernel methods for learning languages, On learning thresholds of parities and unions of rectangles in random walk models, Model-based learning of interaction strategies in multi-agent systems, On the learnability and usage of acyclic probabilistic finite automata, Learning a Random DFA from Uniform Strings and State Information, Exploiting random walks for learning