Action Structures

Robin Milner

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 two other ingredients: 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; however, the work is presented algebraically rather than in category theory.

The notion of action structure is developed mathematically, and examples are studied ranging from the evaluation of expressions to the statics 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. This allows a common treatment of bisimulation congruence.

The theory of action structures emphasizes the notion of effect; that is, the effect which any interaction among processes exerts upon its participants. Effects are degenerate actions, and constitute a sub-actionstructure with special properties which support the general treatment of bisimulation.

Other current work on action structures is outlined, in particular their use for the pi-calculus. Challenges are posed for the algebraic theory, including the study of combinations of action structures. Action structures are briefly compared with some other general models.

LFCS report ECS-LFCS-92-249, December 1992.

Previous | Index | Next