Abstract
Automata learning is a popular technique used to automatically construct an automaton model from queries. Much research went into devising ad hoc adaptations of algorithms for different types of automata. The CALF project seeks to unify these using category theory in order to ease correctness proofs and guide the design of new algorithms. In this paper, we extend CALF to cover learning of algebraic structures that may not have a coalgebraic presentation. Furthermore, we provide a detailed algorithmic account of an abstract version of the popular \(\mathtt {L}^{\!\star }\) algorithm, which was missing from CALF. We instantiate the abstract theory to a large class of \(\mathbf {Set}\) functors, by which we recover for the first time practical tree automata learning algorithms from an abstract framework and at the same time obtain new algorithms to learn algebras of quotiented polynomial functors.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
References
Aarts, F., Fiterau-Brostean, P., Kuppens, H., Vaandrager, F.: Learning register automata with fresh value generation. In: Leucker, M., Rueda, C., Valencia, F.D. (eds.) ICTAC 2015. LNCS, vol. 9399, pp. 165–183. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-25150-9_11
Aarts, F., de Ruiter, J., Poll, E.: Formal models of bank cards for free. In: ICST, pp. 461–468 (2013). https://doi.org/10.1109/ICSTW.2013.60
Aarts, F., Schmaltz, J., Vaandrager, F.: Inference and abstraction of the biometric passport. In: Margaria, T., Steffen, B. (eds.) ISoLA 2010. LNCS, vol. 6415, pp. 673–686. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-16558-0_54
Aarts, F., Vaandrager, F.: Learning I/O automata. In: Gastin, P., Laroussinie, F. (eds.) CONCUR 2010. LNCS, vol. 6269, pp. 71–85. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15375-4_6
Adámek, J., Milius, S., Moss, L.S.: On well-founded and recursive coalgebras. In: FoSSaCS 2020. LNCS, vol. 12077, pp. 17–36. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45231-5_2
Adámek, J., Milius, S., Velebil, J.: Free iterative theories: a coalgebraic view. MFCS 13(2), 259–320 (2003). https://doi.org/10.1017/S0960129502003924
Adámek, J., Trnková, V.: Automata and Algebras in Categories. Kluwer, Dordrecht (1989)
Angluin, D.: Learning regular sets from queries and counterexamples. Inf. Comput. 75(2), 87–106 (1987). https://doi.org/10.1016/0890-5401(87)90052-6
Angluin, D., Fisman, D.: Learning regular omega languages. Theor. Comput. Sci. 650, 57–72 (2016). https://doi.org/10.1016/j.tcs.2016.07.031
Arbib, M.A., Manes, E.G.: A categorist’s view of automata and systems. In: Manes, E.G. (ed.) Category Theory Applied to Computation and Control. LNCS, vol. 25, pp. 51–64. Springer, Heidelberg (1975). https://doi.org/10.1007/3-540-07142-3_61
Awodey, S.: Category Theory. Oxford University Press, Oxford (2010)
Barlocco, S., Kupke, C., Rot, J.: Coalgebra learning via duality. In: Bojańczyk, M., Simpson, A. (eds.) FoSSaCS 2019. LNCS, vol. 11425, pp. 62–79. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17127-8_4
Bergadano, F., Varricchio, S.: Learning behaviors of automata from multiplicity and equivalence queries. SIAM J. Comput. 25(6), 1268–1280 (1996). https://doi.org/10.1137/S009753979326091X
Besombes, J., Marion, J.: Learning tree languages from positive examples and membership queries. Theor. Comput. Sci. 382(3), 183–197 (2007). https://doi.org/10.1016/j.tcs.2007.03.038
Colcombet, T., Petrisan, D., Stabile, R.: Learning automata and transducers: a categorical approach. In: CSL, vol. 183, pp. 15:1–15:17 (2021). https://doi.org/10.4230/LIPIcs.CSL.2021.15
Comon, H., et al.: Tree Automata Techniques and Applications (2008). https://hal.inria.fr/hal-03367725
de la Higuera, C.: Grammatical Inference: Learning Automata and Grammars. Cambridge University Press, Cambridge (2010)
Drewes, F., Högberg, J.: Learning a regular tree language from a teacher. In: Ésik, Z., Fülöp, Z. (eds.) DLT 2003. LNCS, vol. 2710, pp. 279–291. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45007-6_22
Fiterău-Broştean, P., Janssen, R., Vaandrager, F.: Combining model learning and model checking to analyze TCP implementations. In: Chaudhuri, S., Farzan, A. (eds.) CAV 2016. LNCS, vol. 9780, pp. 454–471. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-41540-6_25
Gischer, J.L.: The equational theory of pomsets. Theor. Comput. Sci. 61, 199–224 (1988). https://doi.org/10.1016/0304-3975(88)90124-7
Gold, E.M.: System identification via state characterization. Automatica 8(5), 621–636 (1972). https://doi.org/10.1016/0005-1098(72)90033-7
Grabowski, J.: On partial languages. Fundam. Inform. 4(2), 427 (1981)
van Heerdt, G.: An abstract automata learning framework. Master’s thesis, Radboud Universiteit Nijmegen (2016)
van Heerdt, G., Jacobs, B., Kappé, T., Silva, A.: Learning to coordinate. In: de Boer, F., Bonsangue, M., Rutten, J. (eds.) It’s All About Coordination. LNCS, vol. 10865, pp. 139–159. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-90089-6_10
van Heerdt, G., Kappé, T., Rot, J., Sammartino, M., Silva, A.: Tree automata as algebras: minimisation and determinisation. In: CALCO, vol. 139, pp. 6:1–6:22 (2019). https://doi.org/10.4230/LIPIcs.CALCO.2019.6
van Heerdt, G., Kappé, T., Rot, J., Sammartino, M., Silva, A.: A categorical framework for learning generalised tree automata. arXiv e-prints (2020). https://arxiv.org/abs/2001.05786
van Heerdt, G., Kappé, T., Rot, J., Silva, A.: Learning pomset automata. In: FOSSACS 2021. LNCS, vol. 12650, pp. 510–530. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-71995-1_26
van Heerdt, G., Kupke, C., Rot, J., Silva, A.: Learning weighted automata over principal ideal domains. In: FoSSaCS 2020. LNCS, vol. 12077, pp. 602–621. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45231-5_31
van Heerdt, G., Sammartino, M., Silva, A.: CALF: categorical automata learning framework. In: CSL, pp. 29:1–29:24 (2017). https://doi.org/10.4230/LIPIcs.CSL.2017.29
van Heerdt, G., Sammartino, M., Silva, A.: Learning automata with side-effects. In: Petrişan, D., Rot, J. (eds.) CMCS 2020. LNCS, vol. 12094, pp. 68–89. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57201-3_5
Isberner, M., Howar, F., Steffen, B.: The open-source LearnLib. In: Kroening, D., Păsăreanu, C.S. (eds.) CAV 2015. LNCS, vol. 9206, pp. 487–495. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-21690-4_32
Jacobs, B., Silva, A.: 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. LNCS, vol. 8464, pp. 384–406. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06880-0_20
Lane, S.M.: Categories for the Working Mathematician. Graduate Texts in Mathematics, Springer, New York (1998). https://doi.org/10.1007/978-1-4612-9839-7
Lodaya, K., Weil, P.: Series-parallel languages and the bounded-width property. Theoret. Comput. Sci. 237(1), 347–380 (2000). https://doi.org/10.1016/S0304-3975(00)00031-1
Lüth, C., Ghani, N.: Composing monads using coproducts. In: ICFP, pp. 133–144 (2002). https://doi.org/10.1145/581478.581492
Moerman, J., Sammartino, M., Silva, A., Klin, B., Szynwelski, M.: Learning nominal automata. In: POPL, pp. 613–625 (2017). https://doi.org/10.1145/3009837.3009879
Mues, M., Howar, F., Luckow, K.S., Kahsai, T., Rakamaric, Z.: Releasing the PSYCO: using symbolic search in interface generation for Java. ACM SIGSOFT Softw. Eng. Notes 41(6), 1–5 (2016). https://doi.org/10.1145/3011286.3011298
Osius, G.: Categorical set theory: a characterization of the category of sets. J. Pure Appl. Algebra 4(1), 79–119 (1974)
Sakakibara, Y.: Learning context-free grammars from structural data in polynomial time. Theor. Comput. Sci. 76(2–3), 223–242 (1990). https://doi.org/10.1016/0304-3975(90)90017-C
Taylor, P.: Practical Foundations of Mathematics. Cambridge University Press, Cambridge (1999)
Urbat, H., Schröder, L.: Automata learning: an algebraic approach. In: LICS, pp. 900–914 (2020). https://doi.org/10.1145/3373718.3394775
Vaandrager, F.W.: Model learning. Commun. ACM 60(2), 86–95 (2017). https://doi.org/10.1145/2967606
Acknowledgements
T. Kappé was partially supported by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101027412 (VERLAN), as well as ERC Starting Grant 679127 (ProFoundNet). Gerco van Heerdt, Matteo Sammartino, and Alexandra Silva were partially supported by the EPSRC Standard Grant CLeVer (EP/S028641/1).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 IFIP International Federation for Information Processing
About this paper
Cite this paper
Heerdt, G.v., Kappé, T., Rot, J., Sammartino, M., Silva, A. (2022). A Categorical Framework for Learning Generalised Tree Automata. In: Hansen, H.H., Zanasi, F. (eds) Coalgebraic Methods in Computer Science. CMCS 2022. Lecture Notes in Computer Science, vol 13225. Springer, Cham. https://doi.org/10.1007/978-3-031-10736-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-031-10736-8_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-10735-1
Online ISBN: 978-3-031-10736-8
eBook Packages: Computer ScienceComputer Science (R0)