ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Eighth Annual IEEE Symposium on

Logic in Computer Science (LICS 1993)

Paper: Bisimulation and open maps (at LICS 1993)

Winner of the Test-of-Time Award in 2013
Authors: André Joyal Mogens Nielsen Glynn Winskel


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


    author = 	 {André Joyal and Mogens Nielsen and Glynn Winskel},
    title = 	 {Bisimulation and open maps},
    booktitle =  {Proceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science (LICS 1993)},
    year =	 {1993},
    month =	 {June}, 
    pages =      {418--427},
    location =   {Montreal, Canada}, 
    publisher =	 {IEEE Computer Society Press}

Last modified: 2022-10-3113:49
Sam Staton