This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
C^ with p' \= cpg' but ^' ^ (^^' (use negation if necessary). Now p^a Aq'eQ' ^9' ^ C^^^ and therefore ^y |= a Aq'eQ' ^q'- ^^ ^^^^^ "^^^^ be a ^' G P with q - ^ <7' and q' ^ 2 ^ which had to be shown. D Comparing their modal characterizations ( = ^ of 1± and = ^ of '^) one finds p ^ q
=» p--q
=^
P='B^'
Theorem 2.1 in Hennessy and Milner [27,28] says, essentially, that for image finite processes the relation ^ satisfies the defining properties of a bisimulation (cf. Definition 12). Inspired by this insight. Park [41] proposed the concise formulation of bisimulation equivalence employed in Definition 12. It follows immediately that if p, ^ G P are image finite, then p<±q ^ p^ q. The following strengthening of this result is due to Hollenberg [32]. PROPOSITION
12.6. Let p,q eF and p is image finite. Then pt± q O p=~Bq'
PROOF. Write pBq iff p =~^ q and p is image finite. It suffices to establish that 5 is a bisimulation. - Suppose pBq and q - % q\l have to show that 3r G P with p - % r and HM{r) = HM(q'). Lei R he
{reF\p-^rA
HM(r) ^ HM{q) \.
54
RJ. van Glabbeek As p is image finite, R is finite. For every r e R take a formula (pr € HM{q') - HM(r) (note that if i/r € HM(r) - HM{q) then ^^ e HM{q) - //M(r)). Now
a
/\(preHM{q)=HM{p), reR
SO there must be a r G P with p - ^ r and r [= Are/? ^f- The latter implies r ^ /?, i.e., HM{r) = HM{q'), which had to be shown. - Suppose pBq and p - ^ p'. I have to show that 3q' e P with q - % ^' and HM(p') = //M(^0.Let5be {5 6 P I /? - ^ ^ A //M(5) 7«^HMip)}. As /? is image finite, S is finite. For every s e S take a formula (ps e HM(p) - HM(s). Now a / \ (^, €//M(p) = f/M(^),
so there must be a ^' € P with q - ^ q' and ^' [= AVGS^^- ^^ ^^^ previous item in this proof, 3r € P with /? - ^ r and HMir) = HM{q), hence r \= /\^^^ (ps. The latter implies r^S, so HM(r) = HM{p'). Thus HM{p') = HM{q'), which had to be shown. D By Counterexample 12, a result like the one above does not hold for (ready) simulation semantics. For the sake of completeness, two more variants of bisimulation equivalence can be conside£ed. Let FB* be characterized by the Hennessy-Milner logic augmented with formulas X, and /?B* by the Hennessy-Milner logic augmented with formulas X, for X c Act. Then B~ < FB* < RB* < B^ < B, and for image finite processes all five equivalences coincide. The strictness of these inclusions is given by Counterexamples 4, 11,9 and 1: PROPOSITION
12.7. CT:^B-,
and hence FB"" 2^ B'.
PROOF. Counterexample 4 shows two processes with CT{left) i^ CT{right). It remains to be shown that HM(left) = HM(right), i.e., that for all cp € CHM' left ^ cp <^ right \= cp. Using Definition 12.5 it is sufficient to restrict attention to formulas (p which are of the form a(A/e/ ^i~^ ^ /\jeJ """^i^) ^^^h ^ ^^^ ^ ^^^^^ ^^^^ ^^ indices. It is not difficuh to see that each such formula that is satisfied on one side is also satisfied on the other side. D PROPOSITION
12.8. R:^ FB\ and hence RB* i FB"".
PROOF. Counterexample 11, shows two processes with R{with) ^ R(without). It remains to be shown that FB*(with) = FB* (without). The argument is the same as in the previous proof, but this time focusing on formulas of the form a(X A A / e / ' T A Ayey "^7~'") ^^^^ / and J finite sets of numbers and X a possibly infinite set of numbers (= actions). D
The linear time - branching time spectrum I
55
PROPOSITION 12.9. 5^ ^^ /?5*, and hence RB^ i, RB*. PROOF. Counterexample 9 shows two processes with S^{with) :^ S^(without). It remains to be shown that RB*(with) = RB* (without). The argument is the same as in the previous proofs - this time using formulas
a({b} A /\biT /€/
A
/\-^bjTj jeJ
'
with / and / finite sets of numbers.
D
PROPOSITION 12.10. T^ i.B'^, and hence B 2< B"^, In addition, PF i, 5^. Counterexample 1 shows two processes with T^(left) ^ T^(right). As remarked at the end of Section 7, also PF(left) / PF (right). It remains to be shown that left = ^ right, i.e., that for all n eN: left --„ right. In order to establish p ^n (1 for two trees p and q, the parts of p and q that are further than n edges away from the root play no role, and can just as well be omitted. As the cut versions of left and right are isomorphic, by Corollary 12.1 surely left --„ right. U PROOF.
In addition one has IS' < B~, F2S* < FB\ R2S* < RB*, 25^ < B"^ and
2S
13. Tree semantics 13. Let ^ e G. The unfolding ofg is the graph U(g) e G defined by • N0DES(i7(^)) = PATHS(^), • ROOT(U(g)) = ROOT(^), i.e., the empty path, starting and ending at the root of g, • (n, a, 7t^) e EDGES(L^(^)) iff TT' extends TT by one edge, which is labelled a. Two processes p and q are tree equivalent, notation p =ij q/\i their unfoldings are isomorphic, i.e., if U(G(p)) = U(G(p)). In tree semantics (U) two processes are identified iff they are tree equivalent. DEFINITION
It is easy to see that the unfolding of any process graph is a tree, and the unfolding of a tree is isomorphic to itself. It follows that up to isomorphism every tree equivalence class of process graphs contains exactly one tree, which can be obtained from an arbitrary member of the class by means of unfolding. PROPOSITION PROOF. AS
U(g)mdg.
13.1. Let g eG. Then U(g)t> g. Hence g=u h=^
gi±h.
is easily verified, {(7T,end(7T)) \ n € PATHS(g)} is a bisimulation between D
Tree semantics is employed in Winskel [50]. No plausible testing scenario or modal characterization is known for it. Proposition 13.1 shows that B
56
/ ? . / van Glabbeek
a -\- a
a
Counterexample 15. Bisimulation equivalent, but not tree equivalent.
Although above tree equivalence is defined entirely in terms of action relations, such a definition is in fact misleading, as action relations abstract from an aspect of system behaviour that tree semantics tries to capture. The problem can best be explained by cona
sidering the process ^cT that can proceed from its initial to its final state by performing one of two different a-transitions. In tree semantics, such a process should be considered equivalent to the leftmost process of Counterexample 15, and hence different from the rightmost one. However, action relations only tell whether a process p can evolve into q by performing an ^-action; they do not tell in how many ways this can happen. So in labelled transition systems as defined in this paper the mentioned process is represented as c^-^ and hence considered tree equivalent to the rightmost process of Counterexample 15. The mishap that ensues this way will be illustrated in Section 17. Tree semantics on labelled transitions systems as in Section 1.1 is a sensible notion only if one knows that each transition in the system can be taken in only one way. In general, more satisfactory domains for defining tree equivalence are labelled transition systems in which the transitions (p,a,q) are equipped with a multiplicity, telling in how many different ways this transition can be taken, or process graphs g = (NODES(^), ROOT(g), EDGES(^), begin, end, label) in which NODES(g) and EDGES(^) are sets, ROOT(^) € NODES(^), begin, end: EDGES{g) -^ NODES(g) and label :EDGES(g) -^ Act. The functions begin, end and label associate with every edge a triple (s, a, t) G NODES(^) X Act x NODES(^), but contrary to the situation in Definition 1.3 the identity of an edge is not completely determined by such a triple. On such process graphs, the notions PATHS, unfolding and tree equivalence are defined exacdy as for the process graphs of Definition 1.3.
14. Possible worlds semantics In Veglioni and De Nicola [49], a nondeterministic process is viewed as a set of deterministic ones: its possible worlds. Two processes are said to be possible worlds equivalent iff they have the same possible worlds. Two different approaches by which a nondeterministic process can be resolved into a set of deterministic ones need to be distinguished; I call them the state-based and the path-based approach. In the state-based approach a deterministic process h is obtained out of a nondeterministic process g e G by choosing, for every state s oi g and every action a e I(s) a single edge s —% s'. Now h is the reachable part of the subgraph of g consisting of the chosen edges. In the path-based approach on the other hand, one chooses for every path n e PATHS(g) and every action a e I{end{n)) a single edge end{iz) - ^ s' to continue with. The chosen edges may now be different for different
57
The linear time - branching time spectrum I
paths ending in the same state. The difference between the two approaches is illustrated in Counterexample 16. In the state-based approach, the process in the middle has two possible worlds, depending on which of the two Z^-edges is chosen. These worlds are essentially abc and ab^. In the path-based approach, the process in the middle has countably many possible worlds, namely ab^c for n ^ 1 and ab^. In [49], Veglioni and De Nicola take the state-based approach: *'once we have resolved the underspecification present in a state s by saying, for example, s - ^ s, then, we cannot choose s —% 0 in the same possible world". However, they provide a denotational characterization of possible worlds semantics on finite processes, namely by inductively allocating sets of deterministic trees to BCCSP expressions (cf. Section 17), which can be regarded as path-based. In addition, they give an operational characterization of possible world semantics, essentially following the state-based approach outlined above. They claim that both characterizations agree. This, however, is not the case, as Counterexample 17 reveals a difference between the two approaches even on finite processes. In the path-based approach the process displayed has a possible world acd -\- bee (i.e., a process with branches acd and bee), which it has not in the state-based approach. As it turns out, the complete axiomatization they provide w.r.t. BCCSP is correct for the path-based, denotational characterization, but is unsound for the state-based, operational characterization. To be precise: their operational semantics fails to be compositional w.r.t. BCCSP. Counterexample 16 shows that a suitable formulation^ of the state-based approach to possible worlds semantics is incomparable with any of the semantics encountered so far. The processes left and middle are state-based possible worlds equivalent, yet
state
bi
—pw
/path
Tpw
f b _I)ath -pw
Counterexample 16. State-based versus path-based possible worlds equivalence.
Counterexample 17. State-based versus path-based possible worlds equivalence for finite processes. Let two processes be possible worlds equivalent iff each possible world of the one is ~-equivalent to a possible world of the other, where ~ is any of the equivalences treated in this paper. Theorem 6 will imply that the choice of ~ is immaterial.
58
/?./ van Glabbeek
abbe G T{middle) — T(left). Furthermore, the processes right and middle are tree equivalent, yet in the state-based approach one has abbe e PW(right) - PW(middle). Below I propose a formalization of the path-based approach to possible worlds semantics that, on finite processes, agrees with the denotational characterization of [49]. DEFINITION 14. A process p is a possible world of a process q if p is deterministic and P ^RS q- Let PW(q) denote the class of possible worlds of q. Two processes q and r Sire possible worlds equivalent, notation q =pw r, if PW(q) = PVy(r). Impossible worlds semantics (PW) two processes are identified iff they are possible worlds equivalent. Write q ^PW r iff PW(q) C PW(r). It can be argued that the philosophy underlying possible worlds semantics is incompatible with the view on labelled transition systems taken in this paper. The informal explanation of the action relations in Section 1.1 implies for instance that the right-hand process graph of Counterexample 8 has a state in which a has happened already and both be and bd are possible continuations. In the possible worlds philosophy on the other hand, this process graph is just a compact representation of the set of deterministic processes [abc,abd}. None of the two processes in this set has such a state. This could be a reason not to treat possible worlds semantics on the same footing as the other semantics of this paper. However, one can give up on thinking of non-deterministic processes as sets of deterministic ones, and justify possible worlds semantics - at least the path-based version of Definition 14 - by an appropriate testing scenario. This makes it fit in the present paper. Testing scenario. A testing scenario for possible worlds semantics can be obtained by making one change in the reactive testing scenario of failure simulation semantics. Namely in each state only as many copies of the process can be made as there are actions in Act, and, for a e Act, the first test on copy pa of p is pressing the «-button. If it goes down, one goes on testing that copy, but is has already changed its state; if it does not go down, the test on Pa ends. Modal characterization. On well-founded processes, a modal characterization of possible worlds semantics can be obtained out of the modal characterization of ready simulation semantics by changing the modality /\i^f (pi into AC/GX ^^« ^^^^ ^ — ^^^' Possible worlds of a well-founded process p can be simply encoded as modal formulas in the resulting language. Probably, this modal characterization applies to image finite processes as well. For processes that are neither well-founded nor image finite this characterization is not exact, as it fails to distinguish the two processes of Counterexample 1. Classification. RT < PW < RS. PW is independent of 5, CS and PF. PROOF. 'TW
< RS'""^ follows by the transitivity of
^RS.
^ The counterexample against ""PW < /?5" given in [49] is incorrect. The two processes displayed there are not ready simulation equivalent.
The linear time - branching time spectrum I
a{bd-\-ce) -\-a{cf + bg)
59
a{bd -^ ce -^ cf -\-by)
Counterexample 18. Ready trace equivalent, but not possible worlds equivalent.
"/?r :< PW" holds as a is a ready trace of /? G P iff it is a ready trace of a possible world of p. "5 7^ PW" (and hence ''RS :^ PW) follows from Counterexample 8. There S(left) i^ S{right), but PW(left) = PW(right) = {abc, abd). "PF i, PW' follows since PF ^ RS. ''CS t PW follows since CS ^ RT, and 'TF t PW since PF ^ RT. Finally, ''RT ^ PW follows from Counterexample 18, taken from [49]. There the first process denotes two possible worlds, whereas the second one denotes four. D Infinite processes. The version of possible worlds semantics defined above is the infinitary one. Note that RT^ < PW. Exactly as above one even establishes p ^Rs q=^ p ^pw q=^ p ^fr ^' i.e., RT^ <* PW <* RS. Finitary versions could be defined by means of the modal characterization given above. I will not pursue this here.
15. Summary In Sections 2-14 fifteen semantics were defined that are different for finitely branching processes. These are abbreviated by 7, Cr, F ' , F, /?, FT, RT, PF, S, CS, RS, PW, IS, B and U. For each of these semantics O, except U, a modal language CQ (a set of modal formulas (p) has been defined: CT
(p ::= T | a(p\(p' € CT)
the (partial) trace formulas CcT ^'•'•=^\ aip'{(p' e CCT) I 0 the completed trace formulas Cp\ (p:\=T \ a(p\(p' € Cf\) | a{a € Act) the singleton-failure formulas CF (^ ::= T I a(p\(p' e CF) I X{X c Act) the failure formulas
60
R.J. van Glabbeek CR
(p ::= T I acp'icp' e £/?) | X(X c Act)
the readiness formulas CFT
(f ::= T | a(p\(p' e CFT) I X(p\X c Act. ip' e CFT)
iht failure trace formulas CRT
(p::=T\ acp^cp' e CRT) I X(p\X c Act,
DOM. An element x e DOM is called difixedpoint of (p'\f4>{x)=x. Let F/X be the set of all fixed points of 0 . An element x e DOM is called the least fixed point of
: DOM -^ DOM be a ^-monotonic mapping. Then
iff 3F.E - ^ F A F |= 0. We may also add some notion of variable or atomic proposition to the logic, in which case we provide a valuation which maps a variable to the set of states at which it holds. The expressive power of HML in this form is quite weak: obviously a given HML formula can only make statements about a given finite number of steps into the future. HML was introduced not so much as a language to express properties, but rather as an aid to understanding process equivalence: two (image-finite) processes are equivalent iff they satisfy exactly the same HML formulae. To obtain the expressivity desired in practice, we need stronger logics. The logic PDL, Prepositional Dynamic Logic [56,26], as mentioned above, is both a development of Floyd-Hoare style logics, and a development of modal logics. It is not widely used these days, but for historical reasons it is worth presenting it briefly. PDL is an extension of HML in the circumstance that the action set has some structure. There is room for variation in the meaning of action, but in the standard logic, a program is considered to have a number of atomic actions, which in process algebraic terms are just process actions, and a is allowed to be a regular expression over the atomic actions: a,a; p.aUfi, or a*. We may consider atomic actions to be uninterpreted atoms; but in the development from Royd-Hoare logics, one would see the atomic actions as, for example, assignment statements in a while program. PDL enriches the labels in the modalities of HML. An alternative extension of HML is to include further modalities. The branching time logic CTL, Computation Tree Logic Computation Tree Logic [17], can be described in this way as an extension of HML, with some extra 'temporal' operators which permit expression of liveness and safety properties. For the semantics we need to consider 'runs' of a process. A run of EQ is a sequence £"0 - ^ E\ -%• • • • which may have finite or infinite length; if it has finite length then its final process is a 'sink' process which has no transitions. A run EQ -%• E\ - ^ • • • has the property 0 U T/^, '0 until i/r', if there is an / ^ 0 such that £/ |= x// and for all 7: 0 ^ y < /,
£,N0. Eo-^ 'U
N (t>
E,^
•
N
• • •
£ ,
N ^
The formula F0 = (tt U 0) means '0 eventually holds' and G0 = --(tt U --0): '0 always holds'. For each 'temporal' operator such as U there are two modal variants, a strong variant ranging over all runs of a process and a weak variant ranging over some run of a process. We preface a strong version with V and a weak version with 3. If HML is extended with the two kinds of until operator the resulting logic is a slight but inessential variant of
Modal logics and mu-calculi: An introduction
299
CTL. The formal semantics is given by inductively defining when a state (process) has a property. For instance E |= V[0 U x//] iff every run of E has the property (pV \{/. CTL has variants and enrichments such as CTL* [25] and ECTL* [72]. These allow free mixing of path operators and quantifiers: for example, the CTL* formula V[F U 3FQ] is also a CTL formula, but V[P U ¥Q] is not, because the F is not immediately governed by a quantifier. Hence extensions also cover traditional temporal logics - that is, literally logics of time - as advocated by Manna and Pnueli and others. In this view, time is a Unear sequence of instants, corresponding to the states of just one execution path through the program. One can define a logic on paths which has operators O 0 'i" ^he next instant (on this path) 0 is true', and 0 U i/r '0 holds until i/ holds (on this path)'; and then a system satisfies a formula if all execution paths satisfy the formula - in CTL* terms, the specification is a path formula with a single outermost universal quantifier. One can also extend PDL with temporal operators, as in process logic. There are extensions of all these logics to cover issues such as time and probability. The introduction of real-valued quantities such as times and probabilities poses a number of problems, and such logics are still under active development.
2.1. The small model property A general result about many modal logics is that they have the small model property; that is if a formula is satisfiable, then it is satisfiable by a model of some bounded size. Provided that model-checking is decidable, which is the case for almost all temporal logics, this inmiediately gives decidability of satisfiability for the logic, as one need simply check every transition system up to the size bound. The technique used to establish the small model property for PDL (and therefore HML) is a classical technique in modal logic, that of filtration. Let £" be a possibly infinite-state process with the property 0, and let T be its transition system. Let F be the set of all subformulas of 0 and their negations: in the case of PDL one also counts {a)\lr and ()S)V^ as subformulas of {a U ^)T/r, {fi)}// as a subformula of (a; P)\lr and (a; Qf*)i/r, and {a)\l/ as subformulas of {a*)\l/. The size of F is proportional to |0| (the length of 0). One then filters T through F by defining an equivalence relation on the states of T, £ = F iff W^ e F.E \=\l/
[F]-%[F]
iff 3E' e[ElF'
e[FlE' -^
F\
The number of equivalence classes is at most 2'^' and so is 0(2'"^'). The rest of the proof shows that the filtered model is indeed a model, in that [E] \= x// iff E \= ir for xlr e F. For PDL the only case requiring comment is the case (a*)iA, which proceeds by an induction on the length of the witnessing sequence of c^'s. Consequently if 0 is a satisfiable PDL formula, then it has a model with size 0(2l^'), and in fact 2>^l suffices - see [26] for full details. In order to obtain an upper bound for satisfiability from the small model property, we also need to know the complexity of model-checking, that is, determining whether F f= 0.
300
/ Bradfield, C. Stirling
It is straightforward to define an inductive procedure for this, which is polynomial in the size of the formula and of the system. For example, to determine the truth of (a*)0, one computes the *-closure of the a relation, and then checks for an Q?*-successor satisfying 0. These results give an NTIME(c'0 upper bound for the satisfiability problem. By a reduction to alternating Turing machines, [26] also gave a lower bound of DTIME(c''/'^"). A closer to optimal technique for satisfiability due to Pratt uses tableaux [57]. Although CTL, CTL* and modal mu-calculus all have the finite model property, the filtration technique does not apply. If one filters T through a finite set F containing VF|2 unintended loops may be added. For instance if T is £/ - ^ £",+1 for 1 < / < « and Q is only true at state E,^ then £"/ |= VFQ for each /. But when n is large enough the filtered model will have at least one transition [Ej] —^ [£"/] when i ^ j
2.2. CTL model-checking CTL has some obvious differences from PDL. Firstly, although it is a state-based logic, in the sense that the formulae one writes are defined on states, it uses path operators internally: evaluating the formula V[0 U i/r] at a state involves considering all paths from that state. Thus, at first sight, one might expect to lose the obvious exponential upper bound on modelchecking. However, this turns out not to happen, and in fact CTL is very easy to modelcheck. This was shown by a direct construction in [18]; it also follows from the fact that, as we shall see later, CTL is a particularly simple fragment of the modal mu-calculus. The model-checking procedure of [18] is an example of an apparently global technique. It proceeds by model-checking subformulae from the bottom up, doing a full pass over the state space for subformulae before considering the superformula. In the original paper, the algorithm is presented as imperative pseudo-code, and it takes a little thought to see why it works. Here is an EngHsh outline, which extracts the idea of the code: • to check tt, -"0,01 A 02, check the subformulae and perform the Boolean operation; • to check (fl>0, [fl]0, check 0, and then apply the semantic definitions; • to check 3[0 U V^], check the subformulae, then find the states at which V^ holds, and trace backwards along paths on which 0 holds; these states satisfy 3[0 U ^]\ • to check V[0 U V^], check the subformulae; then make a depth-first traversal of the system, applying the following: if a state satisfies i/^, mark it as satisfying V[0 U i/r]; otherwise, if it fails 0, mark it as failing V[0 U i/^]; otherwise, after processing the successors, mark it as satisfying V[0 U V^] iff all its successors do. In following sections, we shall see CTL translated into modal mu-calculus, and we shall see global, backward-looking model-checking algorithms, and local, forward-looking algorithms. It is interesting, from today's perspective, to see that this early CTL algorithm has elements of both: the code for 3[0 U xj/] is doing exactly the computation by approximants (see Section 4.4) of the mu-calculus translation; but the code for V[0 U V^] is doing tableau model-checking (see Section 5.1).
Modal logics and mu-calculi: An introduction
301
3. Introduction to mu-calculi The defining feature of mu-calculi is the use of fixpoint operators.' The use of fixpoint operators in program logics goes back at least to De Bakker, Park and Scott [52]. However, their use in modal logics of programs dates from work of Pratt, Emerson and Clarke and Kozen. Pratt's version [58] used a fixpoint operator like the minimization operator of recursion theory, and this has not been further studied. Emerson and Clarke added fixed points to a temporal logic to capture fairness and other correctness properties [22]. Kozen's [37] paper introduced the modal mu-calculus as we use it today, and established a number of basic results.^ Fixpoint logics are notorious for being incomprehensible. Indeed, it has been known for several reasonably expert people to spend an hour or two trying to work out whether a one line formula means what it was intended to mean. Furthermore, a full understanding of the mathematical intricacies of the modal mu-calculus requires familiarity with mathematics that, although not difficult, is not covered in most undergraduate mathematics or computer science programmes; this can be a source of irritation for the practitioner new to the area. Fortunately, one can get a very good intuitive understanding, which is even provably equivalent to the formal semantics, without knowing the full details. Moreover, this intuition is all but essential for understanding the deep theory as well. In this section, therefore, we shall give an introduction to the modal mu-calculus that avoids the harder and more technical details, and concentrates rather on developing the intuition. In the first two subsections, we shall be so informal as to use notation and terminology well in advance of their definitions. In the following section, the semantics of the logic is examined in a little more detail, and the intuitions given a precise mathematical meaning.
3.1. Fixpoints as recursion Suppose that S is the state space of some system. For example S could be the set of all processes reachable from by arbitrary length sequences of transitions from some initial process E, One way to provide semantics of a state-based modal logic is to map formulae 0 to sets of states, that is to elements of pS. For any formula 0 this mapping is given by 110II ? The idea is that this mapping tells us at which states each formula holds. If we allow our logic to contain variables with interpretations ranging over pS, then we can view the semantics of a formula with a free variable, 0(Z), as a function / : pS -^ pS. If we take the usual lattice structure on pS, given by set inclusion, and if / is a monotonic function, then by the Knaster-Tarski theorem we know that / has fixed points, and indeed has a ' Whether one should say 'fixpoint', 'fix-point', or 'fixed point' is one of the most controversial questions in the theory of mu-calcuh. One of us (Bradfield) takes the view that one has 'fixpoint operators', which generate 'fixed points' of functions. Fortunately, few people enunciate with sufficient clarity to distinguish the two in conversation. ^ Kozen called the logic 'propositional mu-calculus' but this would be more appropriate for propositional logic + fixpoint operators, a logic we shall comment on later. The mapping can be either given directly (inductively) or indirectly as the set {5 G 5 : s\=(t>].
302
J. Bradfield, C. Stirling
unique maximal and a unique minimal fixed point. So we could extend our basic logic with a minimal fixpoint operator /x, so that /xZ.(/)(Z) is a formula whose semantics is the least fixed point of / ; and similarly a maximal fixpoint operator v, so that vZ.(p(Z) is a formula whose semantics is the greatest fixed point of / . The reason we might want to do this is that, as in domain theory for example, it provides a semantics for recursion. Writing recursive modal logic formulae may not be an immediately obvious thing to do, but it provides a neat way of expressing all the usual operators of temporal logics. For example, consider the CTL formula VG), 'always 0'. Another way of expressing this is to say that it is a property X such that if X is true, then 0 is true, and wherever we go next, X remains true; so X satisfies the modal equation X = 0A[-]X where = is logical (truth-table) equivalence,"^ and [—]X means that X is true at every immediate successor (see Section 3.3). So we could write this formula as?X.0A[—]X. But what is '?'? Which fixed point is the right solution of the equation - least, greatest, or something in between? We may argue thus: if a state satisfies any solution X' of the equation, then surely it satisfies VG(/>. Hence the meaning of the formula is the largest solution, vX.cf) A [—]Z. On the other hand, consider the CTL property 3F0, 'there exists a path on which 0 eventually holds'. We could write this recursively as T holds if either 0 holds now, or there's some successor on which Y is true': y = 0v{-)r. This time, it is perhaps less obvious which solution is correct. However, we can argue that if a state satisfies 3F0, then it surely satisfies any solution Y' of the equation; and so we want the least such solution. The astute reader will by now have noticed that the equations do not capture the meaning of the English recursive definitions - we should have written X=>(t)A[-]X and y^0v{-)y, or in terms of the semantic function, ||X|| c ||0 A [-]X\\ and ||y|| 2 110 v {-}Y\\. So we are not really interested in fixed points, but rather in respectively post-fixed points and pre-fixed points of the functions defined by the formulae on the right of the (in)equations; and since there is only one canonical post-fixed point and one canonical pre-fixed point, it becomes obvious which is required. It is an easy fact that the greatest post-fixed point and the least pre-fixed point of a monotonic function are also the greatest and least fixed points. We use double arrows =>, ^ for logical implication; single arrows -> are used for transition relations, as well as with their normal mathematical use.
Modal logics and mu-calculi: An introduction
303
and so we may continue to use the notation /x and y, and work with fixpoints. However, it is usual to emphasize this point when writing the semantics of fixpoint logics by writing, for example, ||/xZ.0(Z)|| = f ^ { ^ I 5 2 110(5)11} with inclusion rather than equality. At this point, the reader who does not already know the answer might like to apply a similar argument to produce the fixpoint translation of the CTL formula V[(/> U yfr].
3.2. Approximating fixpoints and ^i as finitely' The other key idea is that of approximants and unfolding. The standard theory tells us that if / is a monotonic function on a lattice, we can construct the least fixed point of / by iterating / on the bottom element ± of the lattice to form an increasing chain whose limit is the fixed point. The length of the iteration is in general transfinite, but is bounded at worst by the cardinal after cardinality of the lattice, and in the special case of a powerset lattice p<S, by the cardinal after the cardinality of S. So if / is monotonic on pS, we have
a
and similarly
Oi
- or in terms of a infinitary logic, ixZ.cpi^Z) = \Ja
304
/ Bradfield, C Stirling
one follows a chain of dependencies, the chain terminates. This is the strict meaning behind the slogan "/z means 'finite looping'", which, with a little refinement, is sufficient to understand the mu-calculus. On the other hand, for a maximal fixpoint vZ.(j)(Z), there is no such decreasing chain: def
s \= vZ.(f){Z) iff ^ 1= (l){vZ,(j)(Z)), and we may loop for ever, as in the CCS process P = a.P, which satisfies vZ.{a)Z. (However, if a state fails a maximal fixpoint, then there is a descending chain of failures.) Instead, we have the somewhat mystical principle of fixpoint induction: if by assuming that a set 5" |= Z, we can show that 5 ^= 0(Z), then we have shown that S \= vZ.cf) (compare the recursive formulation of VG0 in the previous section). So in summary, one may understand fixpoints by the slogan 'y means looping, and /x means finite looping'. This slogan provides an alternative means of explaining why a minimal fixpoint is required in the translation of 3F(/). This formula means that there is a path on which 0 eventually holds: that is, on the chosen path, 0 holds within finite time. Hence the 'equation' F = 0 v (—) 7 must only be applied a finite number of times, and so by the slogan we should use a minimal fixpoint. In the case of formulae with alternating fixpoints (which we shall examine a little later), the slogan remains valid, but requires a little more care in application. It is essential to almost all proofs about modal mu-calculus: the notion of 'well-founded premodel' with which Streett and Emerson [68] proved the finite model property, is an example of the slogan; so are the tableau model-checking approaches of Stirling and Walker [66], and Bradfield and Stirling [13]. 3.3. Syntax of modal mu-calculus Let Var be an (infinite) set of variable names, typically indicated by Z, F , . . . ; let Prop be a set of atomic propositions, typically indicated by P, Q , . . . ; and let £ be a set of labels, typically indicated by a,b, The set of modal mu-calculus formulae (with respect to Var, Prop, C) is defined in parsimonious form as follows: • P is a. formula. • Z is a formula. • If 01 and 02 are formulae, so is 0i A 02. • If 0 is a formula, so is [a]0. • If 0 is a formula, so is -•0. • If 0 is a formula, then vZ.cf) is a formula, provided that every free occurrence of Z in 0 occurs positively, i.e., within the scope of an even number of negations. (The notions of free and bound variables are as usual, where v is the only binding operator.) If a formula is written as 0(Z), it is to be understood that the subsequent writing of 0(V^) means 0 with ^r substituted for all free occurrences of Z. There is no suggestion that Z is the only free variable of 0; and variable capture is not avoided. The positivity requirement on the fixpoint operator is a syntactic means of ensuring that 0(Z) denotes a functional monotonic in Z, and so has unique minimal and maximal fixpoint. This requires irritating book-keeping, and it is usually more convenient to introduce derived operators defined by de Morgan duality, and work in positive form:
Modal logics and mu-calculi: An introduction
305
• 01 V 02 means -"(-^01 A --^02). • {a)(j) means -^[a]-^^. • fxZ.(j)(Z) means -iyZ.-'0(-^Z). Note the triple use of negation in /x, which is required to maintain the positivity. A formula is said to be in positive form if it is written with the derived operators so that -^ only occurs applied to atomic propositions. It is in positive normal form if in addition all bound variables are distinct. Any formula can be put into positive normal form by use of de Morgan laws and a-conversion. So we shall often assume positive normal form, and when doing structural induction on formulae will often take the derived operators as primitives. For the concrete syntax, we shall assume that modal operators have higher precedence than Boolean, and that fixpoint operators have lowest precedence, so that the scope of a fixpoint extends as far to the right as possible. There are a few extensions to the syntax which are convenient in presenting examples, and in practice. The most useful is to allow modalities to refer not just to single actions, but to sets of actions. The most useful set is 'all actions except«'. So: . s\= [K](t) iff Vfl G K.s f= [a]0, and [«,/?,.. .]0 is short for [[a, b,.. .}]0. • [—K](p means [C — K](p, and set braces may be omitted. Thus [—10 means just [£]0.^
3.4. Semantics of modal mu-calculus A modal mu-calculus structure T (over Prop, C) is a labelled transition system, namely a set 5 of states and a transition relation -> c 5 x £ x 5 (as usual we write s —> r), together with an interpretation Vprop : Prop -^ pS for the atomic propositions. Given a structure T and an interpretation V: Var -^ pS of the variables, the set ||0||y of states satisfying a formula 0 is defined as follows: \\P\\V = Vprop(P), \\Z\\l = V(Z), Ih0llv=<5-11011^, ll0iA02||^ = 110111^ n 110211^, IIW0llv =
{^|Vr.^-^r=^r€||0||^},
IvZ.cPWv = U I ^ ^ ^ I ^ ^ I I ^ I I V I Z : :--s\i where V[Z := S] is the valuation which maps Z to 5 and otherwise agrees with V. If we are working in positive normal form, we may add definitions for the derived operators by duality: ^ Beware that many authors use '[]0' to mean *[£]0\ rather than the (vacuous) *[0]0" that it means in our notation.
306
/ Bradfield. C. Stirling
Ui^Mv
^ ll'AillvUII'/'all^,
\\{aml =
[s\Jt.s^tAte\ml},
\\HZ4\\1 ^f][SQS\So
\mv[z:^s]]-
We drop ^ and y whenever possible; and write 5 ^= 0 for 5 G ||(/>||. We have discussed informally the importance of approximants; let us now define them. If iiZ.(t){Z) is a formula, then for a € On, let fiZ".(f) and /xZ*^".0 be formulae, with semantics given, with simultaneous induction on a, by:
\\fiz<\4>\\l=
[j\\nz'^.
The approximants of a maximal fixpoint are defined dually:
ivz<«.0|i; = nii-2^-
T
v
Note that iiZ^^.(f) <<=^ ff and vZ^^.cp <=> tt. By abuse of notation, we write Z" or 0^ to mean ^Z^.cf); of course this only makes sense when one knows which fixpoint and variable is meant. We should remark here that most literature on the modal mu-calculus uses a slightly different definition, putting /xZ^.0 = ff, /xZ^+' .0 = 0(/xZ^.>), and /iZ^.0 = U^<;, /xZ^.0 for limit k - which in effect is writing a for our
Modal logics and mu-calculi: An introduction
307
is a relativized 'always' formula: 'P is true along every cr-path'. Slightly more complex is the relativized 'while' formula vZ.Qv(PA[a]Z) 'on every a-path, P holds while Q fails'. Both formulae can be understood directly via the fixpoint construction, or via the idea of 'y as looping': for example the second formula is true if either Q holds, or if P holds and wherever we go next (via a), the formula is true, and . . . , and because the fixpoint is maximal, we can repeat forever. So in particular, if P is always true, and Q never holds, the formula is true. fx formulae, in contrast, require something to happen, and thus are liveness properties. For example fjiZ.Pv[a]Z is 'on all infinite length a-paths, P eventually holds'; and fjiZ.Q\/(PA{a)Z) is 'on some a-path, P holds until Q holds (and Q does eventually hold)'. Again, these can be understood by '/x as finite looping': in the second case, we are no longer allowed to repeat the unfolding forever, so we must eventually 'bottom out' in the Q disjunct. This level of complexity suffices to translate CTL, since we have /xZ.Q v (F A {—)Z) as a translation of 3[P U Q], and fxZ.Qv (P A [ - ] Z A (-)tt) as a translation of V[P U Q]; and obviously we can nest formulae inside one another, such as yZ.(/xF.Pv(->r)A[-]Z 'it is always possible that P will hold', or VG(3FP). Equally obviously, we can write formulae with no CTL translation, such as luiZ.[a]ffv {a){a)Z which asserts the existence of a maximal a-path of even length; a formula which is, incidentally, expressible in PDL. This is, however, a fairly simple extension; much more interesting is the power one gets from mixing fixpoints that depend on one another. Consider the formula /jiY.vZ.iP A [a]Y) V ( - P A [a]Z), This formula is likely to stymie the average newcomer to the modal mu-calculus, but it has a simple meaning, which can be seen by using the slogans. fiY— is true if vZ— is true if (P A [a]Y) V (--F A [fl]Z), which is true if either P holds and at the next («)-states we loop back to JJLY , or P fails, and at the next states we loop back to vZ By the slogan '/x means finitely', we can only loop through fiY finitely many times on any path, and hence P is true only finitely often on any path.
308
/ Bradfield, C. Stirling
A variant on this theme illustrates the ease with which the modal mu-calculus can talk about actions, which from a traditional process calculus viewpoint are all that one can observe. By similar reasoning to the above, one can see that fiY.vZ.[a]Y
A[-a]Z
asserts that a process does only finitely many a actions, whatever else it does: it may even diverge. For example, consider the divergent value-passing CCS process def
A(n) = T.A(n + 1) -h T.B{n)
B(n) =ifn>0
then a.B(n - 1).
A(0) satisfies the formula. To see that this really is true, as the slogans suggest it is, we can examine the semantics. As this is an example of a nested fixpoint, let us consider the approximants. The first approximant of the outer minimal fixpoint is fiY^....
= vZ.[a]{fjiY''^....)
A [-a]Z = yZ.[^]ff A [-a]Z.
We may also calculate this maximal fixpoint by approximants. Its first approximant is vZ^— = [a]ff A [—«]tt, which is, by inspection, the processes A(i) (/ ^ 0) and B(0). The next approximant is vZ^ = [a]ffA [—a](vZ'^^ ), which again by inspection is just B(0); and here we stabilize. So we are now in a position to calculate the next outer approximant: /xF^ ... = vZ.[a]{fjiY''\ ...) A [-a]Z = vZ.[a]{B(0)} A [-a]Z. The reader may compute this by approximants to obtain ^(0), ^(1). Continuing, we obtain fiY^ — = {B(j) I j < /}. The next approximant is where everything happens: /xF^.... = vZ.[a]{iiY^'^....)
A [-a]Z = vZ.[a]{B(i)} A [-a]Z.
A further calculation shows that here vZ^ is all processes, and so we stabilize; now the outer approximant chain has also converged at all processes. It is also worth briefly considering the negative of this, namely 'infinitely often', as it illustrates the finite unfolding of /x within an outer v. Consider the formula vY.fiZ.(a)Yv
(r)Z.
Applying the slogans, we see that this is true if either we can do an a and loop to 7, or do a r, and loop to Z. We can only loop to Z finitely often, so we can only do finitely many consecutive rs; but if we do an a and loop back out to F, we then re-enter the inner fixpoint, free to do another independent finitely many rs. The really enthusiastic reader might like to evaluate this formula by approximants on the modified set of processes given by putting B{n) = T.A(2n) -h if n > 0 then a.B(n-\). We shall see in a later section that this so-called alternation of fixpoint operators does indeed give ever more expressive power as the number of alternations increases. It also
Modal logics and mu-calculi: An introduction
309
appears to increase the complexity of model-checking: all known algorithms are exponential in the alternation, but whether this is necessarily the case is the main remaining open problem about the modal mu-calculus. (See Section 4.4 for more on the complexity of model-checking.) However, the practitioner who is alarmed by the thought of even more complex formulae, can take comfort in the widely asserted proposition that one never actually needs more than two alternating fixpoints, and even two is a bit unusual. In fact, many would go further and say that in real life we are only interested in safety properties. There are two main reasons why alternating formulae might appear. The first is if one has a front end working in CTL* (or another complex logic), and is translating into modal mucalculus for the main engine. This is theoretically possible, by work of Mads Dam [19], but the translation is sufficiently complex that it would be surprising to find a tool doing this. The second is if one needs to express fairness. Fairness properties, whether weak (an event continuously enabled must happen) or strong (an event enabled infinitely often must happen), can be written in the modal mu-calculus, and require mixing fixpoints. For example, to say that an action a is fairly treated means that there are no paths on which a is enabled infinitely often, but occurs only finitely often; this can be written as vX.fiY.vZ.[a]X
A ({a)ti => [-a]Y) A [-a]Z,
Of course, we may be in a situation where the system is inherently unfair - e.g., it is a normal interleaving of concurrent components - and in that case we can use a similar idea to express properties such as ' P eventually holds on all paths, provided that a is fairly treated', which is left as an exercise for the reader. However, fairness can also be handled by other means, such as defining the set of fair paths 'outside' the logic, and adapting algorithms to apply only to fair paths. 3.6. Modal mu-calculus as a process logic So far, we have described the modal mu-calculus as a logic on labelled transition systems; but this is a handbook of process algebra. Of course, process algebras, or at least simple traditional process algebras, are equipped with an operational semantics that defines a labelled transition system, in which the states are usually pieces of syntax. The easy way to interpret any modal logic on a process algebra is just to use this generated transition system. However, in theory one's notion of process is not just a piece of syntax, but some behaviour, and one wishes to treat identically 'processes' that are behaviourally equivalent. In the CCS world view, we believe that processes that are strongly bisimilar are equivalent for all practical purposes - and most non-practical purposes - and in many situations we might treat observational congruence or weak bisimulation similarly. In more exotic situations we might view any of the hundreds of known equivalences as process equality. This raises the obvious question of how our logic behaves with respect to such equivalences, and what should we do if it behaves badly. The first answer is that the logic behaves well: If two processes (i.e., states in transition systems) are strongly bisimilar, then they satisfy exactly the same modal mu-calculus formulae. This is proved by an easy induction. In fact, for finite-branching systems (more precisely, image-finite systems) the converse is also true provided the atomic propositions respect
310
/ Bradfield, C. Stirling
bisimulation, so that modal mu-calculus (or indeed its small subset HML) characterizes strong bisimulation; this fails for arbitrary systems. An inductive proof of this result is presented in [64]. However, if we prefer, as we usually do, to work with a weaker equivalence, this of course is no longer true, since the modal mu-calculus as we have defined it treats r just as any other action. There are several ways to deal with this. One is just to accept it, and when writing properties in the mu-calculus to be very careful to write explicitly a formula that does the desired thing with silent actions; this has obvious drawbacks. A more natural option, provided that whatever tool one is using supports it, is to work with the weak transition system, namely the transition system defined by"^ s ^=^ t if s - ^ - ^ - ^ t. A compromise is to stick with the strong transition system, but to define derived modalities which take account of r. For example, one can define {{tz))0 to mean /zZ.(r)Z v {a)/jiZ.(t) v (r>Z, which captures in the strong logic the diamond modality in the weak transition system. Another issue that affects practice is the atomic propositions. We have presented the logic with arbitrary valuations for atomic propositions, but this is neither possible nor desirable in practice. Typically there will be some small language of atomic propositions; for example, in value-passing CCS one wants to have basic expressions over the parameters of a process. One might imagine that by restricting this language one could obtain better results on decidability etc.; although this is, loosely speaking, true in practice, in the sense that 'sensible' properties of 'sensible' systems can be expressed and often proved entirely within a 'sensible' language, it is not generally true in a mathematical sense, since the basic mu-calculus operators are sufficient to expose any undecidability that may be lurking in a system - for example, the halting property is just /xZ.[-]Z.
3.7. Linear time mu-calculus The modal mu-calculus is a pure branching time logic, although as we have seen in the examples it can express properties that are usually found in mixed branching/linear logics such as CTL*. One may also add fixpoint operators to linear time logic, to get a pure linear time mu-calculus. The modality in this case is a 'next' operator (g), and the logic is interpreted not over states of a system, but over runs or maximal paths. The formula @0 is satisfied by the runs cr = SQ -%• s\ -%- • • • such that a\ =a and s\ -^ • • • satisfies >. Adding negation, conjunction and maximal fixpoint to this operator gives the linear time mu-calculus. Just as in the modal case, the linear mu-calculus encompasses most other linear time logics. The linear 'until' operator (/> U i/^ is just /jiZ.x// v ((/> A QZ), and linear fairness operators can be expressed in a similar manner to their branching counterparts. At first sight, the linear mu-calculus is much harder to handle than the modal logic: we are interpreting over runs, and even a finite-state system generates continuum-many runs. So we are taking fixpoints in a lattice of size 2^"^, and our approximants may, at first sight, not close until (2^)+! Of course, this doesn't actually happen, and in fact for a finite-state system fixpoints close at a finite approximant. However, this approximant may ^ This double arrow is not logical implication!
Modal logics and mu-calculi: An introduction
311
be large, and model-checking is exponential [71]. It is possible to give a direct procedure, and even a direct local procedure, to model-check the linear time mu-calculus [66,12], but they are complicated, and for all but the smallest examples, automata-theoretic techniques are superior. On the other hand, the linear time mu-calculus is in some ways simpler than the modal mu-calculus. In particular, increasing alternation does not give increasing expressive power: any formula is equivalent to one of alternation depth two. Indeed, any formula is equivalent to an a>-regular expression. An elegant direct proof of this result is contained in [53] (which doesn't mention temporal logic and uses fixpoints of linear systems of equations^). An alternative proof uses automata. Biichi automata and linear time mu-calculus are equi-expressive, and a Biichi automaton is easily transformed into a formula whose alternation depth is at most two, see for example [51]. Generally speaking, the linear time mu-calculus has not offered the same advantages as the modal mu-calculus, and those who use a linear time logic use the traditional logic of 'next' and 'until', and its fragments.
4. Theory of modal mu-calculus 4.1. Fixpoint regeneration and the 'fundamental semantic theorem * In the informal description of the meaning of fixpoints, we used the idea of the dependency of 5 at 0 on / at i/r. We now make this precise. Assume a structure T, and a formula >. Suppose that we annotate the states with sets of subformulae, such that the sets are locally consistent: that is, s is annotated with a conjunction iff it is annotated with both conjuncts; s is annotated with a disjunction iff it is annotated with at least one disjunct; if s is annotated with [a]\lr (respectively, («)^), then all (respectively at least one) ^-successor is annotated with yl/\if s is annotated with a fixpoint or fixpoint variable, it is annotated with the body of the fixpoint. We call such an annotated structure a quasi-model. A choice function / is a function which for every disjunctive subformula ^\V\l/2 and every state annotated with \lr\ v 1/^2 chooses one disjunct f(s,\l/\ v 1/^2); and for every subformula (a)}// and every state s annotated with (a)}// chooses one ^-successor t = f(s, (a)}//) annotated with i/r. A pre-model is a quasi-model equipped with a choice function. Given a pre-model with choice function / , the dependencies of a state s that satisfies a subformula x/r are defined thus: s@'ilr\ A x/rz > s@\l/i for / = 1, 2; s@[a]\lr > t@\// for every t such that s - ^ t; s@\l/\ w \j/2> s@f(s, f\ v 1/^2); s@{a)^ > f(s, {a)xlr)@\l/; s@^Z.\lr > s@\lf; s@Z > s@\l/ where Z is bound by ^ Z. 1/^. A trail is a maximal chain of dependencies. If every trail has the property that the highest (i.e., with the outermost binding fixpoint) variable occurring infinitely often is a y-variable, the pre-model is well-founded. (Equivalently: in any trail, a /x-variable can only occur finitely often unless a higher variable is encountered.) The fundamental theorem on the semantics of the modal mu-calculus can now be stated: This is the same paper where bisimulationfirstappears.
312
J. Bradfield, C Stirling
THEOREM 1. A well-founded pre-model is a model: in a well-founded pre-model, if s is annotated with i/r, then indeed s |= i/r.
The theorem in this form is due to Streett and Emerson in [68], from which the term 'well-founded pre-model' is taken. Stirling and Walker [65] presented a tableau system for model-checking on finite structures, and the soundness theorem for this is essentially a finite version of the fundamental theorem with a more relaxed notion of choice; the later infinite-state version of [13,8] is the fundamental theorem, again with a slight relaxation on choice. A converse is also true: 2. If in some structure s \= (f), then there is a locally consistent annotation of the structure and a choice function which make the structure a well-founded pre-model. THEOREM
The fundamental theorem, in its various guises, is the precise statement of the slogan '/x means finite looping'. To explain why it is true, we need to make a finer analysis of approximants. Assume a structure T, valuation V, and formula 0 in positive normal form. Let Y\, ...,Yn be the /x-variables of 0, in an order compatible with formula inclusion: that is, if fiYj.-il/j is a subformula of ^lYi.ijri, then / ^ 7 . If K, is some inner fixpoint, then its denotation depends on the meaning of the fixpoints enclosing it: for example, in the formula ijiY\.{a)iJiY2.(P V Y{)v (b)Y2, to calculate the inner fixpoint 11Y2 we need to know the denotation of Y\. We may ask: what is the least approximant of Y\ that could be plugged in to make the formula true? Having fixed that, we can then ask what approximant of Y2 is required. This idea is the notion of signature. A signature is a sequence a = a i , . . . , a,, of ordinals, such that the / least fixpoint will be interpreted by its of/th approximant (calculated relative to the outer approximants). The definition and use of signatures inevitably involves some slightly irritating bookkeeping, and they appear in several forms in the literature. In [68], the Fischer-Ladner closure of 0 was used, rather than the set of subformulae. The closure is defined as for PDL (see Section 2.1), with the addition of the rule that if ^ Z. if{Z) e cl(0), then iA(^ Z. x//) € cl(0). The signatures were defined by syntactically unfolding fixpoints, rather than by semantic approximants. In [65] and following work, a notion of constant was used, which allows some of the book-keeping to be moved into the logic. Although all the notions and proofs using them are interconvertible, the 'constant' variant is perhaps easier to follow, and has the advantage that it adapts easily to the modal equation system presentation of modal mu-calculus, which we shall see below. Indeed, it arises more naturally from that system. Add to the language a countable set of constants U,V, Constants will be defined to stand for maximal fixpoints or approximants of minimal fixpoints. Specifically, given a formula 0, let Ki,..., Y,j be the /x-variables as above, let Z i , . . . , Z,„ be the y-variables, let a = a i , . . . , a„ be a signature, and let f/i,..., L^„, Vi,..., V,„ be constants, which will be associated with the corresponding variables. They are given semantics thus: if Yi is bound by /xF/.V^/, then \\Ui \\a is W/JLY"' .i/r/||^, where x//'. is obtained from x/fi by substituting the corresponding constants for the free fixpoint variables of /xYi.x/fi. If Z, is bound by
Modal logics and mu-calculi: An introduction
313
vZi.yj/i, its semantics is WvZi.f'-Wa. Given an arbitrary subformula yj; of 0, we say a state s satisfies i/r with signature cr, written s \=^o i^/^^s e W^I/'Wo^ where ^' is i/r with its free fixpoint variables substituted by the corresponding constants. Order signatures lexicographically. Now, given a pre-model for 0, extend the annotations so that each subformula at s is accompanied by a signature - write s@\lf[(T]. Such an extended annotation is said to be locally consistent if the signature is unchanged or decreases by passing through Boolean, modal, or y-variable dependencies, and when passing through s@Yi it strictly decreases in the /th component and is unchanged in the 1,...,(/ — l)th components. It can now be shown, by a slightly delicate but not too difficult induction, that if 5@V^[a], then ^ |=^ i/r. Furthermore, given a well-founded pre-model, one can construct a locally consistent signature annotation - essentially, the K, component of cr in 5@i/r[a] is the maximum 'number' (in the transfinite sense) of F, occurrences without meeting a higher variable in trails from s@-4r, and so on; the well-foundedness of the pre-model guarantees that this is well-defined. This gives the fundamental theorem. (A little care is required to get the details of this argument correct, as will be seen from an inspection of the proofs in [68,65,8].) The converse is quite easy: given a model, annotate the states by the subformulae they satisfy; for ^@V^ assign the least a such that s \=o '^\ and choose a choice function that always chooses the successor with least signature. It is easy to show that this is a wellfounded pre-model and signature assignment.
4.2. The finite model property and decidability The notion of well-founded pre-model was introduced by Streett and Emerson in order to estabhsh the 3. The modal mu-calculus is decidable; that is, it is decidable whether a formula has some model. THEOREM
As a corollary of this proof, they obtained the small model property 4. If a modal mu-calculus formula has a model it has a finite model of size exponential in the size of the formula. THEOREM
These results were obtained by appealing to automata theory. First of all, one can easily show that if a formula has a model, it has a model that is a tree (just unravel the original model), and has bounded branching degree (just cut off all the branches that are not actually required by some diamond subformula; this leaves at most (number of diamond subformulae) branches at each node). We can now construct an automaton that accepts such bounded-branching tree models, by combining a finite-state automaton to check the local consistency (i.e., to check that the putative model is a pre-model), and a Rabin automaton (see Section 6) to check that the pre-model is well-founded. Thus the formula is satisfiable if this product automaton accepts some tree. Now established automata theory tells us that (a) this question is decidable (b) if such an automaton accepts some tree, it
314
J.Bradfield, C.Stirling
accepts a regular tree, that is, one that is the unravelling of a finite system; this gives the results. One can, however, obtain a small model property, and thence decidability, by a more direct argument on models. Take a pruned tree model as above, and equip it with an annotation and choice function to make it a well-founded pre-model. Consider an outermost maximal fixpoint vZ.xj/, say. Look at the first occurrence of a state s labelled by Z; let F be the set of formula annotating s. Now, if there is a state t below s that is also annotated by F, prune the tree at /, and identify t with s. Repeat for all Z labelled states with repetitions below them. On the remaining infinite branches of the tree, Z does not occur infinitely often; and by the well-foundedness of the pre-model, no immediately inferior least fix-point occurs infinitely often either; so we still have a well-founded pre-model. Now repeat the procedure with the next maximal fixpoint in, and so on. When all fixpoints have been processed, the result is a finite graph that is still a well-founded pre-model. The repetition detection is reminiscent of the filtration technique we saw for PDL. Unfortunately, filtration is not sound for minimal fixpoints, so we have this less constructive procedure. It generates, naively, a model of triply exponential size; but it is intuitively easy, and of course the existence of even a triply exponential model is enough to give decidability. One can improve the complexity somewhat by being less simple-minded, but to obtain the exponential upper bound of [68], which is in fact also the lower bound, one needs the more sophisticated techniques of automata or games. A different method for obtaining the small model property proceeds via a normal form result for modal-mu calculus. A formula is in "automaton normal form", anf, if it belongs to the following sublogic. • P, --P and Z are anfs. • If 01 and 02 are anfs, so is 0i v 02. • If 0 is an anf, then so are vZ.
(a)r= /\{a)(t>A[a]\/ (per
(p.
(per
Walukiewicz in [74] (and see also [33]) proved that every (closed) modal mu-calculus formula is equivalent to an anf formula. Walukiewicz calls anfs "disjunctive formulae". However they are very close to characteristic automata (and in fact games). The proof of the normal form result uses automata. What is interesting is that an anf formula is satisfiable iff all its fixed point subformulae fxZ.cpiZ) are replaced with 0(fO and all subformulae vZ.(t>{Z) are replaced with 0(tt). The result of these substitutions is a modal mu-calculus formula without fixed points, for which proof of the finite model property is easy. 4.3. Axiomatization A related problem to decidability is the question of providing an axiomatization of the theory of the modal mu-calculus. In his original paper, Kozen presented the following
Modal logics and mu-calculi: An introduction
315
axiomatization of the equational theory, where 0 ^ i^ means > v T/^ = i/r, taking () and /x as primitives and defining [] and v by duality: (1) axioms for Boolean algebras; (2) (a)0v(a)iA = (fl)(0vVr); (3) {a)(t)A[a]xlr^{a)((l)Axlr); (4) (a)ff=ff; (5) (t){iuiX,(f>(X))^fxX.(t>iX); (6)
^W ^ ^ fiX.(t>(X)^if' Axiom (5) is the axiom of fixed point induction, in dual form; rule (6) says that /x is indeed the least pre-fixed point. (An equivalent presentation of the axiom system is as an extension of minimal multi-modal logic K, with the additional axiom 0(/>6X.(/)(X)) =» fiX.cpiX) and the additional inference rule if 0(i/^) => xj/ then /xX.0(X) =>• xfr.) However, despite the naturalness of this axiomatization, Kozen was unable to show that it was complete. He was, however, able to show completeness for a restricted language, the language of aconjunctive formulae, in which (roughly) fixpoint variables are not allowed to occur in both branches of a conjunction. Completeness for the full language remained open for more than a decade, until it was finally solved by Igor Walukiewicz in [74], who established that Kozen's axiomatization is indeed complete. The proof is very involved and utilises automata normal form described above (which generalises the aconjunctive fragment). It is reasonably straightforward to show using tableaux that if an anf formula 0 is consistent^ then it has a model. Much harder to prove is that every (closed) formula is provably equivalent within the axiom system to an anf formula. Walukiewicz utilises automata and games to show this. More information can also be found in the notes [75].
4.4. Model-checking Decidability and axiomatization are standard questions for logicians; but for the practioner, the important question is model-checking: given a system T with some initial state s and a formula 0, is it the case that ^ f= 0? For the modal mu-calculus, the decidability of this question is obvious, for finite systems; the problem is, what is its complexity? There have been great technological advances in the model-checking of finite-state systems by the use of clever data structures such as BDDs. There have also been useful advances for fragments of the modal mu-calculus. However, there has been only one notable improvement in our knowledge of the complexity of the general problem, and a full answer to the question remains something that haunts our dreams - literally, for at least one of the authors! To discuss the complexity of model-checking, we need to introduce the notion of alternation depth of a formula. We shall define this more precisely in the following subsection, which examines alternation. For the moment, it is sufficient to define it loosely as the maximum number of /JL/V alternations in a chain of nested fixpoints. In fact we usually add the ^ A formula (f) is consistent with respect to an axiom system if 0 =^ ff is not derivable within the axiom system. Completeness of an axiom system is equivalent to the statement that every consistent formula has a model (is satisfiable).
316
/ Bradfield, C Stirling
proviso that the nesting is genuine interdependence of the 'infinitely often' kind rather than mere inclusion of closed subformulae of the 'always eventually' kind (see Section 3.5); but the proviso may be ignored without changing the essentials of the arguments. Suppose that we simply 'model-check' by brute force calculation of the approximants. Let the size (number of states plus number of transitions) of the system be n, the length of the formula be m. Every fixpoint closes at, at worst, the nth approximant. Calculating the booleans takes time 0(n); calculating modalities takes time 0(n). For an innermost fixpoint, given a valuation of the free variables, we may need to evaluate the body n times to close. So the innermost fixpoint takes time 0(n • (mn)). Now the next fixpoint out may also need to be evaluated n times, each of which involves evaluating the inner fixpoint (and some non-fixpoint operators); and so that takes 0(M • n • (mn)). And so on: so we end up with 0(m • n^"^'), where d is the depth of fixpoint operators. It turns out that by general results on fixpoints in lattices [7], adjacent fixpoints of the same type, such as /xy./xZ.0(y, Z) are not much worse than one, for the following reason: since ||/xZ.0(y""^\ Z)|| 2 ||/xZ.0(y^, Z)||, and the formulae are monotone, when one evaluates the ith outer approximant, one need not start evaluating the inner fixpoint from 0, but from wherever one had reached on finishing the (/ — l)th outer approximant. Alternatively, one can turn /xF./xZ.^ into a single fixpoint over a vector: /x(X, Y).(t). Thus we obtain the theorem of Emerson and Lei [25]: THEOREM 5. The model-checking problem for a formula of size m and alternation depth d ona system of size n is 0(m • n^'^^).
This theorem holds for the simple-minded notion of alternation, for the somewhat more refined version that Emerson and Lei used, and for the stronger notion of Niwinski [50]. So model-checking appears to be exponential in alternation depth. If, in the usual way, one defines the size of the problem to be the size of the system plus the size of the formula, this means that the problem seems to be exponential. Of course, it is a very well-behaved exponential, both theoretically, as by stratifying the formulae according to alternation depth one gets a chain of polynomial problems of increasing degree; and practically, because systems are typically large, formulae are typically small, and alternation depths are typically 1 or 2. However, it does not appear that the model-checking problem is polynomial. On the other hand, it is readily apparent that the problem is in NP. This was first remarked by Emerson, Jutla and Sistla in [24], who used an automata-theoretic argument. However, it can be seen directly [63]: take a model, and guess the right choice function and annotation to make it a well-founded pre-model. Now to check that it really is a well-founded pre-model, we need to check local consistency of the annotation, which is polynomial (and in fact quadratic); and we need to check well-foundedness. But to check well-foundedness on a finite pre-model, it suffices to show that there are no bad loops in the dependencies: if a minimal fixpoint occurs infinitely often without a higher fixpoint appearing, then there must be some state that occurs twice (and indeed infinitely often) labelled with that fixpoint. To check this, we can do strongly connected component analysis: starting from the bottom up, for each minimal fixpoint, cut the dependency graph at all higher fixpoints, and then look for a strongly connected component involving the said minimal fixpoint. This analysis is polynomial, of low degree; and we do it for each fixpoint; so the whole check is polynomial.
Modal logics and mu-calculi: An introduction
317
Since model-checking is trivially closed under complementation, the problem is in NP n co-NP. This places it in the very small class of such problems that are not known to be polynomial. Opinion is divided on the likely true complexity; some believe it to be polynomial, but although the P faction includes some most accomplished complexity theorists, no polynomial algorithm has yet been found, either for the mu-calculus itself, or for the stochastic pay-off games to which it can be reduced and which the complexity theorists are really interested in. Others, including exactly one of the authors, believe it to be nonpolynomial; although this would make the world a more interesting place, this belief has the obvious disadvantage of being impossible to confirm definitely without a resolution of P = NP. Of course, even a proof of non-polynomiality subject to P 7^ NP would be highly interesting. We mentioned that there has been one advance in the complexity of global modelchecking. This is due to Long et al. [43]. Essentially, they observed that the monotonicity argument that we applied above to adjacent least fixpoints, can also be applied to a formula of shape /xy.yZ.0(y, Z); by a careful and quite subtle analysis, it can be shown that actually this requires quadratic, not cubic, time to compute. Unfortunately, this does not allow all alternation to be collapsed, but they showed that it generalizes to the extent of proving THEOREM
6. Model-checking is 0(m • «l^^/^^+^).
4.5. Alternation We now look at the notion of alternation in more detail. As we have said, the idea is to count alternations of minimal and maximal fixpoint operators, but to do so in a way that only counts real dependency. The paradigm is 'always eventually' versus 'infinitely often': the 'always eventually' formula
vY.(fiZ.Pv{a)Z)A{a)Y is, using the brute-force model-checker above, really no worse to compute than two disjoint fixpoints, since the inner fixpoint can be computed once and for all, rather than separately on each outer approximant; on the other hand, the 'infinitely often' formula
vY.fiZXPv{a)Z)A{a)Y really does need the full double induction on approximants. The definition of Emerson and Lei takes care of this by observing that the 'eventually' subformula is a closed subformula, and giving a definition that ignores closed subformulae when counting alternations. The stronger notion of Niwifiski, which also has the advantage of being robust under translation to modal equation systems, also observes that, for example, ^JiX.vY.[-]Y A /iZ.[-](X V Z) although it looks like a /x/y//x formula, is morally a /x/y formula, since the inner fixpoint does not refer to the middle fixpoint. The alternation depth referred to in the complexity of model-checking is a measure of alternation that is symmetric in /x and y. It is possible to give algorithms that compute
318
J. Bradfield, C. Stirling
the alternation depth of a formula [25,1,36], and this is how the notion was presented by Emerson and Lei. However, for our purposes it is easier to start from a definition of classes for formula, formalizing the idea of *a /x/v//x formula' etc.; such a definition is analogous to the usual definition of quantifier alternation for predicate logic, an analogy which will be exploited later. This was how Niwinski [50] presented the notion of alternation, and we follow his presentation. Assuming positive form, a formula > is said to be in the classes EQ ^ and IIQ^ iff it contains no fixpoint operators. To form the class D^^^j (respectively n^:{^,, take E,^ ^ ^ Tin ^, and close under the following rules: (1) if 01, >2 € E^^^j (respectively 0,^^,), then 0i v 02,0i A 02, (a)0i, [^]0i € E^^^^j (respectively O,^^,); (2) if 0 G Ef^i (respectively n,^^j), then //Z.0 € E,f^i (respectively vZ.(p e n,^^,); (3) if 0(Z), if € E;^^, (respectively O,^^,), then 0(TA) e E,^^, (respectively O,^^,), provided that no free variable of ^ is captured by a fixpoint operator in 0. If we omit the last clause, we get the definition of 'simple-minded' alternation E„^, that just counts syntactic alternation; if we modify the last clause to read ' . . . provided that xfr is a closed formula', we obtain the Emerson-Lei notion E,f^^. (We write just E^ when the distinctions are not important, or when we are making a statement that applies to all versions.) To get the symmetrical notion of alternation depth of 0, we can define it be the least n such that 0 € E^^j n n^_^,. To make these definitions clear, consider the following examples: • The 'always eventually' formula is 02^, but not ^^2'^, and so its simple alternation depth is 2. However, in the Emerson-Lei notion, it is also E2 ^, since vY.W A {a)Y is n f ^^ and so E2^^^, and by substituting the closed E2^^^ (and in fact Ef ^^) formula /xZ.P V {a)Z for W we get 'always eventually' in E^^^; hence its Emerson-Lei (and Niwinski) alternation depth is 1. • The 'infinitely often' formula is E2 but not 112, in all three definitions, and so has alternation depth 2. • The formula fiX.vY.[~]Y A /iZ.[-](X v Z) is E^^, but not H^^; it is also 11^^^ but not 113 ^, since there are no closed subformulae to bring the substitution clause into play. However, in the Niwinski definition, it is actually E2 ^: vY.[-]Y A M^ is fl, ^ and so E^'^; we can substitute the E|^^ formula /xZ.[-](X v Z) for W without variable capture, and so vy.[-]y A / X Z . [ - ] ( X V Z ) is E^^; and now we can add the outer fixpoint, still remaining in E2 ^. We have already discussed the role alternation depth plays in the complexity of modelchecking. A natural question is whether the hierarchy of properties definable by E,^ formulae is actually a strict hierarchy, or whether the hierarchy collapses at some point so that no further alternation is needed. This problem remained open for a while; by 1990, it was known that E^^ ^ fl^^ [3]. No further advance was made until 1996, when the strictness of the hierarchy was estabhshed by Bradfield [10].
Modal logics and mu-calculi: An introduction
319
THEOREM 7. For every n, there is a formula
formula. Bradfield established this for E,f^, which impHes the result for the other two notions. At the same time, Giacomo Lenzi [41] independently established a slightly weaker hierarchy theorem for E„ ^. Lenzi's proof is technically complex, and the underlying stratagem is not easy. Bradfield's proof appears technically complex, but most of the complexity is really just routine recursion-theoretic coding; the underlying stratagem is quite simple, and in some ways surprising. If one takes first-order arithmetic, one can add fixpoint operators to it, and one can then define a fixpoint alternation hierarchy in arithmetic. A standard coding and diagonalization argument shows that this hierarchy is strict [11]. The trick now is to transfer this hierarchy to the modal mu-calculus. Simply by writing down the semantics, it is clear (give or take some work to deal with the more complex notions of alternation) that if one takes a recursively presented transition system and codes it into the integers, then for a modal formula0 G E ^ , its denotation 1101| is describableby an arithmetic E,^ formula. However, it is also possible, given any arithmetic fixpoint formula x, to build a transition system and a modal formula 0, of the same alternation depth as x. such that ||(/) || is characterized by x • If we take x to be a strict E,^ arithmetic formula, then no n,^ arithmetic formula is equivalent to it, and therefore no n ^ modal formula can be equivalent to 0. The transition system that is constructed is infinite, but by the finite model property, the hierarchy transfers down to the class of finite models. Both proof techniques construct explicit examples of hard formulae. Bradfield's examples are: THEOREMS.
The
H^
^.Xn.vXn-\..
formula ..^lX\ .[c]X\ V (ai)Xi V • • • V (fl,,)A:„
is not equivalent to any Wn formula.
5. More on model-checking In the last section, we saw the approximant approach to model-checking finite systems. In this section, we shall look at some other techniques that have been proposed, and at some of the extensions to deal with classes of infinite processes.
5.1. Local model-checking... The approximant calculation of model-checking is inherently global; calculating a fixpoint approximant involves applying a function over the state space. A variant approach is to use local techniques [65], that is, techniques where to determine the truth of ^ |= 0, one looks at the immediate neighbourhood of s as required by the formula; if there are fixpoints, one
320
/ Bradfield, C. Stirling
will of course move further and further away from s, but one can stop as soon as the truth or falsity of 0 at 5* is established, rather than working with the whole state space. This is attractive when a state is a process expression E belonging to a process calculus, and one doesn't want to build its transition graph explicitly. The formulation adopted was inspired by tableau methods in logic. In outline, suppose we want to check £" [= 0. We start with a sequent E h (p, and then apply rules according to the structure of 0. For example, if 0 = 01 A 02, there is an A-rule which is: £1-01 A 02 £ h 01 £ h 02 and if we get to a sequent ^ h (^)i/^, we apply the ()-rule E —> F. Fhx// The transition E - ^ F is derived from the transition rules for the particular process calculus that E belongs to. If we reach a fixpoint formula, or a variable Z which is bound by ^ Z. T/T, we apply the appropriate fixpoint rule'^
^h^z.yr E\-Z
Ehz Ehf
Thus we build up (or rather down, since the rules grow downwards) a goal-directed tree of sequents to be established. The question is, when do we stop? and how do we know we've succeeded? Obviously we stop on an tz-modality if the process has no a-transitions, in which case E h [«]t/r succeeds and E \- {a)\lr fails; and we stop at £ h P, when we look E up in the proposition valuation to determine success. The key is the treatment of fixpoints. If we get to £ h 0, and we have already seen the same sequent higher up in the tree, then we stop and examine the highest fixed point variable Z between these repeat sequents; the leaf sequent is successful if Z is bound by v and unsuccessful if it is bound by /x. Once we have a finite tree, we propagate success and failure back up to the root via the rules. This proof technique is sound and complete for finite systems. The proof of this fact was another development of the fundamental semantic theorem, for finite models. Indeed, it is probably obvious to the reader (at least the reader who has read Section 4.1) that the construction of a successful tableau gives a well-founded pre-model, and that a wellfounded pre-model is a tableau. This statement needs to be interpreted carefully. In the basic tableau construction, sequents E \- {a)\l/ and E h (pv \lr may occur many times on different branches, with different successors; however this could easily be outlawed, and indeed should be outlawed if one wishes to develop an algorithm from the proof method. A variant perspective on tableau is provided by games [63]. Consider two players Verifier and Refuter. A sequent is now a game position. At £ h 0 A V^ Refuter chooses £ 1 - 0 This is a variant presentation. In the original [65] system, fixpoints were first replaced by constants, and then unfolded. This allowed the termination condition to be expressed simply, but at the expense of efficiency.
Modal logics and mu-calculi: An introduction
321
or EY- \j/ and similarly at £" h [«]> Refuter chooses a possible next position F h- 0 when E - % F. Verifier chooses when the main connective of the sequent is v or {a). A play of a game is just a sequence of sequents. The winning conditions are as for tableaux. For instance Refuter wins E h {a)(t> if E has no «-transitions. A play halts if a position is repeated, and the winner is determined by the highest fixpoint variable. From the fundamental theorem it follows that F |= 0 (£ ^ 0) iff Verifier (Refuter) has a history-free winning strategy for the game which starts at F h 0 . ' ' Model checking games are instances of parity games (which are briefly mentioned later). A history-free winning strategy, unlike a tableau, is linear in the size of the model checking problem. Games provide a basis for efficient model checking when one asks, is it the case ^ |= 0? and why? If the answer is returned with a winning strategy, a user can be the opponent and play against the machine which always wins! This can be helpful in understanding why the property holds - or more importantly, perhaps, in understanding why a desired property fails. The proof rules for tableau mentioned above are guided by the structure of the formulae. However when F is a process expression it also has structure, built from the combinators of the particular process calculus. It is possible, for instance [2], to have rules which are guided by process structure. A simple example is to inductively define the effect of the CCS restriction operator \a on modal mu-calculus formulas. For instance, (0 v •\lf)\a is 0\a V i/r\a and (vZ.(t))\a is vZ.(t)\a. More important is the effect on modalities ([K](l))\a is [K - {a, 'a](l)\a (where ^ is ^'s partner). The idea is that \^ on formulas is an inverse of its application to processes. Parallel composition is more problematic. However one can define a "slicing" operator / F , where F is a process expression operator, on formulae which is an inverse of parallel composition [2]. Tableau rules as follows are thereby justified E\aV-(t) E\-(l)\a
E\F\-(t) E\-(t)/F'
5.2. ... for infinite systems Apart from its locality, another feature of the goal-directed tableau approach is that it can be generalized to use symbolic methods, so allowing the proof of properties of infinite systems (or just large systems). The idea is to use sets of states in sequents, rather than single states; then in the v and ()-rules, an explicit choice function is given; termination happens when we construct a sequent S h Z such that we have already seen a sequent 5" h Z for S' 5 S, with no higher fixpoint intervening; and success involves giving a proof that all the dependency trails are well-founded. This latter is typically done by defining some well-founded measure on processes, and showing that it decreases as one passes through minimal fixpoints, and doesn't increase elsewhere. The canonical such measure is the signature, as described in Section 4.1, but simpler measures may suffice. Thus an infinite state tableau constructs a finite presentation of a well-founded quasi- or pre-model. Details may be found in [8,13], and an example of a Petri net implementation in [9]. ^ ^ A winning strategy is a set of rules which tell a player how to move. A player uses a strategy in a play if all her moves obey the rules in it. A history-free strategy is one which is independent of previous positions in a play. A strategy is winning for a player if she wins every play in which she uses it.
322
/ Bradfield, C. Stirling
5.3. Decidable model-checking for infinite processes The infinite-state tableau system just described makes no claims for decidability: it allows arbitrary mathematical reasoning to be used in establishing the termination and success conditions. An obvious question is to ask what can be done for infinite processes while retaining decidability; the answer is quite limited. Clearly model-checking is undecidable for any Turing-powerful class of processes, since lJiZ,[—]Z expresses the halting property. It turns out to be easy to code halting in the modal mu-calculus, or even in small fragments of linear temporal logic, for many classes that are not Turing-powerful by themselves. For example, if we try to model a register machine as a Petri net, we need to test for zero, which nets cannot do; but if 6^ is a transition that can fire when a particular place is non-empty, then [^]ff expresses the emptiness of that place, and so one can write a mu-calculus formula which says 'the net halts, if we look at those "honest" computations where a branch-on-zero is only taken when the corresponding counter really is zero'. Similarly, it is unnecessary for the registers actually to synchronize with the finite-state control, as we can encode the synchronization into the formula. The upshot of this is that model-checking, even with just one fixpoint, is undecidable for BPP, Basic Parallel Processes - a result which might be surprising, given the decidability of bisimulation for BPP. On the other hand, for BPA, Basic Process Algebra, and for its generalization pushdown processes, model-checking is decidable. This follows from a classical result of Muller and Schupp [48] on the monadic second-order theory of pushdown graphs; but it has been shown by a direct and elegant argument by Burkart and Steffen [16]. They view pushdown processes as 'higher-order' transition graphs. For example, the BPA process system given by A = aBA-\- c and B = bB A-\- c is viewed as a system where the A process does an a transition followed by a ^ transition, understood as a recursive call to B, and returns to its initial state (if B terminates), or does a c to terminate. Now, if we are interested in a particular formula 0, each transition, including the 'higher-order' transitions, is viewed as a predicate transformer on the subformulae of 0: assuming that some subformula hold at the terminal state of the process, which formulae hold at the initial state? Obviously there are only finitely many possibilities, and the result can be calculated by an approximantstyle procedure. If one now plugs into the A transformer the formulae that are true at a real terminal state, one obtains the formulae true of A. Further detail on all these results can be found in the chapter by Burkart et al. later in this Handbook [15].
5.4. Equation systems and efficient local model-checking Recall that in Section 3.1 we presented fixpoints as modal equations. We have also seen mention of vectorial fixpoints, allowing the collapse of adjacent fixpoints of the same sign into one. Combining these ideas, we say a modal equation system is a set {X/y = 0/y | 1 ^ / < m, 1 ^ 7 ^ «/} of equations, where each 0,^ is a modal (no fixpoints) formula in the variables Xij; for each /, the set [Xij = (pij | 1 ^ 7 ^ n,} is a block, and each block is either maximal or minimal; say, wlog, that odd blocks are minimal and even blocks are maximal.
Modal logics and mu-calculi: An introduction
323
There is no semantic ordering within a block, but the set of blocks is partially ordered; the ordering 1 , . . . , w of block indices is a linearization of this partial order. The semantics of such a system is given by treating each block as a vectorial fixpoint of the appropriate sign, with the nesting of fixpoints given by the partial ordering on blocks. By the obvious replacement of higher-numbered right-hand side variables by their defining equations, a modal equation system can be turned into a modal mu-calculus formula defining Xi i. Modal equation systems are a concise way of representing properties, as the direct use of variables referring to equations instead of explicit fixpoint formulae allows sharing between equations. For example, \iX\\ =(t>\\ and X12 = 012 both refer to X21 = 021. then to write the system in linear form we have to write the text of 021 twice, once in each 0i/; and so one can obtain an exponential (in the number of blocks) blowup by going from equation systems to normal modal mu-calculus. However, results about the modal mu-calculus in its linear form normally transfer without cost (save in intellectual effort) to equation systems. A Boolean equation system (BES) is similar, except that the variables are just booleans, not states, and the equations contain only Boolean operators. Thus a BES stands to a formula of Boolean logic with fixpoints*^ as a modal equation system stands to a modal mucalculus formula. A modal equation system together with a modal structure can be turned into a Boolean equation system, by treating a (state, modal variable) pair as a Boolean variable. Perhaps surprisingly, this is sometimes worth doing: BES's have the advantage that they strip away the modal operators and the artificial linearization imposed by text, laying bare the problem of computing alternating fixpoints. BES's have been studied by, among others, Andersen [I], Vergauwen and Lewi [73] and Mader [44]. Lui, Ramakrishnan and Smolka [42] presented a BES-based local model-checking algorithm that is quite short, relatively simple, and of similar efficiency to global model-checking.
6. Automata, games and logic There are other formalisms that are intimately related to fixpoint logics, and in this section we shall give an overview of automata and games, which are the main examples. The relationship benefits both parties: the modal mu-calculus provides simple proofs of some automata-theoretic results, and automata theory is used in the proof of modal mu-calculus results.
6.1. Automata The history of automata-theoretic approaches to verification and associated fields has involved ever more invention of new types of automata, as it becomes apparent that some particular restriction is technically inconvenient and can be lifted without harm. In order to explain the main results, we shall need to introduce several of these varieties; let us start at the beginning. A deterministic automaton on finite words is the usual deterministic finite state machine, accepting finite words over its input alphabet; a run of such an automaton is a path A suitable candidate for the title prepositional mu-calculus.
324
/ Bradfield, C Stirling
through the machine matching the input, and it accepts if the final state is accepting. A nondeterministic automaton on finite words is the usual notion, namely that the transition function may specify more than one successor state for a given state and input letter; a run of such an automaton requires choosing one successor at each non-deterministic choice, and the automaton accepts its input if some run accepts that input. There are now several orthogonal generalizations of this idea. Firstly, we may allow infinite words as well as finite words. In this case, we must specify acceptance conditions which determine when an infinite run is successful. There are many of these; the most important are as follows. A BUchi acceptance condition specifies a set G of states, such that we infinitely often meet a G-state on the run (mnemonic: a green light must flash infinitely often). A Rabin acceptance condition specifies k sets /?/ and k sets G,, and requires that for some /, we see G, infinitely often, and don't see /?/ infinitely often (mnemonic: k sets of lights; there must be one set where we see green often and don't see red often). In a Mostowski or parity acceptance condition, each state of the automaton is assigned an integer rank, and the highest rank occurring infinitely often must be even (there is no general agreement on highest/lowest or even/odd in this definition). In the next dimension, we may feed the automata trees rather than words. To start with, assume that the branching degree is fixed at n. The automaton transition function now specifies n successors, and notionally the automaton splits into n copies as it passes to the successors, so a run is a tree matching the input tree. The run is successful if all paths through the run satisfy the acceptance condition, which is specified as above. In the case of a non-deterministic tree automaton, the transition is chosen non-deterministically, but each transition specifies n successors. We can generalize this to automata on trees whose branching degree varies according to the label, or to trees whose branching degree is freely variable (so-called amorphous automata). Finally, we can complicate the success conditions as follows: instead of saying just that every path through the run accepts, we can say that the subrun rooted at a node n is accepted if some Boolean combination, depending on the state, /({7^}) holds, where Ti is the statement that the subrun rooted at «'s /th child is accepted, and that the run is accepted if the subrun starting at the root is accepted, provided the global acceptance condition is met. The global acceptance condition is most easily formulated game-theoretically, as we shall see later, but one can think of it in mu-calculus terms as being: there must exist a choice function which for each node selects a satisfying assignment for /({T/}), and thus selects some children; then every path through the selected nodes must meet the Rabin etc. acceptance condition. These are alternating automata. Warning: this alternation is that between 3 and V; nothing to do with fixpoint alternation! If the Boolean combination is just conjunction, /({T,}) = A/ ^/^ ^^ g^^ a normal tree automaton; if it is disjunction, we get a tree automaton that accepts if some path accepts, rather than if all paths accept, giving a form of non-determinism. It is probably not much of a surprise that: 9. Modal mu-calculus formulae are equivalent to alternating amorphous parity automata (on trees).
THEOREM
The equivalence is simple: a diamond modality corresponds to a node whose Boolean success combination is disjunction, a box modality to one whose success combination is
Modal logics and mu-calculi: An introduction
325
conjunction; and if one assigns ranks to the fixpoint operators that are consistent with subformula inclusion, with even ranks for maximal fixpoints and odd for minimal, the parity condition asserts that the obviously induced tree pre-model is well-founded. A rather more surprising fact is THEOREM
10. Ordinary Rabin automata are equivalent to alternating parity automata
{on trees). It is obvious that a Rabin automaton can be turned into an alternating parity automaton. However, the reverse construction is not so easy. It is quite easy to turn a parity condition into a Rabin condition, but it is harder to remove the alternation, and a large size blowup is required. In terms of modal mu-calculus formulas this is precisely the transformation into automaton normal form, anf, mentioned earlier, which has no V/3 alternation. As a corollary, we have THEOREM
11. Rabin automata are equivalent to modal mu-calculus formulae {on trees).
The theory of automata on infinite objects is highly developed. Wolfgang Thomas [70] provides a survey of the entire area, and Niwinski's [51] is a fundamental study of automata and fixpoint logics, including much useful background material. Here we shall just mention a few more of the immediate connections with modal mu-calculus. • In Rabin's original paper, one of the hardest lemmas was proving that Rabin automata are closed under complementation. Given the above, it is now 'obvious', since modal mu-calculus is closed under complementation by definition. • Rabin automata have the nice property that if they accept some tree, they accept some regular tree: that is, a tree that is the unravelling of a finite system. This gives the finite model property of the modal mu-calculus, as we have seen. • The emptiness problem for Rabin automata is decidable. Hence one can model-check by forming the product of the system with the Rabin automaton, and checking for emptiness, as we have also seen. We have mentioned mostly Rabin automata. Biichi automata on trees are strictly less expressive than Rabin automata. However, on words, parity, Rabin and Biichi automata are equivalent, and one has 12. Rabin/BUchi/parity automata on infinite words are equivalent to linear time mu-calculus formulae.
THEOREM
The fact that Biichi and parity automata are equivalent on words is the automatatheoretic analogue of the fact that the fixpoint alternation hierarchy collapses in linear-time mu-calculus. On trees, alternating Biichi automata correspond to 112 ^^^^^ mu-calculus formulae. 6.2. Monadic second-order logic To continue the story, we bring in monadic second-order logic, studied by Rabin in his original paper. SnS is the monadic second-order logic of the «-ary tree, so that elements
326
/ Bradfield, C Stirling
are nodes of the tree, the n successor relations are in the logic, first-order quantification over nodes is allowed, and quantification over sets, but not relations, of nodes is allowed. Rabin showed that SnS is equivalent to Rabin automata. It follows that on trees, SnS is equivalent to modal mu-calculus. This is a very curious result, since at first sight, SnS offers much more power. (It is obvious that mu-calculus is a sublogic of SnS since the definitions of greatest and least fixed point are monadic second-order definitions.) For one thing, we can talk about ancestors and cousins of nodes; for another, arbitrary secondorder quantification looks more powerful than just fixpoints. But in fact neither of these gives more power. If we consider transition systems rather than trees, David Janin and Igor Walukiewicz [33,34] have recently developed appropriate generalizations of this theory. We already know that modal mu-calculus respects bisimulation; it now turns out that THEOREM 13. A formula in the monadic second-order language of transition systems is expressible in modal mu-calculus exactly if it respects bisimulation.
6.3. Games Games have played an important role in many areas of mathematics, but especially in logic. The so-called Ehrenfeucht-Frai'sse games characterize first-order logic, and extensions and restrictions of them characterize various extensions and restrictions of first-order logic. In a similar manner, we can define games for the modal mu-calculus. Technically, such games are fairly trivial reformulations of automata or tableaux; but they have good explanatory power, and, more surprisingly, provide useful approaches to model-checking. Owing to the extensive use of games in finite model theory, game formulations of mu-calculus problems assist in exploring the close relationships with finite model theory. A parity game is played by two players, Abelard and Eloise.^'^ An arena for the game is a graph, in which each node is labelled as either an Abelard or Eloise node, and also labelled with a rank, as in parity automata. A play of the game consists of a sequence of moves in which the appropriate player chooses a successor of the current node; Eloise wins if the play ends in Abelard getting stuck, or if the play is infinite and the highest rank occurring infinitely often is even. It may be convenient to designate certain nodes as immediate Abelard/Eloise wins, for example to deal with atomic propositions in the mu-calculus. A strategy for one player is a function which given a partial play from which the player is due to move, gives the next move. A winning strategy is one which if followed guarantees a win. A strategy is history-free (or memoryless) if it depends only on the current position in the game. ^^ Game presentations are plagued by the variety of names for the players. In Ehrenfeucht-Fraisse games, they are traditionally called Player I and Player II. In finite-model theory they are called Duplicator and Spoiler, but the meaning of these names does not transfer happily to all situations. Other possibilities are Player and Opponent, or Player 0 and Player 1, or for model checking Verifier and Refuter. Our choice, introduced by Wilfrid Hodges, has the advantage of being formally meaningless, but with a mnemonic for remembering which player is which in appUcations: Vbelard and Eloise.
Modal logics and mu-calculi: An introduction
327
It should be obvious that, for example, modal mu-calculus model-checking can be viewed as a parity game from the discussion in the previous section: the game graph comprises pairs of states and formulae, with transitions given by the dependencies (that is, it is a quasi-model, in the terminology of Section 4.1). Abelard owns the conjunction, box, and maximal fixpoint nodes; Eloise the others; the ranks are assigned as for parity automata. The statement 'Eloise has a winning strategy' is equivalent to the statement that the corresponding alternating parity automaton has an accepting run is equivalent to the statement that the structure satisfies the formula. Equipping the structure with a choice function corresponds to giving Eloise a history-free strategy; and so by the fundamental theorem and duality, a player has a winning strategy iff they have a history-free winning strategy.
References [1] H.R. Andersen, Verification of temporal properties of concurrent systems, DAIMI PB-445, Computer Science Dept., Aarhus University (1993). [2] H.R. Andersen, C. Stirling and G. Winskel, A compositional proof system for the modal jjL-calculus, Proc. 9th IEEE Lies (1994), 144-153. [3] A. Arnold and D. Niwinski, Fixed point characterization of Biichi automata on infinite trees, J. Inform. Process. Cybernet. EIK 26 (1990), 451-^59. [4] J.W. de Bakker, Mathematical Theory of Program Correctness, Prentice-Hall, Englewood Cliffs, NJ (1980). [5] B. Banieqbal and H. Barringer, Temporal logic with fixed points. Temporal Logic in Specification, Lecture Notes in Comput. Sci. 398 (1989), 62-74. [6] H. Barringer, R. Kuiper and A. Pnueli, Now you may compose temporal logic specifications, Proc. 16th ACM STOC (1984), 51-63. [7] H. Bekic, Definable operations in general algebras, and the theory of automata and flow charts. Programming Languages and Their Definition, Lecture Notes in Comput. Sci. 177 (1984). [8] J.C. Bradfield, Verifying Temporal Properties of Systems, Birkhauser, Boston (1991). [9] J.C. Bradfield, A proof assistant for symbolic model-checking, Proc. CAV '92, Lecture Notes in Comput. Sci. 663 (1993), 316-329. [10] J.C. Bradfield, The modal mu-calculus alternation hierarchy is strict, Theoret. Comput. Sci. 195 (1997), 133-153. [11] J.C. Bradfield, Simplifying the modal mu-calculus alternation hierarchy, Proc. STACS '98, Lecture Notes in Comput. Sci. 1373 (1998), 39-49. [12] J.C. Bradfield, J. Esparza and A. Mader, An effective tableau system for the linear time mu-calculus, Proc. ICALP '96, Lecture Notes in Comput. Sci. 1099 (1996), 98-109. [13] J.C. Bradfield and C.P. Stirling, Local model checking for infinite state spaces, Theoret. Comput. Sci. 96 (1992), 157-174. [14] J.R. Biichi, On a decision method in restricted second order arithmetic. Logic, Methodology and Philosophy of Science, Proc. 1960 Congress, Stanford Univ. Press, Stanford, CA (1962), 1-11. [15] O. Burkart, D. Caucal, F. Moller and B. Steffen, Verification on infinite structures. Handbook of Process Algebra, J.A. Bergsta, A. Ponse and S.A. Smolka, eds, Elsevier, Amsterdam (2001), 545-623. [16] O. Burkart and B. Steffen, Model checking for context-free processes, Proc. CONCUR '92, Lecture Notes in Comput. Sci. 630 (1992), 123-137. [17] E.M. Clarke and E.A. Emerson, Design and synthesis of synchronization skeletons using branching time temporal logic. Lecture Notes in Comput. Sci. 131 (1981), 52-71. [18] E.M. Clarke, E.A. Emerson and A.P Sistla, Automatic verification of finite-state concurrent systems using temporal logic specifications, ACM Trans. Programming Languages and Systems 8 (1986), 244-263. [19] M. Dam, CTL* and ECTL* as fragments of the modal mu-calculus, Theoret. Comput. Sci. 126 (1994), 77-96. [20] A. de Morgan, A Budget of Paradoxes, Longmans, Green, and Co., London (1872).
328
/ Bradfield, C Stirling
[21] E.A. Emerson, Temporal and modal logic. Handbook of Theoretical Computer Science, Vol. B., J. van Leeuwen, ed., Elsevier (1990), 995-1072. [22] E.A. Emerson and E.M. Clarke, Characterizing correctness properties ofparallel programs using fixpoints, Procs ICALP '80, Lecture Notes in Comput. Sci. 85 (1980), 169-181. [23] E.A. Emerson and C.S. Jutla, Tree automata, mu-calculus and determinacy, Proc. 32nd IEEE FOCS (1990), 368-377. [24] E.A. Emerson, C.S. Jutla and A.P. Sistla, On model checking for fragments of p-calculus, Proc. CAV '93, Lecture Notes in Comput. Sci. 697 (1993), 385-396. [25] E.A. Emerson and C.-L. Lei, Efficient model checking in fragments of the propositional mu-calculus, Proc. 1st IEEE L i e s (1986), 267-278. [26] M.J. Fischer and R.E. Ladner, Propositional dynamic logic of regular programs, J. Comput. System Sci. 18 (1979), 194-211. [27] R. Royd, Assigning meanings to programs. Mathematical Aspects of Computer Science, J.T. Schwartz, ed., Amer. Math. Soc., Providence, RI (1967), 19-32. [28] Y. Gurevich and L. Harrington, Trees, automata and games, Proc. 14th ACM STOC (1982), 60-65. [29] D. Harel, A. Pnueli and J. Stavi, Propositional dynamic logic of context-free programs, Proc. 22nd IEEE FOCS (1981), 310-321. [30] M. Hennessy and R. Milner, On observing nondeterminism and concurrency, Proc. ICALP '80, Lecture Notes in Comput. Sci. 85 (1980), 295-309. [31] C.A.R. Hoare, An axiomatic basis for computer programming, Comm. ACM 12 (1969), 576-580. [32] H. Huttel, SnS can be modally characterized, Theoret. Comput. Sci. 74 (1990), 239-248. [33] D. Janin and I. Walukiewicz, Automata for the p-calculus and related results, Proc. MFCS '95, Lecture Notes in Comput. Sci. 969 (1995), 552-562. [34] D. Janin and I. Walukiewicz, On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic, Proc. CONCUR '96, Lecture Notes in Comput. Sci. 1119 (1996), 263-277. [35] R. Kaivola, On modal mu-calculus and Biichi tree automata. Inform. Process. Lett. 54 (1995), 17-22. [36] R. Kaivola, Using automata to characterise fixpoint temporal logics, Ph.D. Thesis, University of Edinburgh (1997). [37] D. Kozen, Results on the propositional mu-calculus, Theoret. Comput. Sci. 27 (1983), 333-354. [38] D. Kozen, A finite model theorem for the propositional p -calculus, Studia Logica 47 (1988), 233-241. [39] D. Kozen and R. Parikh, An elementary proof of the completeness ofPDL, Theoret. Comput. Sci. 14 (1981), 113-118. [40] L. Lamport, Proving the correctness of multiprocess programs, IEEE Trans. Software Engrg. 2 (1977), 125-143. [41] G. Lenzi, A hierarchy theorem for the mu-calculus, Proc. ICALP '96, Lecture Notes in Comput. Sci. 1099 (1996), 87-109. [42] X. Liu, C.R. Ramakrishnan and S.A. Smolka, Fully local and efficient evaluation of alternating fixed points, Proc. TACAS '98, Lecture Notes in Comput. Sci. 1384 (1998), 5-19. [43] D. Long, A. Browne, E. Clarke, S. Jha and W. Marrero, An improved algorithm for the evaluation of fixpoint expressions, Proc. CAV '94, Lecture Notes in Comput. Sci. 818 (1994), 338-350. [44] A. Mader, Verification of modal properties using Boolean equation systems, Ph.D. Thesis, Technical University of Munich (1997). [45] Z. Manna and A. Pnueh, Formalization of properties of recursively defined functions, Proc. ACM STOC (1969), 201-210. [46] Z. Manna and A. Pnueli, How to cook a temporal proof system for your pet language, Proc. 10th ACM POPL(1983), 141-154. [47] R. Milner, A Calculus of Communicating Systems, Lecture Notes in Comput. Sci. 92 (1980). [48] D. Muller and P. Schupp, The theory of ends, pushdown automata and second order logic, Theoret. Comput. Sci. 37 (1985), 51-75. [49] P. Niebert, A v-calculus with local views for systems of sequential agents, Proc. MFCS '95, Lecture Notes in Comput. Sci. 969 (1995), 563-573. [50] D. Niwiriski, On fixed point clones, Proc. ICALP '86, Lecture Notes in Comput. Sci. 226 (1986), 464-473. [51] D. Niwiriski, Fixed point characterization of infinite behavior offinitestate systems, Theoret. Comput. Sci. 189 (1997), 1-69.
Modal logics and mu-calculi: An introduction
329
[52] D. Park, Fixpoint induction and proofs of program properties. Machine Intelligence 5 (1969), 59-78. [53] D. Park, Concurrency and automata on infinite sequences. Lecture Notes in Comput. Sci. 104 (1981), 167183. [54] W. Penczek, Temporal logics for trace systems, Intemat. J. Found. Comput. Sci. 4 (1) (1993), 31-67. [55] A. Pnueli, Temporal semantics of concurrent programs, Theoret. Comput. Sci. 27 (1983), 333-354. [56] V. Pratt, Semantical considerations of Floyd-Hoare logic, Proc. 16th IEEE FOCS (1976), 109-121. [57] V. Pratt, A near-optimal method for reasoning about action, J. Comput. System Sci. 20 (1980), 231-254. [58] V. Pratt, A decidable mu-calculus, Proc. 22nd IEEE FOCS (1982), 421-427. [59] M.O. Rabin, Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141 (1969), 1-35. [60] M.O. Rabin, Weakly definable relations and special automata. Mathematical Logic and Foundations of Set Theory, Y. Bar-Hillel, ed., North-Holland, Amsterdam (1970), 1-23. [61] A.P Sistla and E.M. Clarke, Complexity of propositional temporal logics, J. ACM 32 (1986), 733-749. [62] C. Stirling, Modal and temporal logics. Handbook of Logic in Computer Science, Vol. 2, S. Abramsky, D. Gabbay and T. Maibaum, eds, Oxford University Press (1991), 477-563. [63] C. Stirling, Local model checking games, Proc. Concur '95, Lecture Notes in Comput. Sci. 962 (1995), 1-11. [64] C. Stirling, Modal and temporal logics for processes. Logics for Concurrency, Lecture Notes in Comput. Sci. 1043(1996), 149-237. [65] C. Stirling and D. Walker, Local model checking in the modal mu-calculus, Theor. Comput. Sci. 89 (1991), 161-177. [66] C. Stirling and D. Walker, CCS, liveness, and local model checking in the linear time mu-calculus, Proc. First International Workshop on Automatic Verification Methods for Finite State Systems, Lecture Notes in Comput. Sci. 407 (1990), 166-178. [67] R. Streett, Propositional dynamic logic of looping and converse, Proc. 13th ACM STCX^ (1981), 375-383. [68] R.S. Streett and E.A. Emerson, An automata theoretic decision procedure for the propositional mu-calculus. Inform, and Comput. 81 (1989), 249-264. [69] PS. Thiagarajan, A trace based extension of linear time temporal logic, Proc. 9th IEEE LICS (1994), 438447. [70] W. Thomas, Languages, automata, and logic. Handbook of Formal Language Theory, Vol. Ill, G. Rozenberg and A. Salomaa, eds. Springer-Verlag, New York (1998), 389-455. [71] M.Y. Vardi, A temporal fixpoint calculus, Proc. 15th POPL (1988), 250-259. [72] M.Y. Vardi and P. Wolper, Yet another process logic. Logics of Programs, Lecture Notes in Comput. Sci. 164 (1983), 501-512. [73] B. Vergauwen and J. Lewi, Efficient local correctness checking for single and alternating Boolean equation systems, Proc. ICALP '94, Lecture Notes in Comput. Sci. 820 (1994), 302-315. [74] I. Walukiewicz, Completeness ofKozen's axiomatisation of the propositional p.-calculus, Proc. 10th IEEE LICS (1995), 14-24. [75] I. Walukiewicz, Notes on the propositional p-calculus: Completeness and related results, BRICS Notes Series BRICS-NS-95-l,http://www.brics.dk/BRICS/NS/95/l/BRICS-NS-95-l/index.html.
Subject index alternation (in automata), 324 alternation depth, 318 alternation, fixpoint, 318 anf, 314 annotation, 311 ^^^ approximant, 303 automaton normal form, 314 choice function, 311
CTL, 298 disjunctive formula, 314 __^ equation system, 322
filtration,
fairness, 309 299
330 games, 320 Hennessy-Milner Logic, 298 HML,298 liveness, 306
J. Bradjield, C. Stirling pre-model, well-founded, 311 Propositional Dynamic Logic, 298 quasi-model, 311 safety, 306 signature, 312
model-checking, complexity of, 315 tableau, 319 PDL, 298 pre-model, 311
unfolding, 303
CHAPTER 5
Process Algebra with Recursive Operations Jan A. Bergstra^'^, Wan Fokkink^ Alban Ponse^'^ ' CWI, Kruislaan413, 1098 SJ Amsterdam, The Netherlands http://www. cwi. nl ^ Utrecht University, Department of Philosophy, Heidelberglaan 8, 3584 CS Utrecht, The Netherlands http./Avww.phil. uu. nl/eng/home. html ^ University of Amsterdam, Programming Research Group, Kruislaan 403, 1098 SJ Amsterdam, The Netherlands http://www. science, uva. nl/re search/prog E-mails: [email protected], [email protected], [email protected]
Contents 1. Introduction 2. Preliminaries: Axioms and operational semantics 2.1. ACP-based systems 2.2. Transition rules and operational semantics 2.3. Recursive specifications 3. Axiomatisation of the binary Kleene star 3.1. Preliminaries 3.2. Completeness 3.3. Irredundancy of the axioms 3.4. Negative results 3.5. Extensions of BPA*(A) 4. Axiomatisations of other iterative operations 4.1. Axiomatisation of no-exit iteration 4.2. Axiomatisation of multi-exit iteration 4.3. Axiomatisation of prefix iteration 4.4. Axiomatisation of string iteration 4.5. Axiomatisation of flat iteration 5. Expressivity results 5.1. Expressivity of the binary Kleene star 5.2. Expressivity of multi-exit iteration 5.3. Expressivity of string iteration 5.4. Expressivity of flat iteration 6. Non-regular recursive operations 6.1. Process algebra with a push-down operation
335 338 338 341 344 345 346 347 354 355 357 358 358 359 361 363 363 365 365 370 371 372 374 375
HANDBOOK OF PROCESS ALGEBRA Edited by Jan A. Bergstra, Alban Ponse and Scott A. Smolka © 2001 Elsevier Science B.V. All rights reserved
333
334 6.2. Expressing a stack 6.3. Undecidability results 7. Special constants 7.1. Silent step and fairness 7.2. Empty process Acknowledgements References Subject index
J A. Bergstra et aL 378 381 382 383 384 385 385 388
Abstract This chapter provides an overview of the addition of various forms of iteration, i.e., recursive operations, to process algebra. Of these operations, (the original, binary version oO the Kleene star is considered most basic, and an equational axiomatisation of its combination with basic process algebra is explained in detail. The focus on iteration in process algebra raised interest in a number of variations of the Kleene star operation, of which an overview, including various completeness and expressivity results, is presented. Though most of these variations concern regular (iterative) operations, also the combination of process algebra and some non-regular operations is discussed, leading to undecidability and stronger expressivity results. Finally, some attention is paid to the interplay between iteration and the special process algebra constants representing the silent step and the empty process.
Process algebra with recursive operations
335
1. Introduction In process algebra, a (potentially) infinite process is usually represented as the solution of a system of guarded recursive equations, and proof theory and verification tend to focus on reasoning about such recursive systems. Although specification and verification of concurrent processes defined in this way serve their purposes well, recursive operations give a more direct representation and are easier to comprehend. The Kleene star * can be considered as the most fundamental recursive operation. In process algebra, the defining equation for the binary Kleene star reads x*j = x-(x*y) + >; where • models sequential composition and -h models non-deterministic choice (• binds stronger than +). In terms of operational semantics, the process x^'y chooses between x and J, and upon termination of x has this choice again. For example, the expression a*b for atomic actions a and b can be depicted by
V
where yj expresses successful termination. This chapter discusses the Kleene star in the setting of process algebra, and considers some derived recursive operations, with a focus on axiomatisations and expressiveness hierarchies. In the summer of 1951, S.C. Kleene was supported by the RAND Corporation, leading to Research Memorandum "Representation of Events in Nerve Nets and Finite Automata" [52]. The material in that paper, based on the fundamental paper [59],* was republished under the same title five years later [53]. In this seminal work, Kleene introduced the binary operation * for describing 'regular events'. He defined regular expressions, which correspond to finite automata, and gave algebraic transformation rules for these, notably £'*F = £ ( £ * F ) v F (£'*F being the iterate of E on F). Kleene noted the correspondence with conventions of algebra, treating £ v F as the analogue of £ -h F, and F F as the product of E and F. In 1958, Copi, Elgot, and Wright [30] showed interest in the results from [53]. However, they judged Kleene's theorems on analysis^ and synthesis^ obscured both by the complexity of his basic concepts and by the nature of the elements used in his nets. They introduced ' Kleene judged the theory for nerve nets with circles in [59] (McCuUoch and Pitts, 1943) to be obscure, and proceeded independently. He came up with "regular events" and the major correspondence results in automata theory. Theorem 5, stating that finite automata model regular events. ^ Theorem 3, stating that each regular event can be described by a finite automaton ("nerve net").
336
JA. Bergstra et al
simpler and stronger nets (in a sense weakening Kleene's synthesis result, but stating that this "brings the essential nature of the result into sharper focus"), and simpler operations. In particular they introduced a unary * operation "[...] because the operation Kleene uses seems "essentially" singulary and because the singulary operation simplifies the algebra of regular events. It should be noted that the singulary and binary star operations are interdefinable." [30, p. 195] This contradicts Kleene's original argument in [52, p. 50] that the length of an event is at least one, and that for this reason he did not define £"* as a unary operation. Four years later, Redko [69] proved that there does not exist a sound and complete finite equational axiomatisation for regular expressions. (This proof was simplified and corrected by Pilling; see [31, Chapter 11].) In 1966, Salomaa [70] presented a sound and complete finite axiomatisation for regular expressions, with as basic ingredient an implicational axiom dating back to Arden [9], namely (in process algebra notation): x = {y'X) + z=^x = y''z if y does not have the so-called empty word property. According to Kozen [57], this last property is not algebraic, in the sense that it is not preserved under action refinement; he proposed two alternative implicational axioms that do not have this drawback. Krob [58] settled two conjectures by Conway [31], to obtain an infinite sound and complete equational axiomatisation for regular expressions. Bloom and Esik [25] developed an alternative infinite equational axiomatisation for regular expressions, within the framework of iteration theories. In 1984, Milner [62] was the first to consider the unary Kleene star in process algebra, modulo strong bisimulation equivalence [66]. In contrast with regular expressions, this setting is not sufficiently expressive to describe all regular (i.e., finite-state) processes. Moreover, the merge operator jc || y [60] that executes its two arguments in parallel, and which is fundamental to process algebra, cannot always be eliminated from process terms in the presence of the Kleene star. Milner presented an axiomatisation for the unary Kleene star in strong bisimulation semantics, being a subset of Salomaa's axiomatisation, and asked whether his axiomatisation is complete. Fokkink [39] solved this question for noexit iteration jc*(5, where the special constant 8, called deadlock, does not exhibit any behaviour; since 5 blocks the exit, jc*5 executes JC infinitely often. Bloom, Esik, and Taubner [26] presented a complete axiomatisation for regular synchronisation trees modulo strong bisimulation equivalence, within the framework of iteration theories. Milner also asked for a characterisation of those recursive specifications that can be described modulo strong bisimulation semantics in process algebra with the unary Kleene star. Bosscher [28] solved this question in the absence of the deadlock. The two questions by Milner in their full generality remain unsolved. The unary Kleene star naturally gives rise to the empty process [74], which does not combine well with the merge operator. Therefore, Bergstra, Bethke, and Ponse [16,17] returned in 1993 to the binary version x*y of the Kleene star in process algebra, naming the operator after its discoverer. Troeger [73] introduced a process specification language
Process algebra with recursive operations
337
with iteration, in which he introduced a striking axiom for the binary Kleene star, here presented in process algebra notation:
Fokkink and Zantema [38,44] gave an affirmative answer to an open question from [17], namely, that the defining axiom and Troeger's axiom for the binary Kleene star, together with x * ( y . z ) = (x*y)-z
and the five standard axioms on + and • for basic process algebra [19], provide an equational characterisation of strong bisimulation equivalence. Corradini, De Nicola, and Labella studied the unary Kleene star in the presence of deadlock modulo resource bisimulation equivalence. In [32,33] they presented a complete axiomatisation based on Kozen's conditional axioms. In [34] they came up with a complete equational axiomatisation including Troeger's axiom. Aceto, Fokkink, and Ingolfsdottir [4] proved that a whole range of process semantics coarser than strong bisimulation do not allow a finite equational characterisation of the binary Kleene star. Furthermore, Sewell [72] showed that there does not exist a finite equational characterisation of the binary Kleene star modulo strong bisimulation equivalence in the presence of the deadlock <5, due to the fact that {a^Y3 is strongly bisimilar to fl*5 for positive integers k. Several variations of the binary Kleene star were introduced, to obtain particular desirable properties. • In order to increase the expressive power of the binary Kleene star in strong bisimulation semantics, Bergstra, Bethke, and Ponse [16] proposed multi-exit iteration {x\, ...,XkT(y\, ...,yk)fov positive integers k, with as defining equation
(xi,...,xkTiyx,...,n) = -^1 • (U2,...,xk.x\T{y2. ..-.yk,y\)) + >'i. Aceto and Fokkink [1] presented an axiomatic characterisation of multi-exit iteration in basic process algebra, modulo strong bisimulation equivalence. • Prefix iteration (similar to the delay operation from Hennessy [51]) is obtained by restricting the left-hand side of the binary Kleene star to atomic actions. Aceto, Fokkink, and Ingolfsdottir [5,36] presented finite equational characterisations of prefix iteration in basic CCS [60], modulo a whole range of process semantics. • String iteration [7] is obtained by restricting the left-hand side of the binary Kleene star to non-empty finite strings of atomic actions. Aceto and Groote [7] presented an equational characterisation of string iteration in basic CCS, modulo strong bisimulation equivalence. • Bergstra, Bethke, and Ponse [16] introduced^^r iteration, which is obtained by restricting the left-hand side of the binary Kleene star to sums of atomic actions. Unlike the binary Kleene star, the merge operator can be eliminated from process terms in the presence of flat iteration. In [48], van Glabbeek presented a complete finite equational
338
J.A. Bergstra et al.
characterisation of flat iteration in basic CCS extended with the silent step r [60], modulo four rooted weak bisimulation semantics that take into account the silent nature of the special constant r (identifying xx and x). This chapter also concerns expressivity of (subsystems of) the algebra of communicating processes (ACP) [19] extended with the constant r and abstraction operators [20], and enriched with the binary Kleene star or variants thereof. The r, which represents a silent step, in combination with abstraction operators, which rename actions into r, enables one to abstract from internal behaviour. In weaker semantics that identify xx and x, each regular process can be specified in ACPr (i.e., ACP with abstraction) and the binary Kleene star, using only handshaking (i.e., two-party communication) [22] and some auxiliary actions. Furthermore, in such a semantics, each computable process can be specified in ACPr with abstraction and a single recursive, non-regular operation, using only handshaking and some auxiliary actions. This chapter is set up as follows. Section 2 introduces the preliminaries. Section 3 contains an exposition on axiomatisations for the binary Kleene star, while Section 4 discusses axiomatisations for related iterative operations. Section 5 compares the expressivity of these iterative operations, and Section 6 studies the expressivity of some non-regular recursive operations. Finally, Section 7 touches upon topics such as fairness and the empty process.
2. Preliminaries: Axioms and operational semantics In this section we recall various process algebra axiom systems, structural operational semantics, behavioural equivalences, and recursive specifications. For a detailed introduction to these matters see, e.g., Baeten and Weijland [15].
2.1. ACP-based systems Let A be a finite set of atomic actions a,b,c,..., and let 5 be a constant not in A. We write As for A U {5}. Let furthermore _ | _ : A^ x A<5 -> A<5 be a communication function that is commutative, a\b — b\a
for all «, Z? € A5,
associative, a\{b\c)
= {a\b)\c
for all a,b,ce
A^,
and that satisfies 8 \ a = 8 for all a e As. The communication function | will be used to define communication actions: in the case that a \b = c e A,the simultaneous execution of actions a and b results in communication action c. The actions in A and the communication function | can be regarded as parameters of the process algebra axiom systems that are presented below.
Process algebra with recursive operations
339
The process algebraic framework ACP(A, |, r) stands for a particular signature over fixed A and communication function |, and a set of axioms over this signature. Let V denote the set of process terms over this signature: sorts:
A
(the given, finite set of atomic actions), (the set of process terms; A c P),
V operations: -{-:V xV -^ V
(non-deterministic choice or sum).
'\VxV->V
(sequential composition).
\\:VxV->V
(merge, parallel composition).
IL
(left merge). (communication merge, extending the given communication function). (encapsulation, // c A),
:Vxr->V
\'.VxV-^V dH'-V^V Ti\V->V constants: 5 € P xeV
(abstraction, / c A), (deadlock), (silent step).
Intuitively, an action a represents indivisible behaviour, 8 represents inaction, and r represents invisible internal behaviour. Moreover, P -\- Q executes either P or Q, P - Q first executes P and at its successful termination proceeds to execute Q, and P \\ Q executes P and Q in parallel allowing communication of actions from P and Q. The operators P ^ Q and P I Q both capture part of the behaviour of P \\ Q: P |L Q takes its first transition from P, while the first transition of P | Q is a communication of actions from P and Q. Finally, in 9//(P) all actions from // in P are blocked, while in r/(P) all actions from / in P are renamed into r. We take • to be the operation that binds strongest, and -I- the one that binds weakest. As usual in algebra, we tend to write xy instead of x • y. For • e {+, •, ||, |} we will assume that expressions PQ D • • • D P/? associate to the right. Furthermore, for /: ^ I we define x^"^' as jc -x^, and jc^ as JC. In Table 1 the axioms of the system ACP(A, |, r) are collected. Note that + and • are associative, and that + is moreover commutative and idempotent. In the case that a\(b\c)
= 8 for all a, Z?, c G A,
while I itself defines a communication, we speak of handshaking. We will study the following subsystems of ACP(A, |, r): • BPA(A). The signature of BPA(A) contains the elements of A, non-deterministic choice, and sequential composition. The axioms of BPA(A) are (A1)-(A5). • BPA5(A). The signature of BPA5(A) is the signature of BPA(A) extended with the deadlock. The axioms of BPA5(A) are (A1)-(A7).
340
J.A. Bergstra et al Table 1 The axioms for ACP(A, |, r), where a,be A^^ and H,I C,A (Al) (A2) (A3) (A4) (A5) (A6) (A7) (CI) (C2) (C3) (CMl) (CM2) (CMS) (CM4) (CM5) (CM6) (CM7) (CMS) (CM9) (Dl) (D2) (D3) (D4) (Bl) (Til) (TI2) (TI3) (TI4)
x-\'y x + iy-^z)
:zz V+JC
= = {x + v)z = {xy)z = jc + 5 = 8x = a\b = {a\b)\c = 6\a = x\\y = at X = ax IL V = (^ + v) t z = ax 1 b = a 1 bx = ax 1 by = {X -\-y)\z = x\{y + z) = ^Hio) = a//(«) = a//(^ + v) = ^Hixy) = XX = Tiia) = riia) = T/ix + y) = T^lixy) = X -l-JC
(x + v) + z X
xz 4- yz x(yz) X
8 b\a a\ib\c) 8 {x I v + y IL x)-}-x\\y ax o(x II y ) AT IL z + V (L z
(a 1 b)x (a 1 b)x (a \ b){x II y) x\z-^y\z x\y + x\z a ifa^H 8 if aeH 9//(^) + 9//(v) dH(x)dH(y) X
a if a ^ I T ifael T/ix) + Tj(y) Tj{x)rj(y)
• PA(A). The signature of PA(A) is the signature of BPA(A) extended with the merge and left merge. The axioms of PA(A) are (A1)-(A5), (CM2)-(CM4) (with a ranging over A), and (Ml)
x\\y = x I y-^y
I
x.
• PA5(A). The signature of PA5(A) is the signature of PA(A) extended with the deadlock. The axioms of PA(A) are (A1)-(A7), (Ml), and (CM2)-(CM4) (with a ranging over A^). • ACP(A, I). The signature of ACP(A, |) is the signature of ACP(A, |, r) w/r/z6>Mr the silent step and abstraction operators. The axioms of ACP(A, |) are (A1)-(A7), (CF1)-(CF2), (CM1)-(CM9), and (D1)-(D4) (with a, h ranging over As)We note that in PA(A) and PA5(A), commutativity of the merge (x || y = y || x) can be derived from axioms (Al) and (Ml). The binary equality relation = on process terms induced by an axiom system is obtained by taking all closed instantiations of axioms, and closing it under equivalence (i.e., under reflexivity, symmetry, and transitivity) and under contexts.
Process algebra with recursive operations
341
2.2. Transition rules and operational semantics We define a structural operational semantics in the style of Plotkin [68], to relate each process term to a labelled transition system. Then we define strong bisimulation as an equivalence between labelled transition systems, which carries over to process terms. The operational semantics and strong bisimulation are used in the proofs on axiomatisations in Sections 3 and 4, and on classification results in Section 5. A labelled transition system (LTS) is a tuple (5, {-^, -A- y/\a e A),s), where 5* is a set of states, - ^ for a G A is a binary relation between states, —> y for a € A is a unary predicate on states, ^ G 5 is the initial state. Expressions s - ^ s' and s - ^ y are called transitions. Intuitively, s - ^ s' denotes that from state s one can evolve to state s' by the execution of action a, while s - ^ y/ denotes that from state s one can terminate successfully by the execution of action a {y/ is pronounced "tick"). Consider one of the process algebra axiom systems BPA(A) — ACP(A, |, r), and let V represent all process terms given by its signature. We want to relate each process term in 7^ to a labelled transition system. We take the process terms in V as the set of states, and the atomic actions in A as the set of labels. (Note that atomic actions can denote both states and labels.) Exploiting the syntactic structure of process terms, the transition relations - ^ and - ^ y/ for a e A 3xt defined by means of inductive proof rules called transition rules | . Validity of the premises in 5, under a certain substitution, implies validity of the conclusion c under the same substitution. The transition rules in Table 2 define the labelled transition system associated to a process term in ACP(A, |, r). The signature and parameters of V (possibly including a communication function |) determine which transition rules are appropriate. For example, the last two transition rules for || (i.e., with x || y in the left-hand sides of their conclusions) are not relevant for ^\s{A). Note that the deadlock 8 has no outgoing transitions. The labelled transition system related to process term P has P itself as initial state. Often we will write simply P for the labelled transition system related to P. Intuitively, strong bisimulation relates two states if the LTSs rooted at these states have the same branching structure. This semantics does not take into account the silent nature ofr. DEFINITION 2.2.1 {Strong bisimulation). A strong bisimulation is a binary, symmetric relation IZ over the set of states that satisfies
-^ P' ^ 3Q'{Q~^ Q' PUQAP-^y/ =^ G - ^ V.
PHQAP
AP'UQ'),
Two states P and Q are strongly bisimilar, notation P ±± Q, if there exists a strong bisimulation relation 7^ with PIZQ.
342
J A. Bergstra et ai
Table 2 Transition rules for ACP(A, |, T ) , where a,be a
a a
X 1 X -\-y
1 > X «
a
x-Vy
X
a
>X
b
y
II
^ 1 ^
a
1
>X y
a
xy
1
X
b
«i^
II
1
a
X
'\ia\b^A
/
II X IL y
X
> X
,
b
y
> y
,
X
X
a
> X
^'
^ V ,
X 11 >' « l ^ > /x'II II / y'
1 > X
> V
t > X
y
11
"l^^
b
X 1 _v
/ > yj
> X'
11 V b
>'-
v'
ii
II
JC [j_ y X
a
.
y
>
>y
t > X
X 1y
y
a\b
b
a
a
/ > yj
/
b
/
X—>
V y—^ V 1 "1^ / x\y—> V
,
>X
/
H
xiaiH
9//U)-^3//U0 X
ifa\b€A
/
-y—^ V
> x'/
a\b
ifalbeA
"I'' /
JC II V a
X
1
>yyl
II
y- II >' — ^ y
a
b
^ II V
Q
X II y — > X
/
>^
X II y — U x' II y'/
> ^
II
> V
a
\ia\h^A
V
> V
X II V
f
y—>y
>V
>y
X
/ II
X—^V
x-\-y
>V
^—^ V
y—^ V ;c II >^ - ^ X y' II
>y
y—^V
V
X+ V
t > X
a
> x' II >' 1
ae A-c X—^
1
> y
a
xy t > X
X
V^
/ it
X
X II y
H, I C,A
y —> y
> X/
a
Aj,
r > X
x,(x)-^x,(x') x-^x' r/(x)-^r/UO
jjlael
lail
X
> V
' - ^ ^
-r
I
Mai I
2.2.2. (1) (Equivalence) It is not hard to see that strong bisimulation is an equivalence relation over ACV{A,\). (2) (Congruence) Strong bisimulation equivalence is a congruence relation up to ACP(A, I), meaning that PQ ±> QQ and P\ ^ Q\ implies Po-\- P\ ^ Go + 2 b PoPi ^ QoQ\, Po II P\ t> Qo II Q\, Pol P\^Qol Qu Po\P\^Qo\ Qu and 3// (Po) "^ 9// (Go)- This follows from the fact that the transition rules in Table 2 are in path/ormar; see [14,43,50] or Chapter 3 [6] in this handbook, (3) (Soundness) Up to and including ACP(A, j), all axiom systems are sound with respect to strong bisimilation equivalence, meaning that P = Q implies P <±Q. Since strong bisimulation is a congruence, soundness follows from the fact that all closed instantiations of axioms in ACP(/4, j) are valid in strong bisimulation semantics. (4) (Completeness) Up to and including ACP( A, j), all axiom systems are complete with respect to strong bisimilation equivalence, meaning that P<±Q implies P = Q; see, e.g.. [15,42].
THEOREM
Process algebra with recursive operations
343
We proceed to define some more semantic equivalence relations on states in a labelled transition system that do not take into account the silent nature of r. These definitions use the following notions, assuming an underlying LTS. Let P - ^ 2 for a 6 A* denote that state P can evolve to state Q by the execution of the sequence of actions a. This binary relation on states is defined as follows (with e denoting the empty string): - P-^ P; p- ^ Q Q-^ R P^^R p-
•V
p-^^V A string a 6 A* is a trace of P if P-^
Q for some state Q or P-^
2.2.3 (Substate). Q is a substate of P if P-^ proper substate of P if P-^ Q for some a e A* \{£}. DEHNITION
^.
Q for some a € A*. Q is a
2.2.4 (Ready simulation). A simulation is a binary relation 71 over the set of states that satisfies:
DEFINITION
PUQAP-U
P' ^ 3Q\Q-^
P U Q A P ^ ^
^
Q ^
Q'
AP'UQ').
V.
A simulation 7^ is a ready simulation if whenever PIZQ and « is a trace of Q, then a is a trace of P. Two states P and Q are simulation equivalent, notation P 2:1:5 C if P T^i Q and QIZ2P for simulations IZx and 7^2Two states P and Q are ready simulation equivalent, notation P —RS Q,if P7Z\ Q and QIZ2P for ready simulations 1Z\ and 7^2DEFINITION 2.2.5 (Lxinguage equivalence). Two states P and Q are language equivalent, notation P 2^^. 2> if for each trace P-^ ^ there is a trace Q - ^ V, and vice versa. DERNITION 2.2.6 {Jrace equivalence). Two states P and Q are rrac^ equivalent, notation P 2^:7 Q, if they give rise to the same set of traces.
In [45], van Glabbeek gave a comparison of a wide range of behavioural equivalences and preorders (i.e., relations that are in general not symmetric) that do not take into account the silent nature of T . Apart from the equivalence relation discussed above, he studied completed trace preorder and a variety of decorated trace preorders, which are based on decorated versions of traces. These preorders are coarser than strong bisimulation and ready simulation, but more refined than language and trace equivalence. In Section 4.3, prefix iteration is axiomatized with respect to some of the decorated trace preorders. The reader is referred to [45] for the definitions of these preorders.
344
J.A. Bergstra et al
Four standard semantic equivalences that take into account the silent nature of r (and that constitute congruence relations over ACP(y4, | , T ) ) are rooted branching bisimulation [49], rooted delay bisimulation [61], rooted //-bisimulation [13], and rooted weak bisimulation [63]. Of these four semantics, rooted branching bisimulation constitutes the finest relation, while rooted weak bisimulation constitutes the coarsest relation. In all four semantics the axiom (Bl) (i.e., jcr = jc) is valid, and that is all that is needed for the expressivity results concerning ACP(/4, |, r) discussed in this chapter. In [47], van Glabbeek gave a comparison of a wide range of process semantics that take into account the silent nature of r.
2.3. Recursive specifications Although iterative operations are recursive by nature, we will use recursive specifications and associated notions to prove some of the results concerning these operations. DEFINITION 2.3.1 {Recursion). We assume a set of recursion variables {Xj \ j e J) for some index set 7. A recursive specification £" is a set of recursive equations Xj = Tj for j € 7, where Tj is an ACP(A, |, r)-term in which the recursion variables X, for / e J may occur. Given some process semantics, processes Pj (for j e J) form a solution of E if substitution of Pj for Xj in the recursive equations of E yields equations that hold in this semantics. If a recursive specification has solutions, then these solutions are often referred to by the names of the corresponding recursion variables in E. Table 3 presents the transition rules for recursive specifications. If for instance E = [X = aX-\-b], then X - ^ X by the first transition rule, and X —> ^ by the second transition rule. Recursive specifications need not have unique solutions in any reasonable process semantics, examples being {X = X} and {X = TX}. The following two definitions are sufficient to remedy this imperfection. DEHNITION 2.3.2 (r-Guardedness). Let P be an expression containing a recursion variable X. An occurrence of X in P is z-guarded if P has a subexpression a Q where a e Aj; and Q contains this occurrence of X.
Table 3 Transition rules for recursion
\fX = TeE
T-^
I — ifX =
TeE
Process algebra with recursive operations
345
A recursive specification E — [Xj = Tj \ j e J] h r-guarded if by repeatedly substituting Tj expressions for occurrences of Xj, and by applying axioms of ACP(i4, |, r), one can obtain the situation that all occurrences of recursion variables in right-hand sides of recursive equations are r-guarded. DEFINITION 2.3.3 {z-Convergence). A recursive specification E = [Xj = Tj \ j e J)is X-convergent if Xj - ^ P (for j e J) implies that there is no infinite r-trace P —^ P' - ^ p'' ^ ^
Recursive specifications that are r-guarded and r-convergent have a unique solution modulo any reasonable process semantics. The existence of a solution underlies the soundness of the recursive definition principle [11]. We proceed to introduce the recursive specification principle (RSP), discussed in for instance [21,11]. This principle states that the recursive specification E = {Xj = Tj \ j e J} has at most one solution per recursion variable, modulo the process semantics under consideration. (RSP)
yj = TAyi/X:\ieJ)forJeJ Xk = yk
^^^^^^^^
(RSP) is sound with respect to the process equivalences mentioned thus far, provided E is both r-convergent and r-guarded. Note that (RSP) is not sound with respect to the recursive specifications {X = X] and {X = TX}. DEFINITION 2.3 A (Regularprocess). A process P is regular if P is bisimilar to a process T^iiQ) where 2 is a solution for a recursion variable in a finite recursive specification
where aij and fij are finite sums of actions in A (the empty sum representing 8).
3. Axiomatisation of the binary Kleene star In Section 1 we introduced the binary^ Kleene star (BKS), notation *. This operation is defined by the equation x''y=zx(x*y)-\-y. This section considers its finite equational axiomatisation in strong bisimulation semantics, and presents a negative result on the finite equational axiomatisability of BKS in a variety of other process semantics.
346
JA. Bergstra et al
3.1. Preliminaries BPA*(A) is obtained by extending BPA(A) with BKS. Bergstra, Bethke, and Ponse [17] introduced an axiomatisation for BPA*(A) modulo strong bisimulation equivalence, which consists of axioms (A1)-(A5) for BPA(y4), extended with the axioms (BKSl)-(BKS) for BKS in Table 4. The axiom (BKS3) stems from Troeger [73]. In order to provide process terms over BPA*(y4) with an operational semantics, we introduce transition rules for BKS. The transition rules for BKS in Table 5 express that x* j repeatedly executes x until it executes y. Together with the transition rules for BPA(A) in Table 2 they provide labelled transition systems to process terms over BPA*(A). Note that by the first two transition rules in Table 5, a state P can have itself as a proper substate. For example, a*6 - ^ a^'b. The transition rules for BKS are in path format [14,50]. Hence, strong bisimulation equivalence is a congruence with respect to BPA*(A); see [43] or Chapter 3 [6] in this handbook. Furthermore, its axiomatisation is sound for BPA*(y4) modulo strong bisimulation equivalence. Since strong bisimulation equivalence is a congruence, this can be verified by checking soundness for each axiom separately. It can be easily shown that the BKS axioms are valid in strong bisimulation. Fokkink and Zantema [44] proved that the axiomatisation for BPA*(A) is complete modulo strong bisimulation equivalence. Their proof is based on a term rewriting analysis (see, e.g., [10]), in a quest to reduce bisimilar process terms to the same ground normal form, which does not reduce any further. Since this aim cannot be fulfilled for BKS, this operator is replaced by an operator representing x{x*y), and the BKS axioms are adopted to fit this new operator. Those axioms are turned into conditional rewrite rules, which are applied modulo associativity and commutativity of the -f (see, e.g., [67]). Knuth-Bendix completion [54] is applied to make the conditional rewrite system weakly confluent. Termination of the resulting conditional term rewriting system is obtained by means of the technique oi semantic labelling from Zantema [75]. Hence, each process term is provably equal to a normal form. Finally, a careful case analysis learns that if two normal forms are strongly bisimilar, then they are syntactically equal modulo associativity and commutativity of the -f. This observation yields the desired completeness result. Table 4 Axioms for BKS (BKSl) (BKS2) (BKS3)
;c(jc*y) + v = Jc*y x*{yz) = {x*y)z x*(y((jc + y)*z) + z) = {x + yTz
Table 5 Transition rules for BKS a t
X — > X x^y > x'(jc*y)
a
I
X— >V Jc*y — ^ -v*y
at
>' — ^ y Jc*y > y'
f^'
/
y —^ V JC*_V > J
Process algebra with recursive operations
347
An alternative completeness proof was proposed in [38], based on induction on the structure of process terms. That proof method is more general, and was later on applied to obtain completeness results for axiomatisations of iteration operations in [ 1,34,39]. In the light of the generic applicability of this proof method and the significance of the completeness result in the realm of this chapter, we present the proof from [38] in some detail. Following Milner [64] (see also [46]), the latter proof strategy can also be used to derive CD-completeness of the axiomatisation for BPA*(y4). That is, if P and Q are open terms over BPA*(A), which may contain variables, and if a ( P ) = a(|2) holds for all closed instantiations a, then P = Q can be derived from the axioms. Often, co-completeness can be proved by providing variables with an operational semantics, such that P <^ Q holds with respect to this new operational semantics if and only if <J(P) <±a(Q) holds for all closed instantiations a with respect to the original operational semantics. In [38], completeness of the axiomatisation for BPA*(A) modulo bisimulation equivalence is derived for open terms, which immediately implies a>-completeness of the axiomatisation. Here, we present the proof from [38] for closed (instead of open) terms. The reader is referred to [38] for a proof of CD-completeness. (The motivation to refrain from this generalisation here is clarity of presentation; we prefer to work in an unambiguous semantic framework throughout this chapter.)
3.2. Completeness We note that each process term over BPA*(y4) has only finitely many substates. In the sequel, process terms are considered modulo associativity and commutativity of the -h, and we write P =AC Q if P and Q can be equated by axioms (Al) and (A2). As usual, z2i=\ Pi represents P\-\ \- Pn- We take care to avoid empty sums (where ^ L i Pi + Q is not considered empty and equals Q). For each process term P, its collection of possible transitions is non-empty and finite, say {P - ^ P, IJ = 1 , . . . , m} U {P - X y I y = 1,...,«}. We call m
n
J2^iPi-^J2^j i=\
j=\
the HNF-expansion of P (Head Normal Form expansion, cf. [15]). The process terms a, Pi and bj are the summands of P. LEMMA
3.2.1. Each process term is provably equal to its HNF-expansion.
PROOF.
Straightforward, by structural induction, using (A4), (A5), and (BKS1).
D
Process terms in BPA*(A) are normed, which means that they are able to terminate in finitely many transitions. The norm [12] of a process yields the length of the shortest termination trace of this process. Norm can be defined inductively by \a\ = 1,
348
JA. Bergstra et al.
|P + ei \PQ\ =
=min[\Pl\Q\}^ \P\^\Ql
\P'Q\ = \Ql We note that strongly bisimilar processes have the same norm. The following lemma, due to Caucal [29], is typical for normed processes. LEMMA 3.2.2. Let PQ±>RS. By symmetry we may assume \Q\ ^ |.S|. We can distinguish two cases'. • either P ±> R and Q±> S\ • or there is a proper substate P' of P such that P ±> RP' and P'Q<± S. PROOF.
This lemma follows from the following Facts A and B.
FACT A. IfPQ^RS and\Q\ ^ |5|, then either Q±±S, or there is a proper substate P' of P such that P'Q^S. PROOF. We prove Fact A by induction on |P|. First, let | P | = 1. Then P -^ ^ fox some a, so PQ -U Q. Since PQ ^ RS, and \R'S\ > \S\ ^ \Q\ for all substates R' of /?, it follows that R - ^ y and Q 't± S. Then we are done. Next, suppose we have proved the case for | P | ^ n, and let | P | = n -f-1. Then there is a P' with | P ' | = « and P - ^ P\ which implies PQ - % P'Q. Since PQ ±^ RS, we have two options: (1) P - ^ V and P'Q±>S. Then we are done. (2) R-^ R' and P'Q<± R'S. Since \P'\=n, induction yields either Q±^S or P"Q±± S for a proper substate P'^ of P'. Again, we are done. This concludes the proof of Fact A. D FACTB.
IfPQ^RQ,thenP<±R.
PROOF. Define a binary relation B on process terms by TBU iff TQ^ UQ.V^t show that B constitutes a strong bisimulation relation between P and R. • Since 1> is symmetric, so is B. • PQ±^RQ, so PBR. • Suppose r e L ^ and T -U ^. Then TQ - ^ Q, Since TQ ±> UQ. and \U'Q\ > Q for all substates U' of U. it follows that UQ-^ Q. In other words, U -^ ^. • Suppose r S L ^ and T - % r . Then TQ - % T'Q. Since TQ±>UQ. and i e | < \rQl it follows that there is a transition U -^ V with T'Q^ U'Q. Hence, T' B U'. This concludes the proof of Fact B. D
Finally, we show that Facts A and B together prove the lemma. l.Qi PQ <± RS with I |2I < |5|. According to Fact A we can distinguish two cases. • Q±±S. Then PQ^RS±^ RQ, so Fact B yields P i± /?.
Process algebra with recursive operations
349
• P'Q<±S fox some proper substate P' of P. Then PQ±>RS<± RP'Q. so Fact B yields P<±RP\ D We construct a set B of basic terms, such that each process term is provably equal to a basic term. The completeness theorem is proved by showing that strongly bisimilar basic terms are provably equal. (x + y)z -^ xz-h yz, ixy)z -> x{yz), (x*y)z ^
x'iyz).
The term rewriting system above consists of directions of the axioms (A4), (A5), and (BKS2), pointing from left to right. Its rewrite rules are to be interpreted modulo associativity and commutativity of the +. The term rewriting system is terminating, meaning that there are no infinite reductions. This follows from the following weight function w in the natural numbers: wia) = 2, w(P-\-Q)
=
w(P)-hw(Q),
w(PQ) =
wiPfwiQ),
w(P*Q) =
w(P)-^w(Q).
It is not hard to see that if P reduces to Q in one or more rewrite steps, then w(P) > w(Q). Since the ordering on the natural numbers is well-founded, we conclude that the term rewriting system is terminating. Let G denote the collection of ground normal forms, i.e., the collection of process terms that cannot be reduced by any of the three rewrite rules. Since the term rewriting system is terminating, and since its rewrite rules are directions of axioms, it follows that each process term is provably equal to a process term in G. The elements in G are defined by: P::=a\P-\-P\aP\
P^'P.
G is not yet our desired set of basic terms, due to the fact that there exist process terms in G which have a substate outside G. We give an example. EXAMPLE 3.2.3. Let A = {a, b, c}. Clearly, (a*b)*c € G, and (a*byc-U(a*b){(a%rc). The substate (a*b)((a*b)*c) is not in G, because the third rewrite rule in 1Z reduces this process term to a*(b((a*b)'^c)).
350
J.A. Bergstra et ai
In order to overcome this complication, we introduce the following collection of process terms: H = { P * e , P'iP^'Q) I P * e € G and P' is a proper substate oiP]. We define an equivalence relation = on IHI by putting P'{P"" Q) = P* Q fov proper substates P ' of P, and taking the reflexive, symmetric, transitive closure of = . The set B of basic terms is the union of G and H. LEMMA
3.2.4. IfPeMandP-^
P\ then P' eB.
PROOF. By induction on the structure of P.
If P G H \ G, then it is of the form Q'{Q*R) for some 2*/? G G. So P' is of the form either g*/? or Q'^Q^'R) for some proper substate Q" of Q'. In both cases, P' G B . If P G G, then it is of the form Y.i ^i Qi + Hj ^*j^j + E)t ^^' ^^^^^ ^^^ 2 " ^y' ^^^ Sj are in G. So P' is of the form Qi, R*Sj, R'jiR*Sj), or 5^, which are all basic terms (in the last case, this follows by structural induction). D The L-value [44] of a process term is defined by L(F) =max{|P'| | P' proper substate of P } . L(P) < L(PQ) and L{P) < L(P* Q), because for each proper substate P' of P, P ' Q is a proper substate of P Q and P\P* Q) is a proper substate of P* Q. Since norm is preserved under strong bisimulation, it follows that the same holds for L-value; i.e., ii P ±> Q then L{P) = L{Q). We define an ordering -< on B as follows:
•
P
• P -< (3 if P is a substate of Q but Q is not a substate of P; • if P -< Q and (2 -( P, then P < R. Note that if P, 2 G HI with P = Q, then P and Q have the same proper substates, and so L(P) = L(Q). These observations imply that the ordering ^ on B respects the equivalence = on M, that is, if P = g ^ P = 5, then P <S. LEMMA 3.2.5. < is a well-founded ordering on B. If P is a substate of Q, then all proper substates of P are proper substates of g , so UP) ^ L(Q). Hence, if P ^ g then L(P) ^ L(Q). Assume, toward a contradiction, that there exists an infinite backward chain < Pi < P\ < PQ. Since L(P„+i) ^ L(Pn) for all n G N, there is an A^ such that L(Pn) = LiPis/) for all n > iV. Since Pn < PN for n > N, it follows that P„ is a substate of Pi^ for n > N. Each process term has only finitely many substates, so there are m, n > A^ with n > m and Pn =AC Pm- Then Pn i^ Pm. SO wc havc found a contradiction. Hence, -< is well-founded. D PROOF.
Process algebra with recursive operations
351
In the proofs of the next two lemmas, we need a weight function g in the natural numbers, which is defined inductively by g{a) = 0, g(P-hQ) g(PQ)
=meix{g(P)^g(Q)}, =m^x{g(P),g(Q)},
g{P^Q) = max{^(P),g(Q) + l}. It is not hard to see, by structural induction, that if P -^ LEMMA
P\ then g(P) ^ g(P')-
3.2.6. Let P*Q£ B. IfQ' is a proper substate of Q, then Q' < P^'Q.
is a substate of g , so g(Q') ^ g(Q) < g(P*Q). which implies that P*Q cannot be a substate of Q'. On the other hand, Q' is a substate of P* g , so Q' < P*Q. D PROOF. Q'
LEMMA
3.2.7. IfP eMandP-^
PROOF.
This lemma follows from the following Facts A and B.
FACT
A. IfPeM
PROOF.
P\ then either P' < P, or P,P' eU and P = P\
and P - ^ P\ then either P' eWor P' has smaller size than P.
We prove Fact A by induction on the structure of P. Let
Since P -^ P\ P' is of one of the following forms. • P^ =AC Qi for some /. Then P^ has smaller size than P. . P' =AC ^'ji^^jSj) or P' =AC R)Sj for some 7. Then P' e M. • Sj - A P' for some j . Then induction yields that either P' e H, or P' has smaller size than Sj, which in turn has smaller size than P. This concludes the proof of Fact A. D FACT B .
IfP eMandP-^
P\ then either g(P) > g(P'), or P' eU and P = P'.
Since P € H, either P =AC Q'iQ^'P) or P =AC C*/? for some Q and R. Hence, P' =AC Q'^Q^'R). P' =AC G * ^ . or P' =AC R' for a proper substate R' of R. In the first two cases P ' € H and P = P\ and in the last case g{P') = g{R') ^ g{R) < g(Q*R) = g(P). This concludes the proof of Fact B. D PROOF.
Finally, we show that Facts A and B together prove the lemma. Let P -^ P' ^ P\ we prove that P, P ' € H and P = P'.
P' with
352
J.A. Bergstra et al.
Since P' is a substate of P and P' -/: P, P isa substate of P\ So there exists a sequence of transitions P o - ^ P i ^ - ' - ^ P .
(Ol)
where PQ =AC /", P\ =AC Z'', and P„ =AC P^ Suppose Pk ^B. for all k. Then according to Fact A, Pk-^\ has smaller size than Pk for k = 0,.... n — I, so Pn has smaller size than PQ. This contradicts PQ =AC ^ ==AC PnHence, Pi eM for some /. Since each Pk is a substate of each Pk',g{Pk) must be the same for all k. Then it follows from Fact B, together with Pi e H, that Pk eU for all /: and PQ = ^i = • • • = ^n • D Now we are ready to prove the desired completeness result for BPA*(A). THEOREM 3.2.8. (A1)-(A5), (BKS1HBKS3) is complete for BPA*(A) modulo strong bisimulation equivalence.
Each process term is provably equal to a basic term, so it is sufficient to show that strongly bisimilar basic terms are provably equal. Assume P, 2 e B with P i± g ; we show that P = Q,hy induction on the ordering ^ . To be precise, we assume that we have akeady dealt with strongly bisimilar pairs P, 5" e B with P -( P and 5 ^ 2 , or P ^ P and 5 = e , o r P ^ P a n d 5 ^ 2. First, assume that P or Q is not in H, say P ^ H. By the induction hypothesis, together with Lemma 3.2.7, for all transitions P - A P' and G - ^ Q' with P' <± Q' we have P = Q. Since P ±^ Q, axiom (A3) can be used to adapt the HNF-expansions of P and Q to the form PROOF.
m
n
m
n
where P, = 2/ for / = 1 , . . . , m. Hence, P = Q. Next, assume P,
iel
jeJ
where the P/ and the Tj are of the form either aV or a. Since P*5 i> 7*(/, each P/(P*5) for / e / is strongly bisimilar either to Tj{T*U) for a 7 € y or to a sunmiand of (/. We distinguish these two cases. (a) P/(P*5)±>r,(r*L^)fora7 G7.ThenP/(P*5)t>7;(P*5),sobyLemma3.2.2 (b) P, (P*5) ±±aU' for a transition U - ^ W.
Process algebra with recursive operations
353
Thus, / can be divided into the following, not necessarily disjoint, subsets: /o =
[ieI\3jeJ{Ri^Tj)]^
h = [i e I \3U -^
U'
(Ri(R*S)±>aU')}.
Similarly, J can be divided: 70 = {jeJ\3ieI /i = [j e J \3S -^
(Tj^Ri)}, S\Tj(T''U) ±^ aS')}.
If both I\ and J\ are non-empty, then U" <± /?*5 for a proper substate U'' of U, and ^ff ^ j^U f^^ ^ pj.Qpgj. substate S" of 5, and so U" <± S". By Lemma 3.2.6, S" < R*S and U'' < T^'U, so induction yields R*S = U" = 5'' = T*^, and we are done. Hence, we may assume that either I\ or J\ is empty, say J\ = 0. We proceed to derive ^ / ? / ( / ? * 5 ) + 5 = i7.
(1)
ieh
We show that each summand at the left-hand side of the equality sign is provably equal to a summand of U, and vice versa. • By definition of / i , for each RiiR*S) with / e I\ there is a summand aU' of U such that Ri{R*S) <± aU\ By Lemma 3.2.6 U' < T*U, so induction yields Ri(R*S)=aU\ • Consider a summand aS' of 5. Since R*S±±T*U and J\ = 0, it follows that aS' is strongly bisimilar to a summand all' of U, so induction yields aS' — aU'. • Finally, summands a of 5 correspond with summands a of U. • By the converse arguments it follows that each summand of U is provably equal to a summand at the left-hand side of the equality sign. This concludes the derivation of (1). Since J\ = 0, it follows that Jo ^ 0, so /Q ^ 0. By the definitions of /Q and Jo = J, each Ri with / e /o is strongly bisimilar to a Tj with 7 € J, and vice versa. Since L(Ri) ^L(R) < L(/?*5), induction yields Ri = Tj. Hence, ^ / ? / = r.
(2)
ielo
Finally, we derive R*S
(A3)
(BKS3).(A3)
(iy2)
^*^
354
J A. Bergstra et al
(2) Let P =Ac R'{R*S) and Q =AC T'^U. We prove /?\/?*5) = T'^U. \U\ = \T*U\ = \R\R*S)\ ^ 2 implies that U does not have atomic summands, so its HNF-expansion is of the form Yli^i^i- Since R\R*S) ^ T*U, each Ui is strongly bisimilar to R*S or to R'\R*S) for a proper substate R" of /?^ According to Lemma 3.2.6 Uj < T*U, so induction yields Ut = R*S or Uj — /?''(/?*5). This holds for all /, so ^ = J^i^i^i = ViR^S) for some process term V. Then R\R*S) ±> T*U i> (r*V)(/?*5), so Lemma 3.2.2 implies R' ^ T*V. Since L(R') < L(R\R*S)), induction yields R' = T*V. Hence, R\R*S) = (7*V)(/?*5') ^^=^^ r*(V(/?*5)) = r*L^. (3) Let P =Ac /?'(/?*5) and Q =AC T'{T*U). We prove /?'(/?*5') = r(T*U). By symmetry we may assume |/?*5| ^ |r*/7|. Lemma 3.2.2 distinguishes two possible cases. • R'^T' and /?*5 ±> T*U. Since L(/?0 < L(R'(R*S)), induction yields R' = T\ and case (1) applied to R*S ±± T*U yields R*S = T*U. Hence, R\R*S) = • R' ±± T'R" and R^R^'S) ±> T*U for a proper substate R^' of /?'. Since L(R') < L(R\R*S)), induction yields R' = T'R". Furthermore, case (1) applied to R'\R*S) ±> T*U yields R'\R''S) = T*U. Hence, R\R*S) = (T'R'')(R*S) ^^= ^^ r(R'\R*S)) This finishes the derivation of P = Q.
=
r(T*U). D
3.3. Irredundancy of the axioms Fokkink [38] showed that each of the BKS axioms is essential for the obtained completeness result. 3.3.1. If one of the BKS axioms is skipped from (A1HA5), (BKS1)-(BKS3), then this axiomatisation is no longer complete for BPA*(A) modulo strong bisimulation equivalence. THEOREM
PROOF. We apply a standard technique for proving that an equation e cannot be derived from an equational theory £, which prescribes to define a model for £ in which e is not valid. In order to show that (BKSl) cannot be derived from (A1HA5), (BKS2), (BKS3), we define an interpretation function 0 of open terms in the natural numbers:
cl>(a) = 0, 0(x) = 0, HP-^Q) = max{>(P),0(e)}, (l>(PQ) = cP(P)^ (l>(P*Q) = max{0(P) + \,(t>(Q) + 1}.
Process algebra with recursive operations
355
It is easy to see that this interpretation is a model for (A1)-(A5), (BKS2), (BKS3). However, 0(«(«*fl) -i-fl) = 0, while (/)(«*^) = 1. Hence, a(a*a) -\-a —a*a cannot be derived from (A1HA5), (BKS2), (BKS3). In order to show that (BKS2) cannot be derived from (A1)-(A5), (BKSl), (BKS3) we define an interpretation function i/r of open terms in the natural numbers: f{a) = 0, f{x)
= 0,
HP + Q) =max{Vr(/^),iA(e)}, ^{PQ)
=
f{Q).
rlr(P*Q) = max{^(P) + 1, if(Q)}. It is easy to see that this interpretation is a model for (A1)-(A5), (BKSl), (BKS3). However, \lf((a*a)a) = \lr(a) = 0, while \l/(a*(aa)) = max{V^(«) -h 1, ir(aa)] = 1. Hence, (a*a)a = a*(aa) cannot be derived from (A1HA5), (BKSl), (BKS3). In order to show that (BKS3) cannot be derived from (A1)-(A5), (BKSl), (BKS2), we define an interpretation function r] of open terms in sets of natural numbers:
nia) = 0, riM = 0, V(P + Q) = riiPQ) = riiP^'Q) =
r](P)^n(Q). ri(P)Ur](Q), ri(P)Uri(Q)U{\P\}.
It is easy to see that this interpretation is a model for (A1)-(A5), (BKSl), (BKS2). However, rj((aa)*(a((aa -I- a)*a) -^ a)) = {\aa\, \aa -\- a\} = {1,2} while r]{{aa -f aTa) = {|aa + a|} = {1}. Hence, {aaT{a{{aa + aTa) -h a) = {aa -h aYa cannot be derived from (A1)-(A5), (BKSl), (BKS2). D
3.4. Negative results In contrast with the positive result on the finite equational axiomatisability of BPA*(A) modulo strong bisimulation equivalence, Aceto, Fokkink, and Ingolfsdottir [4] showed that BPA*(A) is not finitely based modulo any process semantics in between ready simulation (see Definition 2.2.4) and language equivalence (see Definition 2.2.5). In the case of a singleton alphabet, this answered a problem in regular languages raised by Salomaa in [71 ]; see [3]. Crvenkovic, Dolinka, and Esik [35] provided a more elegant answer to the latter question. Ready simulation and language equivalence constitute congruence relations over BPA*(A) (in the case of language equivalence this follows from the fact that the transition rules for BPA*(A) are in L cool format [40]). Process semantics in the linear/branching
356
J.A. Bergstra et al
time spectrum [45] that are finer than language equivalence and coarser than ready simulation, and which constitute congruence relations over BPA*(y4), are failure semantics, ready semantics, failure trace semantics, and ready trace semantics. The result above follows from the existence of an infinite set of equations that cannot all be proved by means of any finite set of equations that is sound modulo language equivalence. This family of equations consists of E.n
a*{a") + {a")*{a + ... + a") = {a"y{a +
.--+a")
for n ^ 1, where a is some action. Ready simulation is the finest semantics in the linear/branching time spectrum in which the E.n are sound. Note that for n > 1, none of the equations E.n is sound in strong bisimulation equivalence. Given a finite set of equations that is sound with respect to language equivalence, Aceto, Fokkink, and Ingolfsdottir construct a model Ap for these equations in which equation E./7 fails, for some prime number p. The model that is used for this purpose is based on an adaptation of a construction due to Conway [31], who used it to obtain a new proof of a theorem, originally due to Redko [69], saying that BPA*(y4) is not finitely based modulo language equivalence. Let a be an action. For p a. prime number, the carrier Ap of the algebra Ap consists of non-empty formal sums of a^,a\ ..., «^~^ together with the formal symbol a*, that is. ^ a '
|0C/c{O,...,/7-l}
U{a*}.
iel
The syntax of Ap contains three more operators, which are semantic counterparts of the binary function symbols in BPA*(A). In order to avoid confusion, circled symbols denote the operators in the algebra Ap: 0 , O, and (g) represent the semantic counterparts of -h, •, and *, respectively. Table 6 presents an axiomatisation for Ap. Process terms over BPA*(A) are mapped to Ap as expected: every action in A is mapped to the symbol a ^, while -h, •, and * are mapped to 0 , O, and ®, respectively. For a process Table 6 Axiomatisation for the algebra Ap a ©X = a X ©a* = a* iel
jeJ
helUJ
a* Ox = a* xQa* = a*
^a'0E«^= iel
jeJ
E he[(i+j) mod p\{ij)elxJ]
a*
otherwise
Process algebra with recursive operations
357
term P, the denotation of P in the algebra Ap is represented by ^/?|[Pl. We note that equation E.p fails in Ap. Namely,
The following theorem is the key to the nonaxiomatisability result from [4]. 3.4.1. For every finite set £ of equations that are sound with respect to there exists a prime number p such that all equations in S are valid in Ap. THEOREM
COROLLARY 3.4.2. No congruence relation over BPA*(A) that is included in satisfies E.nfor alln^l has a complete finite equational axiomatisation.
^L
'^L.
and
A process semantics that is coarser than language equivalence is trace equivalence 2:IT. where two process terms are considered equivalent if they give rise to the same (not necessarily terminating) traces (see Definition 2.2.6). If |A| > 1, then trace equivalence is not a congruence relation over BPA(i4); e.g., a-{-aa C:^T aa, but (a -f aa)b 9^7 aab. However, if the set A of actions is a singleton [a], then trace equivalence constitutes a congruence relation over BPA*(A). In contrast with their negative results on the finite axiomatisability of BPA*(A) modulo process semantics between ready simulation and language equivalence, Aceto, Fokkink, and Ingolfsdottir showed that BPA*({a}) modulo trace equivalence is axiomatized completely by the five axioms for B?A({a]) together with the three axioms in Table 7. THEOREM
3.4.3. (A1)-(A5), (T1)-(T3) is complete for BPA*({^}) modulo trace equiva-
lence.
3.5. Extensions of BFA*{A) The signature of BPA^(A) is obtained by extending BPAsiA) with BKS. Its axioms are those of BPA*(A) and of BPA5(A), i.e., (A1)-(A7) in Table 1 for BPA^(A), and (BKSl)(BKS3) for BKS. Sewell [72] showed that there does not exist a complete equational ax-
Table 7 Axioms for trace equivalence {A = {a}) (Tl) X + iy*z) (T2) X -\-xy xy (T3)
= = =
a*a xy yx
358
JA. Bergstra et al. Table 8 Axioms for BKS with encapsulation and abstraction (BKS4) (BKS5)
a//(;c*v) = a//U)*a//(v) Tj(x*y) = r/(;c)*r/(y)
iomatisation for BPA^(A) modulo strong bisimulation equivalence. This motivates the introduction of the implicational axiom (Rsp*)
'=y'+\ X = y*z
It remains an open question, dating back to Milner [62], whether (A1)-(A7), (BKSl), (RSP*) is complete modulo strong bisimulation equivalence. We note that (BKS2) and (BKS3) can be derived from this axiomatisation. The signature of PA*(A) is obtained by extending PA(A) with BKS. The axioms of PA*(A) are those of PA(A) and (BKS1)-(BKS3). The system PAsiA) can be extended in a similar way to PA^(A). The system ACP* (A, |) is defined by inclusion of (BKS 1HBKS4); see Table 8. Note that (BKS4) can be derived using (RSP*). Finally, ACP*(A, |, r) is obtained by inclusion into ACP(A, |, r) of (BKS1HBKS5); see Table 8. Note that (RSP*) is not sound for ACP*(A, |, T); e.g., r = r r - f 5, but r = T*8 is not a desirable identity in any process semantics.
4. Axiomatisations of other iterative operations This section considers four restricted versions and one generalised version of BKS. We discuss the different advantages of each of these operators, and formulate various axiomatisations and completeness results.
4.1. Axiomatisation of no-exit iteration No-exit iteration (NEI) x"^ is bisimilar to x*8. No-exit iteration can be used to formally describe programs that repeat a certain procedure without end. Many communication protocols can be expressed, and shown correct, using no-exit iteration. An explanation is that (concurrent) components of such protocols often perform repetitive behaviour in the following style (receive/process/send-repetition): (j^n{d)Psj{d)\ ^ deD
or ^
('^r/(J)P5,(^) + e j , ^ deD
'
Process algebra with recursive operations Table 9 Axioms for NEI (NEIl)
x^=x{x^)
359
Table 10 Transition rules for NEI x-^x'
x-^y/
where Q handles an exceptional situation. A standard example in process algebra is the alternating bit protocol (see, e.g., [21]), specified as the concurrent execution of four components, each of which can be specified in the style above. Further examples of this specification and verification style can be found in [18,76]. Table 9 presents two axioms for NEI. (NEIl) is its defining axiom, while (RSP^) is an adaptation of (RSP*). The axiomatisations for BPA'^(A) and BPA^(A) are obtained by extending BPA(A) and BPA5(A) with (NEIl) and (RSP^). In order to provide process terms over BPA^(y4) with an operational semantics, we introduce transition rules for NEI. Together with the transition rules for BPA(i4) in Table 2 they provide labelled transition systems to process terms over BPA^(A). The transition rules for NEI are in path format. Hence, strong bisimulation equivalence is a congruence with respect to BPA^(A). Furthermore, its axiomatisation is sound for BPA^(A) modulo strong bisimulation equivalence. Since strong bisimulation equivalence is a congruence, this can be verified by checking soundness for each axiom separately. It is easily verified that (NEIl) and (RSP^) are indeed sound modulo strong bisimulation equivalence. The following two completeness results for no-exit iteration originate from [39]. Their proofs, which are omitted here, are based on the proof strategy from [38]. THEOREM 4.1.1. (A1)-(A5), (NEIl), (RSP^) is complete for BPA^(A) modulo strong bisimulation equivalence. THEOREM 4.1.2. (A1)-(A7), (NEIl), (RSP^) is complete for BPA^(A) modulo strong bisimulation equivalence.
The observation by Sewell [72] that there does not exist a complete finite equational axiomatisation for BPA|(A) modulo strong bisimulation equivalence, is based on the fact that a^ is strongly bisimilar to {a^)^ fork^ 1. This argument can be copied to conclude that there do not exist complete finite equational axiomatisations for BPA^(A) and BPA^(A). Hence, the implicational axiom (RSP^) is irredundant. It is not difficult to see that axiom (NEIl) is irredundant as well.
4.2. Axiomatisation of multi-exit iteration Milner [62] noted that not every regular process can be described in BRA*(A), up to strong bisimulation equivalence. The limited expressive power of BKS was highlighted in [16],
360
JA. Bergstra et al Table 11 Axioms for MEI
(MEIl)
xx{{x2,...,xk,xxr{y2,...,yk.y\)) +
(MEI2)
{{xx,...,xkr{yx....,yk))z
(MEI3)
(zo'-^2----^^)*(>'i +z\{{x2 =
=
y\--{x\,...,xkr{y\,...,yk) {xx....,xi,r{yM,...,ykz)
xk,zo + z\T{y2^-...yk^y\))^y2^--'^yk)
{zQ-\-z\,x2,..-,xf,)*{y\,-..,yk)
(MEI4)
{ZQ.Z\,X2,...,XkT{y\,Z2{{X2^---,Xk,ZQ{Z\
(MEI5)
((xu...,xk)^r{{y\,...,yk)')
= (zoC^i + Z2),X2,...,
xkTiyx,..., =
+Z2))*(V2---n-'Vl))'>'2---yA:)
yk) {xi,...,xkr{yi,...,yk)
where it was shown that the process described by the recursive specification X\ = aX2 H-fl, X2 = aXi-\-b, cannot be expressed in BPA*(A) modulo strong bisimulation equivalence. See Section 5 for more information on the expressive power of iterative operators. Bergstra, Bethke, and Ponse [16] introduced multi-exit iteration (MEI) as a more expressive variant of iteration. For every A: ^ 1, and process terms Pi and Q, (1 ^ / ^ /:), the process term (P\,..., Pk)*(Q\, - •., Qk) denotes a solution to the recursion variable X\ in the recursive specification Xi = P1X2 + G1,
Xk-\ = Pk-\Xk H- Qk-\. Xk =
PkXi-\-Qk.
Aceto and Fokkink [1] introduced the axiom system BPA'"^*(A), which is obtained by adding the MEI axioms (MEI1)-(MEI5) in Table 11 to BPA(A). The first three MEI axioms are adaptations of the three BKS axioms. The last two MEI axioms relate process terms of distinct exit degrees. (MEM) is the multiplicative counterpart of (MEI3), while (MEI5) enables to reduce repetitive patterns at the left- and right-hand side of MEI. In order to provide process terms over BPA'"^*(A) with an operational semantics, we introduce transition rules for MEI. Together with the transition rules for BPA( A) in Table 2 they provide labelled transition systems to process terms over BPA'"^*(A). The transition rules for MEI are in path format. Hence, strong bisimulation equivalence is a congruence with respect to BPA'"^*(A). Furthermore, its axiomatisation is sound for BPA^^*(A) modulo strong bisimulation equivalence. Since strong bisimulation equivalence is a congruence, this can be verified by checking soundness for each axiom separately. It is easily verified that (MEIl), (MEI2), and (MEI5) are sound modulo strong
Process algebra with recursive operations
361
Table 12 Transition rules for MEI a
I
-yj — ^ - ^ 1
Ui,...,x^)*(>'I,...,>'^)-%jt',(U2,...,^;,A:i)*(y2 x\ Ui,...,xi,Y{y\.•••,yk) a
> ^
- ^ (-^2
t
^k^x\)*(y2
y;,y\) a
y\ — ^ >'i (xi,...,XA:)*(3^i - • . . >'^) - ^ yi
VA, Vl))
I
V, - ^ V Ui
xk)*{y\,...,
vjt) - ^
y
bisimulation equivalence. See [1] for a detailed proof that (MEI3) and (MEM) are sound modulo strong bisimulation equivalence. In [1] it is proved that the axiomatisationBPA'"''*(y4) is complete for BPA'^''*(A) modulo strong bisimulation equivalence. The completeness proof, which is omitted here, is based on the proof strategy from [38]. THEOREM 4.2.1. (A1HA5), (MEI1)-(MEI5) is complete for BPA'"^*(A) modulo strong bisimulation equivalence.
4.3. Axiomatisation ofprefix iteration Prefix iteration (PI) [36] is a variation of BKS, obtained by restricting its first argument to single atomic actions. The advantage of PI over BKS is twofold: (1) PI can be axiomatized in a setting with prefix multiplication of CCS [63], which is obtained from sequential composition by restricting its first argument to single atomic actions; (2) PI allows a complete equational axiomatisation modulo strong bisimulation equivalence in the presence of the deadlock 5. We note that, in general, sequential composition can be restricted to prefix multiplication without loss of expressivity. BPA^*(A) consists of BPA(A), with sequential composition xy restricted to prefix multiplication ax from CCS, extended with PI. Table 13 presents a collection of axioms for PI. First of all, (PI1)-(PI2) from [36] axiomatize PI with respect to strong bisimulation. THEOREM 4.3.1. (A1)-(A3), (A6), {V\\)-{V\1) is complete for'BVkl''{A) bisimulation equivalence.
modulo strong
The remaining equations and inequalities in Table 13 originate from Aceto, Fokkink, and Ingolfsdottir [5], who proved completeness results for PI in a variety of behavioural equivalences and preorders in the linear/branching time spectrum [45]. These axiomatisations for BPA^*(A) all incorporate axioms (A1)-(A3), (A6) for BPA<5(A) with prefix
362
J A. Bergstra et al Table 13 Axioms for PI (PIl) (PI2)
\{a*x)^x a^ia^'x)
— a*x = a*x
(CTl) (PCTl) (PCT2)
a(x + v) a*ix-\-y) a* (ax)
= = =
ax + ay a*x -\-a*y aia*x)
aS a*8
8 8
X
= = ^
ax a*x
^ ^
ax -\-ay a*(x-^ay)
(LI) (PLl) (SI) (RSI) (PRSl) (Rl) (PRl) (PR2) (Fl) (PFl) (PF2) (PF3)
X+ V
a{bx-\-by + v) ^ a{bx-\-v)-i-a{by + w) a(a*ibx-^by-^v)) ^ aia*{bx-]-v))-{-a(a*(by+ w)) a*ibx-\-by-\-v-^a(by-\-w)) ^ a*(bx-i-v-\-aiby-\-w))-\-by a{x-\-y) a(a*(x + y)) aia*x) a*{x-\-y+a{y + z))
^ ^ ^ ^
ax-\-a(y-{-z) a{a*x)-\-a{a*{y-i-z)) a*ia(x-\-y)) a*{x+a{y-\-z))-\-y
multiplication, standard axioms from the literature for BPA^CA) modulo the behavioural equivalence in question, and (PI1)-(PI2) for PI. (PCT1)-(PCT2) axiomatize PI with respect to completed trace equivalence. THEOREM 4.3.2. (A1HA3), (A6), (PI1)-(PI2), (CTl), (PCT1)-(PCT2) is complete for BPA^*(A) modulo completed trace equivalence.
(PLl), in cooperation with (PCT1)-(PCT2), axiomatize PI with respect to language equivalence. THEOREM 4.3.3. (A1)-(A3), (A6), (PI1)-(PI2), (CTl), (PCT1)-(PCT2), (LI), (PLl), is complete for BPA^*(A) modulo language equivalence.
No extra axioms are needed for PI modulo simulation preorder. THEOREM 4.3.4. ( A 1 ) - ( A 3 ) , simulation preorder.
(A6), ( P I 1 ) - ( P I 2 ) ,
(SI) is complete for BPA^*(A) modulo
(PRSl) axiomatizes PI with respect to ready simulation preorder. THEOREM 4.3.5. (A1)-(A3), (A6), (PI1)-(PI2), (RSI). {VRS\) is complete for BVKl''{A) modulo ready simulation preorder
Process algebra with recursive operations
363
Table 14 Axioms for SI (SA5) (SIl) (SI2) (SB) (SI4)
w\{w2x) = {w\W2)x w{w*x) -\-x w*(w*x) (w")*8 a{(wa)*8)
= = = =
w*x w*x w*8 iaw)*8
(PR1)-(PR2), in cooperation with (PRSl), axiomatize PI with respect to readies preorder. THEOREM 4.3.6. (A1)-(A3),(A6), (PIl)-(PI2),(RSl),(Rl),(RSl),(PRl)-(PR2)/5cowplete for BPA^*(A) modulo readies preorder.
It is still an open question whether there exists a complete axiomatisation for BPA^*(A) modulo failures preorder. Aceto, Fokkink, and Ingolfsdottir conjectured that (PF1)-(PF3), in cooperation with (PRSl), are sufficient to axiomatize PI with respect to failures preorder. CONJECTURE 4.3.7. (A1)-(A3), (A6), (PI1)-(PI2), (Fl), (PRSl), (PF1)-(PF3) is complete for BPA^*(A) modulo failures preorder.
To the best of our knowledge, axioms for PI with respect to ready trace preorder and failure trace preorder have not yet been formulated.
4.4. Axiomatisation of string iteration String iteration (SI) [7] is a variation of PI, in which the first argument of iteration is allowed to contain non-empty finite strings of atomic actions. Aceto and Groote [7] extended the axiomatisation for PI in strong bisimulation to SI. Like P