Unique Solutions of Guarded Recursive Equations
Rob van Glabbeek · 2025
Read Unique Solutions of Guarded Recursive Equations by Rob van Glabbeek (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24206.txt.
Introduction
Rob van Glabbeek shows that a guarded set of self referring rules has just one solution, working alone. Process algebras are math tools that describe systems step by step. In these tools, a process can refer to itself. A rule is guarded when each self call sits behind an action. That guard keeps the rules well behaved and stops loose ends.
He proves there is one solution up to a strong match of behavior. The proof holds for any such tool whose rules fit a known format. The same holds for weaker matches and for their order forms. So these match tests stay sound when guarded self calls are added. The result also gives a full, sound set of laws for the strong match in finite cases.
Catalog record
| CREATOR | Rob van Glabbeek |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 118 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-24206
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Unique Solutions of Guarded Recursive Equations Rob van Glabbeek Abstract This paper shows that guarded systems of recursive equations have unique solutions up to strong bisimilarity for any process algebra with a structural operation semantics in the ready simulation format. A similar result holds for simulation equivalence, for ready simulation equivalence and for the (ready) simulation preorder. As a consequence, these equivalences and preorders are full (pre) congruences for guarded recursion. Moreover, the unique-solutions result yields a sound and ground-complete axiomatisation of strong bisimilarity for any finitary GSOS language. 1 Introduction In many process algebras, including CCS [ 31 ] , CSP [ 11 ] and ACP [ 4 ] , infinite processes are specified by systems {\cal S} of recursive equations \{X={\cal S}_{X}\mid X\in V_{\cal S}\} . Such systems are called recursive specifications . Here V_{\cal S} is a set of recursion variables specific to a recursive specification, and each X\in V_{\cal S} is defined to behave as the expression {\cal S}_{X} . Crucially, X itself, and other variables from V_{\cal S} , may occur in the expression {\cal S}_{X} . An important tool in equational reasoning is that a large class of recursive specifications have unique solutions. Here a solution is a tuple \vec{P} of processes, one for each variable X in the set V_{\cal S} , such that filling in the X -component of \vec{P} for X , at both the left- and the right-hand side of the recursive equations in {\cal S} , yields a set of semantically valid statements. Example 1.1 . recursive specification Using the syntax of CCS [ 31 ] , let {\cal S} be the recursive specification consisting of the two recursive equations \{X=a.X+b.Y~,~Y=c.X+d.Y\} . In the model of labelled transition systems [ 31 ] , the pair (P,Q) of states in the labelled transition system depicted below constitutes a solution of {\cal S} . P a Q b c d In fact, this is the only solution of {\cal S} up to strong bisimilarity [ 31 ] . Unfortunately, not all recursive specifications have unique solutions. The recursive equation X=X , for instance, allows any process as a solution. Milner [ 31 ] formulated a syntactic criterion on recursive specifications called guardedness , and showed that in the process algebra CCS, systems of guarded recursive equations have unique solutions up to strong bisimilarity. In the setting of ACP [ 3 , 4 ] two reasoning principles are defined: the Recursive Definition Principle (RDP) states that any recursive specification has a solution, and the Recursive Specification Principle (RSP) states that guarded recursive specifications have at most one solution, up to a semantic equivalence. Whether these principles hold may depend on the process algebra and on the semantic equivalence employed. First of all it takes a semantic equivalence to determine whether a given tuple \vec{P} is a solution of a recursive specification {\cal S} . Secondly, if {\cal S} is guarded and \vec{P} and \vec{Q} both are solutions, RSP demands that \vec{P} and \vec{Q} are semantically equivalent. RDP and RSP are equational and conditional equational laws that can be added as axioms to the equational theories of various process algebras. Doing so has been a crucial step in achieving complete axiomatisations [ 30 , 5 , 13 , 22 ] —see also Section 11 . Subtly different definitions of guardedness appear in the literature. In [ 31 ] it was required that within the bodies {\cal S}_{X} of recursive equations the recursion variables Y\in V_{\cal S} may appear only within the scope of a CCS action prefixing operator a.\_ . Here this action guards the recursion variable. In Example , {\cal S} is guarded in this sense. In other process algebras one might allow other operators as guards. In ACP [ 4 ] for instance, the left merge \mathbin{\lfloor\hskip-3.0pt\lfloor} is a good candidate. However, it guards only its second argument: the recursive specification X=b\mathbin{\lfloor\hskip-3.0pt\lfloor}X is guarded, but Y=Y\mathbin{\lfloor\hskip-3.0pt\lfloor}b is not. In general, a suitable definition of guardedness is whatever syntactic criterion allows one to obtain RSP for a chosen semantic equivalence. Proofs of RSP [ 31 , 3 ] tend to depend to a large extent on the syntax and semantics of the process algebra involved. The goal of this paper is to give a proof of RSP for strong bisimulation semantics for a large class of process algebras, including CCS and ACP, at once. I do this by characterising a format for transition system specifications in structural operational semantics, proposing the most general definition of guardedness I can find in that context, and formally show that all process algebras whose operational semantics fits that format satisfy RSP, for strong bisimilarity. They also satisfy RDP, but that is fairly trivial. The most general format for standard process algebras (without probabilities, time, name-binding or other special features) that guarantees strong bisimilarity to be congruence is the ntyft/ntyxt format of Groote [ 24 ] , augmented with recursion as in [ 21 ] . Let f (pronounced “after a ”) be a unary operator defined through the transition rules \frac{x\stackrel{{\scriptstyle a}}{{\longrightarrow}}y~~~y\stackrel{{\scriptstyle b}}{{\longrightarrow}}z}{f(x)\stackrel{{\scriptstyle b}}{{\longrightarrow}}z} for the specific action a and each action b . It has lookahead, in the sense that the initial actions of f are determined by looking ahead at the second action performed by its argument. Now the recursive equation X=f(a.X) has any process as solution, even though the recursion variable X appears guarded (by the guard a ) in the body f(a.X) of the recursion equation. Because of this I rule out lookahead in this paper. Aiming for maximal generality, I will obtain RSP for strong bisimilarity in the ready simulation format [ 17 ] , which is the ntyft/ntyxt format without lookahead, augmented with recursion. Most applications of this work will fall in the GSOS format, which restricts the ready simulation format mainly by allowing only variables to occur in premises, except in the rules for recursion. In this context I favour a notion of guardedness due to Vaandrager [ 36 ] : an n -ary operator f guards its i^{\rm th} argument iff there is no transition rule of the form \frac{H}{f(x_{1},\dots,x_{n})\stackrel{{\scriptstyle a}}{{\longrightarrow}}E} such that the variable x_{i} occurs as the left-hand side of one of the premises in H . I will generalise this idea to the ready simulation format by allowing x_{i} to occur in the left-hand sides of premises (which may be complex terms) but only in guarded positions. After establishing RSP for strong bisimilarity, I observe that by means of an almost identical proof it can also be shown for other strong semantic equivalences at the branching time side of the linear time – branching time spectrum [ 19 ] , namely simulation equivalence (in the absence of negative premises) and ready simulation equivalence. Naturally I would like to show it for preorders as well. Using the notation \vec{P}\equiv{\cal S}[\vec{P}] to indicate that the tuple \vec{P} is a solution of the recursive specification {\cal S} up to the semantic equivalence \equiv , there are two ways to replace \equiv by a preorder \sqsubseteq . When \vec{P}\sqsubseteq{\cal S}[\vec{P}] holds I call \vec{P} a presolution of {\cal S}[\vec{P}] , and when {\cal S}[\vec{P}]\sqsubseteq\vec{P} holds I call it a