Open maps in concrete categories and branching bisimulation for prefix orders

H. Beohar, P.J.L. Cuijpers

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
99 Downloads (Pure)

Abstract

Open maps, as introduced in concurrency theory by Joyal, Nielsen and Winskel, provide an abstract way to define functional bisimulations across a wide variety of models of computation (like labelled transition systems, event structures, etcetera). Furthermore, the existence of a span of open maps characterises the well-known relational definition of bisimulations found in the literature associated with these models of computation. However, in our working category of prefix orders (in which the objects represent the sets of executions generated by arbitrary dynamical systems) the open maps do not immediately result in functional bisimulations and the existence of a span of open maps does not result in an equivalence. This is rather surprising, since prefix orders are mere generalizations of (discrete) execution trees, for which the open map approach is known to work. After taking a closer look at the definition of open map, we show in this paper that the issue can be remedied by considering prefix orders as a concrete category and reinterpreting the definition of open-map in this light. As a bonus, the choice of a path-category on which the notion of open-map relies becomes a natural one, namely the subcategory of embeddings. While the existence of spans still does not result in an equivalence, it is shown that the existence of cospans does. In fact, we present a characterisation of the notion of branching bisimulation by van Glabbeek and Weijland which, to the best of our knowledge, was not studied in the framework of open maps before.

Original languageEnglish
Pages (from-to)51-66
Number of pages16
JournalElectronic Notes in Theoretical Computer Science
Volume319
DOIs
Publication statusPublished - 21 Dec 2015
Event31st Conference on the Mathematical Foundations of Programming Semantics (MFPS 2015) - Nijmegen, Netherlands
Duration: 22 Jun 201525 Jun 2015
Conference number: 31

Keywords

  • Branching bisimulation
  • Concrete categories
  • Open maps
  • Prefix orders

Fingerprint Dive into the research topics of 'Open maps in concrete categories and branching bisimulation for prefix orders'. Together they form a unique fingerprint.

Cite this