Abstract
Deterministic finite automata (DFA) have long served as a fundamental computational model in the study of theoretical computer science, and the problem of learning a DFA from given input data is a classic topic in computational learning theory. In this paper we study the learnability of a random DFA and propose a computationally efficient algorithm for learning and recovering a random DFA from uniform input strings and state information in the statistical query model. A random DFA is uniformly generated: for each state-symbol pair \((q \in Q, \sigma \in \Sigma )\), we choose a state \(q' \in Q\) with replacement uniformly and independently at random and let \(\varphi (q, \sigma ) = q'\), where Q is the state space, \(\Sigma \) is the alphabet and \(\varphi \) is the transition function. The given data are string-state pairs (x, q) where x is a string drawn uniformly at random and q is the state of the DFA reached on input x starting from the start state \(q_0\). A theoretical guarantee on the maximum absolute error of the algorithm in the statistical query model is presented. Extensive experiments demonstrate the efficiency and accuracy of the algorithm.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87–106 (1987)
Angluin, D., Aspnes, J., Eisenstat, S., Kontorovich, A.: On the learnability of shuffle ideals. Journal of Machine Learning Research 14, 1513–1531 (2013)
Angluin, D., Eisenstat, D., Kontorovich, L.A., Reyzin, L.: Lower bounds on learning random structures with statistical queries. In: ALT (2010)
Balle, B.: Ergodicity of random walks on random DFA. CoRR, abs/1311.6830 (2013)
Björck, A.: Component-wise perturbation analysis and error bounds for linear least squares solutions. BIT Numerical Mathematics 31(2), 237–244 (1991)
Chen, D.: Learning shuffle ideals under restricted distributions. In: NIPS (2014)
Chung, F.: Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics 9, 1–19 (2005)
Freund, Y., Kearns, M., Ron, D., Rubinfeld, R., Schapire, R.E., Sellie, L.: Efficient learning of typical finite automata from random walks. In: STOC (1993)
Grusho, A.A.: Limit distributions of certain characteristics of random automaton graphs. Mathematical notes of the Academy of Sciences of the USSR (1973)
Higham, N.J.: A survey of componentwise perturbation theory in numerical linear algebra. In: Proceedings of symposia in applied mathematics (1994)
Jackson, J.C., Lee, H.K., Servedio, R.A., Wan, A.: Learning random monotone DNF. In: Goel, A., Jansen, K., Rolim, J.D.P., Rubinfeld, R. (eds.) APPROX and RANDOM 2008. LNCS, vol. 5171, pp. 483–497. Springer, Heidelberg (2008)
Jackson, J.C., Servedio, R.A.: Learning random log-depth decision trees under uniform distribution. SIAM Journal on Computing 34(5), 1107–1128 (2005)
Kearns, M.: Efficient noise-tolerant learning from statistical queries. J. ACM 45(6), 983–1006 (1998)
Kearns, M., Valiant, L.: Cryptographic limitations on learning boolean formulae and finite automata. J. ACM 41(1), 67–95 (1994)
Pitt, L., Warmuth, M.K.: The minimum consistent DFA problem cannot be approximated within any polynomial. J. ACM 40(1), 95–142 (1993)
Ruiz, J., Garcia, P.: Learning k-piecewise testable languages from positive data. In: Grammatical Interference Learning Syntax from Sentences (1996)
Sellie, L.: Learning random monotone DNF under the uniform distribution. In: COLT, pp. 181–192 (2008)
Sellie, L.: Exact learning of random DNF over the uniform distribution. In: STOC, pp. 45–54. ACM (2009)
Thierrin, G.: Permutation automata. Theory of Computing Systems (1968)
Trakhtenbrot, B.A., Barzdin, I.M.: Finite automata; behavior and synthesis. Fundamental Studies in Computer Science 1 (1973)
Valiant, L.G.: A theory of the learnable. Commun. ACM (November 1984)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Angluin, D., Chen, D. (2015). Learning a Random DFA from Uniform Strings and State Information. In: Chaudhuri, K., GENTILE, C., Zilles, S. (eds) Algorithmic Learning Theory. ALT 2015. Lecture Notes in Computer Science(), vol 9355. Springer, Cham. https://doi.org/10.1007/978-3-319-24486-0_8
Download citation
DOI: https://doi.org/10.1007/978-3-319-24486-0_8
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-24485-3
Online ISBN: 978-3-319-24486-0
eBook Packages: Computer ScienceComputer Science (R0)