Path Category for Free: Open Morphisms from Coalgebras with Non-deterministic Branching

Wißmann T, Dubut J, Katsumata Sy, Hasuo I (2019)


Publication Type: Conference contribution

Publication year: 2019

Journal

Publisher: Springer Verlag

Book Volume: 11425 LNCS

Pages Range: 523-540

DOI: 10.1007/978-3-030-17127-8_30

Abstract

There are different categorical approaches to variations of transition systems and their bisimulations. One is coalgebra for a functor G, where a bisimulation is defined as a span of G-coalgebra homomorphism. Another one is in terms of path categories and open morphisms, where a bisimulation is defined as a span of open morphisms. This similarity is no coincidence: given a functor G, fulfilling certain conditions, we derive a path-category for pointed G-coalgebras and lax homomorphisms, such that the open morphisms turn out to be precisely the G-coalgebra homomorphisms. The above construction provides path-categories and trace semantics for free for different flavours of transition systems: (1) non-deterministic tree automata (2) regular nondeterministic nominal automata (RNNA), an expressive automata notion living in nominal sets (3) multisorted transition systems. This last instance relates to Lasota’s construction, which is in the converse direction.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Wißmann, T., Dubut, J., Katsumata, S.y., & Hasuo, I. (2019). Path Category for Free: Open Morphisms from Coalgebras with Non-deterministic Branching. In Mikolaj Bojanczyk, Alex Simpson (Eds.), Proceedings of the 22nd International Conference, FOSSACS 2019 (pp. 523-540). Springer Verlag.

MLA:

Wißmann, Thorsten, et al. "Path Category for Free: Open Morphisms from Coalgebras with Non-deterministic Branching." Proceedings of the 22nd International Conference, FOSSACS 2019 Ed. Mikolaj Bojanczyk, Alex Simpson, Springer Verlag, 2019. 523-540.

BibTeX: Download