Path Category for Free - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Path Category for Free

Résumé

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 et versions

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

Identifiants

Citer

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⟩
27 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More