Action Structures and the Pi Calculus

Robin Milner

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Action structures are proposed as a variety of algebra to underlie concrete models of concurrency and interaction. An action structure is equipped with composition and product of actions, together with an indexed family of abstractors to allow parametrisation of actions, and a reaction relation to represent activity. The eight axioms of an action structure make it an enriched strict monoidal category.
In Part I the notion of action structure is developed mathematically, and examples are studied ranging from the evaluation of expressions to the static s and dynamics of Petri nets. For algebraic process calculi in particular, it is shown how they may be defined by a uniform superposition of process structure upon an action structure specific to each calculus.
The theory of action structures emphasizes the notion of effect; that is, the effect which any interaction among processes exerts upon its participants. Effects together with incidents (roughly speaking, observable actions) allow a uniform treatment of bisimulation congruence.
In Part II, the π-calculus is treated as an extended example of this uniform process theory. Three action structures for the π-calculus are examined; they are presented in a simple graphical form. The incidents for π-calculus are best characterized in terms of reachability, a graphical notion. This leads to a bisimulation congruence for the synchronous π-calculus, in which individual transitions may involve actions of arbitrary complexity.
Original languageUndefined/Unknown
Title of host publicationProof and Computation
Subtitle of host publicationNATO ASI Series
EditorsHelmut Schwichtenberg
PublisherSpringer Berlin Heidelberg
Pages317-377
Number of pages61
Volume139
ISBN (Electronic)978-3-642-79361-5
ISBN (Print)978-3-642-79363-9
DOIs
Publication statusPublished - 1995

Publication series

NameNATO ASI Series
PublisherSpringer Berlin Heidelberg

Keywords

  • abstractor
  • action
  • action structure
  • bisimulation
  • concurrency
  • effect
  • incident
  • interaction
  • monoidal category
  • process structure
  • pi-calculus
  • reaction relation
  • transition

Cite this