Can choice or sequential execution be expressed with other basic operators of the pi calculus?

Question

There are several definitions of what basic operators constitute the pi calculus (see papers from R. Milner, B.Pierce, J.Wing).

The common basic operators ($C$) are:

• the parallel composition
• reading from a named channel
• writing to a named channel
• restriction to get a new named channel
• replication to get an infinite number of parallel copies of a process
• the inert process that does nothing.

Sometimes, there is additionally one of the following two operator mentioned as basic operator:

• the sequential operator for sequential execution;
• the summation operator to choose between processes.

Is $C$ together with the sequential operator equivalent to $C$ with the summation operator? Are they even equivalent to $C$ without any further operator? Why (not)?

Answer 1

This is a really interesting question and only partially understood. The $ \newcommand{\OUT}[2]{\overline{#1} #2 } $ precise answer to such questions depends in subtle ways on exactly what the ambient $\pi$-calculus is and exactly what feature you are encoding.

For sums you need to realise that there are different kinds of sums for example input guarded sums like $x(v).P + x(v).Q$ or $x(v).P + y(v).Q$, or mixed sums like $x(v).P + \OUT{y}{v}.Q$ or even $x(v).P + \OUT{y}{v}.Q + \tau.R$. What you can and cannot encode really depends on what sums you have. The groundbreaking study (1) gives hard limits to 'good' encodings. Simplifying greatly, what (1) shows is that adding mixed sums to a calculus strictly increases expressivity. This it cannot be encoded (in a nice way). The reason is that mixed sums allow a certain form of symmetry breaking that is not achievable in conventional $\pi$-calculi without mixed choice.

With sequential composition $P; Q$ the situation is less complicated, but you need to be clear exactly what sequential means for parallel processes and replication/recursion:

• Should $R$ begin to execute when one or both of $P$ and $Q$ terminate in $(P|Q); R$?

• What is the meaning of $(!x(v).P); R$?

If $(P|Q); R$ means that both $P$ and $Q$ must terminate before $R$ goes to work, and if we disallow sequential composition like $(!x(v).P); R$ with replication, then $P; Q$ is easily encodable, and by (1) it cannot simulate general forms of sums that include mixed sums.

The curse of Turing completeness. There is a further complication. Process calculi typically are Turing-complete, hence any feature can be 'somehow' be encoded. So you need to be very precise about what you mean when you ask if some calculus is "equivalent" to some other. The usual approach to making this precise is to constrain admissible encodings, e.g. to require them to be compositional, or preserve termination, or be closed under renaming, or any number of other interesting structural properties. For different concepts of admissible encoding you tend to get different answers. None of this is germane to process calculi, Turing's curse affects all programming languages, but process calculi are especially subtle, since they can do so much more than mere sequential computation.

For an overview of the state-of-the art in process calculus expressivity, see (2, 3).

---

(1) C. Palamidessi, Comparing the Expressive Power of the Synchronous and the Asynchronous π-Calculi.

(2) D. Gorla, Comparing Communication Primitives via their Relative Expressive Power.

(3) D. Gorla, A Taxonomy of Process Calculi for Distribution and Mobility.