Higher-Order Action Calculi

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 HAC( 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.

Authors

• Robin Milner

Keywords

No keywords are indexed for this paper.