Weak Bisimulation and Open Maps

[Luca Cattani <Luca.Cattani@cl.cam.ac.uk>]

The following paper, to be presented at LICS '99, is available from my home 
page:

    
               http://www.cl.cam.ac.uk/~glc25/weabom.html .




                        Weak Bisimulation and Open Maps

     Marcelo Fiore             Gian Luca Cattani            Glynn Winskel
         COGS                 Computer Laboratory               BRICS
   Univ. Sussex, UK           Univ. Cambridge, UK          Univ. Aarhus, DK 


                                   Abstract

A systematic treatment of weak bisimulation and observational congruence on
presheaf models is presented.  The theory is developed with respect to a
``hiding'' functor from a category of paths to observable paths.  Via a view
of processes as bundles, we are able to account for weak morphisms (roughly
only required to preserve observable paths) and to derive a saturation monad
(on the category of presheaves over the category of paths).  Weak morphisms
may be encoded as strong ones via the Kleisli construction associated to the
saturation monad.  A general notion of weak open-map bisimulation is
introduced, and results relating various notions of strong and weak
bisimulation are provided.  The abstract theory is accompanied by the concrete
study of two key models for concurrency, the interleaving model of
synchronisation trees and the independence model of labelled event structures.


Comments are welcome.

Luca

-- 
-----------------------------------------------------------
Gian Luca Cattani          Phone: +44 (0)1223 334697
Cambridge University       Fax:   +44 (0)1223 334678
Computer Laboratory,       email: Luca.Cattani@cl.cam.ac.uk
New Museums Site,
Pembroke Street,
CB2 3QG, Cambridge, 
United Kingdom
-----------------------------------------------------------