Abstract
Automata learning is a known technique to infer a finite state machine from a set of observations. In this paper, we revisit Angluin’s original algorithm from a categorical perspective. This abstract view on the main ingredients of the algorithm lays a uniform framework to derive algorithms for other types of automata. We show a straightforward generalization to Moore and Mealy machines, which yields an algorithm already know in the literature, and we discuss generalizations to other types of automata, including weighted automata.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aarts, F.: Inference and abstraction of communication protocols. Master’s thesis, Radboud University Nijmegen and Uppsala University (2009)
Aarts, F., de Ruiter, J., Poll, E.: Formal models of bank cards for free. In: ICST Workshops, pp. 461–468. IEEE (2013)
Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Analysis of Computer Algorithms. Addison-Wesley (1974)
Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87–106 (1987)
Angluin, D., Csürös, M.: Learning Markov chains with variable memory length from noisy output. In: Freund, Y., Schapire, R.E. (eds.) COLT, pp. 298–308. ACM (1997)
Arbib, M.A., Manes, E.G.: Adjoint machines, state-behavior machines, and duality. Journal of Pure and Applied Algebra 6(3), 313–344 (1975)
Barr, M., Wells, C.: Toposes, Triples and Theories. Springer, Berlin (1985) Revized and corrected version available from URL, www.cwru.edu/artsci/math/wells/pub/ttt.html
Bonchi, F., Bonsangue, M., Hansen, H., Panangaden, P., Rutten, J., Silva, A.: Algebra-coalgebra duality in Brzozowski’s minimization algorithm. In: ACM Transactions on Computational Logic (TOCL) (2014)
Bonchi, F., Bonsangue, M.M., Rutten, J.J.M.M., Silva, A.: Brzozowski’s Algorithm (Co)Algebraically. In: Constable, R.L., Silva, A. (eds.) Kozen Festschrift. LNCS, vol. 7230, pp. 12–23. Springer, Heidelberg (2012)
Bonchi, F., Caltais, G., Pous, D., Silva, A.: Brzozowski’s and up-to algorithms for must testing. In: Shan, C.-C. (ed.) APLAS 2013. LNCS, vol. 8301, pp. 1–16. Springer, Heidelberg (2013)
Bonchi, F., Pous, D.: Checking nfa equivalence with bisimulations up to congruence. In: Giacobazzi, R., Cousot, R. (eds.) POPL, pp. 457–468. ACM (2013)
Boreale, M.: Weighted bisimulation in linear algebraic form. In: Bravetti, M., Zavattaro, G. (eds.) CONCUR 2009. LNCS, vol. 5710, pp. 163–177. Springer, Heidelberg (2009)
Eilenberg, S.: Automata, languages, and machines. Pure and Applied Mathematics. Elsevier Science (1974)
Hopcroft, J.E., Karp, R.M.: A linear algorithm for testing equivalence of finite automata. Technical report, Cornell University (1979)
Hopcroft, J.E.: An n log n algorithm for minimizing states in a finite automaton. Technical report, Stanford University, Stanford, CA, USA (1971)
Kalman, R.: On the general theory of control systems. IRE Transactions on Automatic Control 4(3), 110–110 (1959)
Pous, D., Sangiorgi, D.: Enhancements of the coinductive proof method. In: Sangiorgi, D., Rutten, J. (eds.) Advanced Topics in Bisimulation and Coinduction. Cambridge Tracts in Theoretical Computer Science, vol. 52, Cambridge University Press (November 2011)
Rot, J., Bonsangue, M., Rutten, J.M.M.: Coalgebraic bisimulation-up-to. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds.) SOFSEM 2013. LNCS, vol. 7741, pp. 369–381. Springer, Heidelberg (2013)
Rutten, J.J.M.M.: Automata and coinduction (an exercise in coalgebra). In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 194–218. Springer, Heidelberg (1998)
Sangiorgi, D.: Beyond Bisimulation: The “up-to” Techniques. In: de Boer, F.S., Bonsangue, M.M., Graf, S., de Roever, W.-P. (eds.) FMCO 2005. LNCS, vol. 4111, pp. 161–171. Springer, Heidelberg (2006)
Shahbaz, M., Groz, R.: Inferring Mealy Machines. In: Cavalcanti, A., Dams, D.R. (eds.) FM 2009. LNCS, vol. 5850, pp. 207–222. Springer, Heidelberg (2009)
De Wulf, M., Doyen, L., Henzinger, T.A., Raskin, J.-F.: Antichains: A new algorithm for checking universality of finite automata. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 17–30. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Jacobs, B., Silva, A. (2014). Automata Learning: A Categorical Perspective. In: van Breugel, F., Kashefi, E., Palamidessi, C., Rutten, J. (eds) Horizons of the Mind. A Tribute to Prakash Panangaden. Lecture Notes in Computer Science, vol 8464. Springer, Cham. https://doi.org/10.1007/978-3-319-06880-0_20
Download citation
DOI: https://doi.org/10.1007/978-3-319-06880-0_20
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-06879-4
Online ISBN: 978-3-319-06880-0
eBook Packages: Computer ScienceComputer Science (R0)