Calculi for Interaction

Robin Milner

Research output: Contribution to journalArticlepeer-review

Abstract

Action structures have previously been proposed as an algebra for both the syntax and the semantics of interactive computation. Here, a class of concrete action structures calledaction calculi is identified, which can serve as a non-linear syntax for a wide variety of models of interactive behaviour. Each action in an action calculus is represented as an assembly ofmolecules; the syntactic binding ofnames is the means by which molecules are bound together. A graphical form,action graphs, is used to aid presentation. One action calculus differs from another only in its generators, calledcontrols.

Action calculi generalise a previously defined action structure PIC for the π- calculus. Several extensions to PIC are given as action calculi, giving essentially the same power as the π-calculus. An action calculus is also given for the typed λ-calculus, and for Petri nets parametrized on their places and transitions.

An equational characterization of action calculi is given: each action calculusA is the quotient of a term algebra by certain equations. The terms are generated by a set of operators, including those basic to all action structures as well as the controls specific toA; the equations are the basic axioms of action structures together with four additional axiom schemata.
Original languageEnglish
Pages (from-to)707-737
Number of pages31
JournalActa Informatica
Volume33
Issue number8
DOIs
Publication statusPublished - 1996

Fingerprint

Dive into the research topics of 'Calculi for Interaction'. Together they form a unique fingerprint.

Cite this