TL;DR
This paper introduces a revised operational semantics for sequential composition in process calculi to address issues of unbounded branching and "forgetfulness" that arise when processes can terminate mid-execution. This new semantics enables a tighter correspondence between context-free processes and pushdown automata, and proves the reactive Turing powerfulness of a process calculus with iteration and nesting.
What Problem Does This Paper Address?
Process calculi are powerful tools for modeling concurrent systems. A fundamental operation is sequential composition (P·Q), which means process P executes, and upon its completion, process Q begins. However, when processes can terminate successfully before completing all their intended actions (intermediate termination), this leads to complications.
The standard semantics of sequential composition exhibits "transparency." If process P can terminate, then P·Q can also terminate immediately if Q can terminate, even if P still has other actions it could perform. This transparency causes two main problems:
- Unbounded Branching: It can lead to transition systems with an unbounded number of branches from a single state, which is problematic for relating these systems to pushdown automata (which inherently have bounded branching).
- Forgetfulness: It makes it difficult to specify certain computational structures, like a counter that always terminates without losing its state, because intermediate transparent processes can be "skipped" or "forgotten."
These issues hinder the smooth integration of process theory with classical automata theory and formal languages, particularly when trying to establish equivalences like bisimilarity.
Methods
The core contribution of this paper is a revised operational semantics for sequential composition. The key change is a negative premise in the rules: a transition in the second component of a sequential composition (P·Q) is disallowed if the first component (P) can perform any transition. This effectively prevents the "skipping" of P's behavior due to its ability to terminate.
The authors then use this revised semantics to:
- Eliminate unbounded branching: They show that with the new semantics, context-free processes (which can exhibit unbounded branching with the old semantics) now correspond to pushdown processes (which are inherently boundedly branching).
- Establish reactive Turing powerfulness: They demonstrate that a process calculus extended with iteration and nesting, using the revised semantics, is reactively Turing powerful. This means it can model the behavior of any reactive Turing machine.
They also introduce and utilize various notions of behavioral equivalence, including strong bisimilarity, branching bisimilarity, and divergence-preserving branching bisimilarity, to formalize their results.
Datasets
Not discussed in the paper. The paper focuses on theoretical aspects of process calculi and automata theory, not empirical evaluation on specific datasets.
Key Insights and Ideas
- Transparency is the culprit: The paper clearly identifies "transparency" in sequential composition with intermediate termination as the root cause of issues like unbounded branching and forgetfulness.
- Negative premises are powerful: Introducing a negative premise (disallowing a transition if another is possible) in the operational semantics of sequential composition is a surprisingly effective way to resolve these fundamental problems.
- Bridging the gap: The revised semantics successfully bridges the gap between context-free processes and pushdown automata, a long-standing challenge in the field.
- Enabling richer computation: The new semantics allows for the specification of more complex computational structures, like always-terminating counters, which were previously difficult or impossible to model accurately.
Key Results
- Elimination of Unbounded Branching: The revised semantics ensures that processes that were previously unbounded in their branching behavior (like the example
X = a.XY + b.1withY = c.1+1) now exhibit bounded branching. This allows for a strong correspondence (bisimilarity) between context-free processes and pushdown processes. - Reactive Turing Powerfulness: The process calculus TCP, when extended with iteration and nesting and using the revised sequential composition, is proven to be reactively Turing powerful modulo divergence-preserving branching bisimilarity. This is a significant result for the expressiveness of process calculi.
- Specification of Always-Terminating Structures: The paper demonstrates how to specify an always-terminating half-counter using the revised semantics, which was not feasible with the original semantics.
Limitations and Future Work
- Negative Premises Complications: The authors acknowledge that negative premises in operational semantics can lead to formal complications, particularly in proving whether a process admits a transition. They illustrate this with an example of an unguarded recursive specification.
- Congruence Issues: Rooted branching bisimilarity is not a congruence with the new sequential composition operator; divergence-preserving branching bisimilarity is required for this property.
- Equational Theory: The paper suggests that a finite, sound, and ground-complete set of equational axioms for the process calculus TCP with respect to strong bisimilarity might not exist due to the nature of the revised sequential composition. Further investigation into the equational theory is suggested.
- Other Process Calculi: The authors propose exploring the reactive Turing powerfulness of other process calculi that use non-regular iterators, such as the pushdown operator "$" and the back-and-forth operator "S", with the revised semantics.
- Generalizing Counters: They also aim to use the revised semantics to define other versions of terminating counters and establish their reactive Turing powerfulness.
Summary updated