Coalgebra learning via duality. (English) Zbl 1524.68158
Bojańczyk, Mikołaj (ed.) et al., Foundations of software science and computation structures. 22nd international conference, FOSSACS 2019, held as part of the European joint conferences on theory and practice of software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11425, 62-79 (2019).
Summary: Automata learning is a popular technique for inferring minimal automata through membership and equivalence queries. In this paper, we generalise learning to the theory of coalgebras. The approach relies on the use of logical formulas as tests, based on a dual adjunction between states and logical theories. This allows us to learn, e.g., labelled transition systems, using Hennessy-Milner logic. Our main contribution is an abstract learning algorithm, together with a proof of correctness and termination.
For the entire collection see [Zbl 1408.68009].
For the entire collection see [Zbl 1408.68009].
MSC:
| 68Q32 | Computational learning theory |
| 03B70 | Logic in computer science |
| 68Q45 | Formal languages and automata |
References:
| [1] | Adámek, J.; Lücke, D.; Milius, S., Recursive coalgebras of finitary functors, ITA, 41, 4, 447-462, 2007 · Zbl 1147.18001 |
| [2] | Adámek, J., Milius, S., Moss, L.S., Sousa, L.: Well-pointed coalgebras. Logical Methods Comput. Sci. 9(3) (2013) · Zbl 1272.18002 |
| [3] | Adámek, J.; Rosický, J., Locally Presentable and Accessible Categories, 1994, Cambridge: Cambridge University Press, Cambridge · Zbl 0795.18007 · doi:10.1017/CBO9780511600579 |
| [4] | Angluin, D., Learning regular sets from queries and counterexamples, Inf. Comput., 75, 2, 87-106, 1987 · Zbl 0636.68112 · doi:10.1016/0890-5401(87)90052-6 |
| [5] | Angluin, D., Eisenstat, S., Fisman, D.: Learning regular languages via alternating automata. In: Yang, Q., Wooldridge, M. (eds.) IJCAI 2015, pp. 3308-3314. AAAI Press (2015) |
| [6] | Barlocco, S.; Kupke, C.; Artemov, S.; Nerode, A., Angluin learning via logic, Logical Foundations of Computer Science, 72-90, 2018, Cham: Springer, Cham · Zbl 1503.68083 · doi:10.1007/978-3-319-72056-2_5 |
| [7] | Blackburn, P.; de Rijke, M.; Venema, Y., Modal Logic, 2001, Cambridge: Cambridge University Press, Cambridge · Zbl 0988.03006 · doi:10.1017/CBO9781107050884 |
| [8] | Blok, A.: Interaction, observation and denotation. Master’s thesis, ILLC Amsterdam (2012) |
| [9] | Bollig, B., Habermehl, P., Kern, C., Leucker, M.: Angluin-style learning of NFA. In: Boutilier, C. (ed.) Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI 2009, pp. 1004-1009 (2009) |
| [10] | Borceux, F., Handbook of Categorical Algebra, 1994, Cambridge: Cambridge University Press, Cambridge · Zbl 0803.18001 · doi:10.1017/CBO9780511525872 |
| [11] | van Heerdt, G.: An abstract automata learning framework. Master’s thesis, Radboud Universiteit Nijmegen (2016) |
| [12] | van Heerdt, G., Sammartino, M., Silva, A.: CALF: categorical automata learning framework. In: Goranko, V., Dam, M. (eds.) 26th EACSL Annual Conference on Computer Science Logic, CSL 2017. LIPIcs, vol. 2, pp. 29:1-29:24. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2017) · Zbl 1440.68146 |
| [13] | van Heerdt, G., Sammartino, M., Silva, A.: Learning automata with side-effects. CoRR, abs/1704.08055 (2017) |
| [14] | Jacobs, B., Introduction to Coalgebra: Towards Mathematics of States and Observation, 2016, Cambridge: Cambridge University Press, Cambridge |
| [15] | Jacobs, B.; Silva, A.; van Breugel, F.; Kashefi, E.; Palamidessi, C.; Rutten, J., Automata learning: a categorical perspective, Horizons of the Mind. A Tribute to Prakash Panangaden, 384-406, 2014, Cham: Springer, Cham · Zbl 1407.68235 · doi:10.1007/978-3-319-06880-0_20 |
| [16] | Jacobs, B.; Silva, A.; Sokolova, A., Trace semantics via determinization, J. Comput. Syst. Sci., 81, 5, 859-879, 2015 · Zbl 1327.68158 · doi:10.1016/j.jcss.2014.12.005 |
| [17] | Jacobs, B.; Sokolova, A., Exemplaric expressivity of modal logics, J. Logic Comput., 20, 5, 1041-1068, 2009 · Zbl 1234.03009 · doi:10.1093/logcom/exn093 |
| [18] | Klin, B., Coalgebraic modal logic beyond sets, Electr. Notes Theor. Comput. Sci., 173, 177-201, 2007 · Zbl 1316.03017 · doi:10.1016/j.entcs.2007.02.034 |
| [19] | Klin, B., Rot, J.: Coalgebraic trace semantics via forgetful logics. Logical Methods Comput. Sci. 12(4) (2016) · Zbl 1445.68129 |
| [20] | Kupke, C.; Kurz, A.; Pattinson, D., Algebraic semantics for coalgebraic logics, Electr. Notes Theor. Comput. Sci., 106, 219-241, 2004 · Zbl 1271.03031 · doi:10.1016/j.entcs.2004.02.037 |
| [21] | Kupke, C.; Pattinson, D., Coalgebraic semantics of modal logics: an overview, Theor. Comput. Sci., 412, 38, 5070-5094, 2011 · Zbl 1360.03068 · doi:10.1016/j.tcs.2011.04.023 |
| [22] | Maler, O.; Pnueli, A., On the learnability of infinitary regular sets, Inf. Comput., 118, 2, 316-326, 1995 · Zbl 0834.68099 · doi:10.1006/inco.1995.1070 |
| [23] | Osius, G., Categorical set theory: a characterization of the category of sets, J. Pure Appl. Algebra, 4, 1, 79-119, 1974 · Zbl 0282.02027 · doi:10.1016/0022-4049(74)90032-2 |
| [24] | Pavlovic, D.; Mislove, M.; Worrell, JB; Johnson, M.; Vene, V., Testing semantics: connecting processes and process logics, Algebraic Methodology and Software Technology, 308-322, 2006, Heidelberg: Springer, Heidelberg · Zbl 1236.68065 · doi:10.1007/11784180_24 |
| [25] | Rutten, JJMM; Sangiorgi, D.; de Simone, R., Automata and coinduction (an exercise in coalgebra), CONCUR’98 Concurrency Theory, 194-218, 1998, Heidelberg: Springer, Heidelberg · Zbl 0940.68085 · doi:10.1007/BFb0055624 |
| [26] | Rutten, JJMM, Universal coalgebra: a theory of systems, Theor. Comput. Sci., 249, 1, 3-80, 2000 · Zbl 0951.68038 · doi:10.1016/S0304-3975(00)00056-6 |
| [27] | Schröder, L., Expressivity of coalgebraic modal logic: the limits and beyond, Theor. Comput. Sci., 390, 2-3, 230-247, 2008 · Zbl 1132.03008 · doi:10.1016/j.tcs.2007.09.023 |
| [28] | Taylor, P., Practical Foundations of Mathematics, 1999, Cambridge: Cambridge University Press, Cambridge · Zbl 0939.18001 |
| [29] | Trnková, V., On descriptive classification of set-functors. I, Comment. Math. Univ. Carolinae, 12, 1, 143-174, 1971 · Zbl 0232.18004 |
| [30] | Vaandrager, FW, Model learning, Commun. ACM, 60, 2, 86-95, 2017 · doi:10.1145/2967606 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
