π-calculus
Sign in to saveAlso known as pi-calculus
In theoretical computer science, the -calculus (or pi-calculus) is a process calculus. The -calculus allows channel names to be communicated along the channels themselves, and in this matter, it is able to describe concurrent computations whose network configuration may change during the computation.
~22 min read
Article
21 sectionsContents
- Informal definition
- Process constructs
- A small example
- Formal definition
- Syntax
- Structural congruence
- Reduction semantics
- The example revisited
- Labelled semantics
- Extensions and variants
- Properties
- Turing completeness
- Bisimulations in the {{pi}}-calculus
- Early and late bisimilarity
- Open bisimilarity
- Early, late and open bisimilarity are distinct
- Barbed equivalence
- History
- Implementations
- Notes
- References
In theoretical computer science, the -calculus (or pi-calculus) is a process calculus. The -calculus allows channel names to be communicated along the channels themselves, and in this matter, it is able to describe concurrent computations whose network configuration may change during the computation.
The -calculus has few terms and is a small, yet expressive language (see ). Functional programs can be encoded into the -calculus, and the encoding emphasises the dialogue nature of computation, drawing connections with game semantics. Extensions of the -calculus, such as the spi calculus and applied , have been successful in reasoning about cryptographic protocols. Beside the original use in describing concurrent systems, the -calculus has also been used to reason through business processes, molecular biology. and autonomous agents in artificial intelligence.