Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadata

https://hal.inria.fr/hal-02374914
Contributor : Jérémy Dubut <>
Submitted on : Thursday, November 21, 2019 - 5:31:15 PM
Last modification on : Monday, May 17, 2021 - 12:00:05 PM

Links full text

Identifiers

Citation

Thorsten Wißmann, Jérémy Dubut, Shin-Ya Katsumata, Ichiro Hasuo. Path Category for Free: Open Morphisms from Coalgebras with Non-deterministic Branching. Foundations of Software Science and Computation Structures - 22nd International Conference, FOSSACS 2019, Apr 2019, Prague, Czech Republic. pp.523-540, ⟨10.1007/978-3-030-17127-8_30⟩. ⟨hal-02374914⟩

Share

Metrics

Record views

51