Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-25T03:28:54.013Z Has data issue: false hasContentIssue false

Transition systems, link graphs and Petri nets

Published online by Cambridge University Press:  06 December 2006

JAMES J. LEIFER
Affiliation:
INRIA, Domaine de Voluceau, BP 105, 78153 Le Chesnay Cedex, France Email: [email protected]
ROBIN MILNER
Affiliation:
University of Cambridge, Computer Laboratory, JJ Thomson Avenue, Cambridge CB3 0FD, U.K.

Abstract

A framework is defined within which reactive systems can be studied formally. The framework is based on s-categories, which are a new variety of categories within which reactive systems can be set up in such a way that labelled transition systems can be uniformly extracted. These lead in turn to behavioural preorders and equivalences, such as the failures preorder (treated elsewhere) and bisimilarity, which are guaranteed to be congruential. The theory rests on the notion of relative pushout, which was previously introduced by the authors.

The framework is applied to a particular graphical model, known as link graphs, which encompasses a variety of calculi for mobile distributed processes. The specific theory of link graphs is developed. It is then applied to an established calculus, namely condition-event Petri nets.

In particular, a labelled transition system is derived for condition-event nets, corresponding to a natural notion of observable actions in Petri-net theory. The transition system yields a congruential bisimilarity coinciding with one derived directly from the observable actions. This yields a calibration of the general theory of reactive systems and link graphs against known specific theories.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)