From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/1114 Path: news.gmane.org!not-for-mail From: Luca Cattani Newsgroups: gmane.science.mathematics.categories Subject: Weak Bisimulation and Open Maps Date: Thu, 06 May 1999 12:54:46 +0100 Message-ID: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1241017575 29565 80.91.229.2 (29 Apr 2009 15:06:15 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 15:06:15 +0000 (UTC) Cc: Luca.Cattani@cl.cam.ac.uk, gwinskel@brics.dk, marcelo@cogs.susx.ac.uk To: categories@mta.ca, concurrency@cwi.nl Original-X-From: cat-dist Thu May 6 23:34:11 1999 Original-Received: (from Majordom@localhost) by mailserv.mta.ca (8.9.3/8.9.3) id WAA09211 for categories-list; Thu, 6 May 1999 22:54:59 -0300 (ADT) X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f X-Mailer: exmh version 2.0.2+CL 2/24/98 Original-Sender: cat-dist@mta.ca Precedence: bulk Original-Lines: 51 Xref: news.gmane.org gmane.science.mathematics.categories:1114 Archived-At: 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 -----------------------------------------------------------