License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2016.25
URN: urn:nbn:de:0030-drops-61555
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6155/
Go to the corresponding LIPIcs Volume Portal

Dubut, Jérémy ; Goubault, Eric ; Goubault-Larrecq, Jean

Bisimulations and Unfolding in P-Accessible Categorical Models

pdf-format:
LIPIcs-CONCUR-2016-25.pdf (0.4 MB)

Abstract

In this paper, we propose a categorical framework for bisimulations and unfoldings that unifies the classical approach from Joyal and al. via open maps and unfoldings. This is based on a notion of categories accessible with respect to a subcategory of path shapes, i.e., for which one can define a nice notion of trees as glueing of paths. We prove that transitions systems and pre sheaf models are a particular case of our framework. We also prove that in our framework, several characterizations of bisimulation coincide, in particular an "operational one" akin to the standard definition in transition systems. Also, accessibility is preserved by coreflexions. We then design a notion of unfolding, which has good properties in the accessible case: its is a right adjoint and is a universal covering, i.e., initial among the morphisms that have the unique lifting property with respect to path shapes. As an application, we prove that the universal covering of a groupoid, a standard construction in algebraic topology, coincides with an unfolding, when the category of path shapes is well chosen.

BibTeX - Entry

@InProceedings{dubut_et_al:LIPIcs:2016:6155,
  author =	{J{\'e}r{\'e}my Dubut and Eric Goubault and Jean Goubault-Larrecq},
  title =	{{Bisimulations and Unfolding in P-Accessible Categorical Models}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Jos{\'e}e Desharnais and Radha Jagadeesan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6155},
  URN =		{urn:nbn:de:0030-drops-61555},
  doi =		{10.4230/LIPIcs.CONCUR.2016.25},
  annote =	{Keywords: categorical models, bisimulation, coreflexions, unfolding, universal covering}
}

Keywords: categorical models, bisimulation, coreflexions, unfolding, universal covering
Collection: 27th International Conference on Concurrency Theory (CONCUR 2016)
Issue Date: 2016
Date of publication: 24.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI