Leading examples of process calculi include CSP, CCS, ACP, and LOTOS.
While the variety of existing process calculi is very large (including variants that incorporate stochastic behaviour, timing information, and specializations for studying molecular interactions), there are several features that all process calculi have in common:[2] To define a process calculus, one starts with a set of names (or channels) whose purpose is to provide means of communication.
In many implementations, channels have rich internal structure to improve efficiency, but this is abstracted away in most theoretic models.
The basic operators, always present in some form or other, allow:[3] Parallel composition of two processes
, is the key primitive distinguishing the process calculi from sequential models of computation.
Some process calculi also allow channels to be created during the execution of a computation.
Process calculi that make such distinctions typically define an input operator (e.g.
The choice of the kind of data that can be exchanged in an interaction is one of the key features that distinguishes different process calculi.
In process calculi, the sequentialisation operator is usually integrated with input or output, or both.
The key operational reduction rule, containing the computational essence of process calculi, can be given solely in terms of parallel composition, sequentialization, input, and output.
The details of this reduction vary among the calculi, but the essence remains roughly the same.
is allowed to range over as the continuation of the output operation substantially influences the properties of the calculus.
Processes do not limit the number of connections that can be made at a given interaction point.
For the synthesis of compact, minimal and compositional systems, the ability to restrict interference is crucial.
Hiding operations allow control of the connections made between interaction points when composing agents in parallel.
The operations presented so far describe only finite interaction and are consequently insufficient for full computability, which includes non-terminating behaviour.
Recursion and replication are operations that allow finite descriptions of infinite behaviour.
can be understood as abbreviating the parallel composition of a countably infinite number of
It is utterly inactive and its sole purpose is to act as the inductive anchor on top of which more interesting processes can be generated.
[4] In the first half of the 20th century, various formalisms were proposed to capture the informal concept of a computable function, with μ-recursive functions, Turing machines and the lambda calculus possibly being the best-known examples today.
The surprising fact that they are essentially equivalent, in the sense that they are all encodable into each other, supports the Church-Turing thesis.
Another shared feature is more rarely commented on: they all are most readily understood as models of sequential computation.
Research on process calculi began in earnest with Robin Milner's seminal work on the Calculus of Communicating Systems (CCS) during the period from 1973 to 1980.
In 1982 Jan Bergstra and Jan Willem Klop began work on what came to be known as the Algebra of Communicating Processes (ACP), and introduced the term process algebra to describe their work.
Various process calculi have been studied and not all of them fit the paradigm sketched here.
This is to be expected as process calculi are an active field of study.
The ideas behind process algebra have given rise to several tools including: The history monoid is the free object that is generically able to represent the histories of individual communicating processes.
A process calculus is then a formal language imposed on a history monoid in a consistent fashion.
[6] That is, a history monoid can only record a sequence of events, with synchronization, but does not specify the allowed state transitions.
Thus, a process calculus is to a history monoid what a formal language is to a free monoid (a formal language is a subset of the set of all possible finite-length strings of an alphabet generated by the Kleene star).