Finitie Coalgebras in Minimization and Recursion
Final Report Abstract
Syntactic Monoids in a Category. State-based systems are often described via their input-output behaviors. In the algebraic theory of languages one associates such behaviors with suitable algebraic structures in order to characterize the given systems by algebraic properties. For instance, the behaviors of finite automata, the regular languages, are precisely the languages recognized by finite monoids. The minimal monoid recognizing a given language is called its syntactic monoid. Several alternative notions of algebraic recognition have been studied in the literature using, e.g., ordered monoids (corresponding to ordered automata) or algebras over a field (corresponding to linear weighted automata). In each case, a different construction of a syntactic algebra has been presented. Our paper unifies all these results and finds new such situations by studying D-automata and their languages for a closed monoidal category D and introducing the concept of a syntactic D-monoid for a language. The paper received the “Best Paper Award” of the conference Coalgebraic and Algebraic Methods in Computer Science (CALCO) 2015. Varieties of Languages. An important result of Eilenberg from the 1970’s is the bijective correspondence between pseudovarieties of monoids (i.e. classes of finite monoids closed under finite products, submonoids, and quotients) and varieties of regular languages. In the past four decades more than 20 generalization of this result have been published in which the underlying systems (which, for regular languages, are finite automata) are generalized to tree automata, weighted automata, Büchi automata, etc. In each case, a bijection between varieties of languages accepted by finite systems and pseudovarieties of finite algebraic structures is established. In a series of papers we have introduced a technique, based on a study of dually equivalent pairs of categories of finite algebras, which enabled a unified proof of all these results and opened new directions of research in this area. One paper received the “Best Paper Award” of the conference Mathematical Foundations of Computer Science (MFCS) 2017. Continuous Nondeterminism and State-Minimality. State minimization of nondeterministic finite automata (NFAs) is PSPACE-complete. Several canonical (but not necessarily state-minimal) nondeterministic acceptors for a given regular language were proposed in the literature, e.g. the átomaton of Brzozowski and Tamm or the minimal xor automaton of Vuillemin and Gama. We demonstrated that all these constructions have a joint core: to form a canonical NFA for a language, one first constructs the minimal deterministic acceptor in a category of finite algebras and then applies an equivalence with a suitable category of structured sets and relations. One instance, the category of finite closure spaces, led us to the notion of a nondeterministic closure automaton (NCA). We showed that every regular language has a unique minimal NCA, which is state-minimal if the underlying closure space is topological. Thus, we identified a natural class of canonical state-minimal nondeterministic acceptors. Finitary Recursion. In earlier work we demonstrated how recursion can be formalized using as recursive equations coalgebras on finitely presentable objects (representing the recursion variables) and studying iterative algebras, where recursive equations have unique solutions. Later various authors have generalized this approach by imposing weaker conditions on the objects of recursion variables. The aim was always to identify the most suitable generalization of the classical iterativity based on finite sets of variables. We have presented a general approach where the notion of “finiteness” becomes a parameter of the categorical setting. This covers not only the different flavors of iterativity studied before, but also yields an interesting new case of recursion with side effects.
Publications
- On continuous nondeterminism and state minimality. In B. Jacobs, A. Silva, and S. Staton, editors, Proc. 30th Conference on the Mathematical Foundations of Programming Science (MFPS’14), volume 308 of Electron. Notes Theor. Comput. Sci., pages 3–23. Elsevier, 2014
J. Adámek, S. Milius, R. Myers, and H. Urbat
(See online at https://doi.org/10.1016/j.entcs.2014.10.002) - Syntactic monoids in a category. In L. S. Moss and P. Sobocinsky, editors, Proc. 6th Conference on Algebra and Coalgebra in Computer Science (CALCO’15), LIPIcs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015. Best Paper Award
J. Adámek, S. Milius, and H. Urbat
- Varieties of languages in a category. In C. Palamidessi, editor, Proc. 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’15), pages 414–425. IEEE, 2015
J. Adámek, R. Myers, S. Milius, and H. Urbat
(See online at https://doi.org/10.1109/LICS.2015.46) - Profinite monads, profinite equations and Reiterman’s theorem. In B. Jacobs and C. Löding, editors, Proc. 19th International Conference on Foundations of Software Science and Computation Structures (FOSSACS’16), volume 9634 of LNCS, pages 531–547. Springer, 2016
L.-T. Chen, J. Adámek, S. Milius, and H. Urbat
(See online at https://doi.org/10.1007/978-3-662-49630-5_31) - Eilenberg theorems for free. In H. Bodlander, K. Larsen, and J.-F. Raskin, editors, Proc. 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS’17), LIPIcs, pages 43:1–43:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017. EATCS Best Paper Award
H. Urbat, J. Adámek, L.-T. Chen, and S. Milius
(See online at https://dx.doi.org/10.4230/LIPIcs.MFCS.2017.43) - Finite behaviours and finitary corecursion. In F. Bonchi and B. König, editors, Proc. 7th Conference on Algebra and Coalgebra in Computer Science (CALCO’17), Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1–24:15, 2017
H. Urbat
(See online at https://dx.doi.org/10.4230/LIPIcs.CALCO.2017.24)
