Path Category for Free - Archive ouverte HAL Access content directly
Conference Papers Year : 2019

Path Category for Free

(1) , (2, 3) , (2) , (2, 4)


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.

Dates and versions

hal-02374914 , version 1 (21-11-2019)



Thorsten Wissmann, 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⟩
23 View
0 Download



Gmail Facebook Twitter LinkedIn More