Models for Name-Passing Processes: Interleaving and Causal

Gian Luca Cattani and Peter Sewell

Technical Report 505, Cambridge University Computer Laboratory, September 2000. Submitted for publication.

Available electronically as gzipped postscript (189k), dvi (228k), pdf (468k) and in hard copy by emailing tech-reports@cl.cam.ac.uk

This is a revised and extended version of Models for Name-Passing Processes: Interleaving and Causal (Extended Abstract)

Abstract

We study syntax-free models for name-passing processes. For interleaving semantics, we identify the indexing structure required of an early labelled transition system to support the usual pi-calculus operations, defining Indexed Labelled Transition Systems. For non-interleaving causal semantics we define Indexed Labelled Asynchronus Transition Systems, smoothly generalizing both our interleaving model and the standard Asynchronous Transition Systems model for CCS-like calculi. In each case we relate a denotational semantics to an operational view, for bisimulation and causal bisimulation respectively. We establish completeness properties of, and adjunctions between, categories of the two models. Alternative indexing structures and possible applications are also discussed. These are first steps towards a uniform understanding of the semantics and operations of name-passing calculi.

@techreport{cattani/sewell:modnppictr,
  author =       {Cattani, Gian Luca and Sewell, Peter},
  title =        {Models for Name-Passing Processes: Interleaving and Causal},
  institution =  {Computer Laboratory, University of Cambridge}
  number =       {505}
  year =         {2000},
  month =        {sep},  
  note =         {Submitted}
}