Bicategories of Automata, Automata in Bicategories

Guido Boccali
(University of Torino)
Andrea Laretto
(Tallinn University of Technology)
Fosco Loregian
(Tallinn University of Technology)
Stefano Luneia
(University of Bologna)

We study bicategories of (deterministic) automata, drawing from prior work of Katis-Sabadini-Walters, and Di Lavore-Gianola-Román-Sabadini-Sobociński, and linking their bicategories of `processes' to a bicategory of Mealy machines constructed in 1974 by R. Guitart. We make clear the sense in which Guitart's bicategory retains information about automata, proving that Mealy machines á la Guitart identify to certain Mealy machines á la K-S-W that we call fugal automata; there is a biadjunction between fugal automata and the bicategory of K-S-W. Then, we take seriously the motto that a monoidal category is just a one-object bicategory. We define categories of Mealy and Moore machines inside a bicategory B; we specialise this to various choices of B, like categories, relations, and profunctors. Interestingly enough, this approach gives a way to interpret the universal property of reachability as a Kan extension and leads to a new notion of 1- and 2-cell between Mealy and Moore automata, that we call intertwiners, related to the universal property of K-S-W bicategory.

In Sam Staton and Christina Vasilakopoulou: Proceedings of the Sixth International Conference on Applied Category Theory 2023 (ACT 2023), University of Maryland, 31 July - 4 August 2023, Electronic Proceedings in Theoretical Computer Science 397, pp. 1–19.
Published: 14th December 2023.

ArXived at: bibtex PDF

Comments and questions to:
For website issues: