Higher-Order Action Calculi

Robin Milner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Action calculi are a broad class of algebraic structures, including a formulation of Petri nets as well as a formulation of the π-calculus. Each action calculus HA (K) is generated by a particular set K of operators called controls. The purpose of this paper is to extend action calculi in a uniform manner to higher-order. A special case is essentially the extension of the π-calculus to higher order by Sangiorgi. To establish a link between the interactive and functional paradigms of computation, a variety of the λ-calculus is obtained as the extension of the smallest action calculus HAC(θ).

The dynamics of higher-order action calculi is presented, blending communication -for example in process calculi- with reduction as in the λ calculus. Strong normalisation is obtained for reduction. A set of equational axioms is given for higher-order action calculi. Taking the quotient of HAC(θ) by a single extra axiom η, a cartesian-closed category is obtained.

An ultimate goal of the paper is to combine process calculi and functional calculi, both in their formulation and in their semantics.
Original languageEnglish
Title of host publicationComputer Science Logic
Subtitle of host publication7th Workshop, CSL '93 Swansea, United Kingdom September 13–17, 1993 Selected Papers
Pages238-260
Number of pages23
Volume832
ISBN (Electronic)978-3-540-48599-5
DOIs
Publication statusPublished - 1993

Fingerprint

Dive into the research topics of 'Higher-Order Action Calculi'. Together they form a unique fingerprint.

Cite this