Bisimulation and open maps
- 31 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 418-427
- https://doi.org/10.1109/lics.1993.287566
Abstract
An abstract definition of bisimulation is presented. It allows a uniform definition of bisimulation across a range of different models for parallel computation presented as categories. As examples, transition systems, synchronization trees, transition systems with independence (an abstraction from Petri nets), and labeled event structures are considered. On transition systems, the abstract definition readily specialises to Milner's (1989) strong bisimulation. On event structures, it explains and leads to a revision of the history-preserving bisimulation of Rabinovitch and Traktenbrot (1988), and Goltz and van Glabeek (1989). A tie-up with open maps in a (pre)topos brings to light a promising new model, presheaves on categories of pomsets, into which the usual category of labeled event structures embeds fully and faithfully. As an indication of its promise, this new presheaf model has refinement operators, though further work is required to justify their appropriateness and understand their relation to previous attempts.<>Keywords
This publication has 6 references indexed in Scilit:
- Refinement of actions and equivalence notions for concurrent systemsActa Informatica, 2001
- Bisimulation of automataInformation and Computation, 1988
- Behavior Structures and NetsFundamenta Informaticae, 1988
- Bisimulations and abstraction homomorphismsPublished by Springer Nature ,1985
- Correspondence TheoryPublished by Springer Nature ,1984
- A Calculus of Communicating SystemsLecture Notes in Computer Science, 1980