The regular viewpoint on PA-processes.
PA is the process algebra allowing non-determinism, sequential and parallel compositions, and recursion. We suggest viewing PA-processes astrees, and usingtree-automata techniques for verification problems on PA. Our main result is that the set of iterated predecessors of a regular set of PA-processes is a regular tree language, and similarly for iterated successors. Furthermore, the corresponding tree automata can be built effectively in polynomial time. This has many immediate applications to verification problems for PA-processes, among which a simple and general model-checking algorithm.
Introduction
Veri-cation of In-nite State Processes is a very active -eld of research today in the
concurrency-theory community. Of course, there has always been an active Petri-nets com-
munity, but researchers involved in process algebra and model-checking really became interested
into in-nite state processes after the proof that bisimulation was decidable for normed
BPA-processes [BBK87]. This prompted several researchers to investigate decidability issues
for BPP and BPA (with or without the normedness hypothesis) (see [CHM94, Mol96, BE97]
for a partial survey).
From BPA and BPP to PA: BPA is the inon-determinism
recursionj fragment of process algebra. BPP is the inon-determinism parallel composition
recursionj fragment. PA (from [BEH95]) combines both and is much less tractable. A few
years ago, while more and more decidability results for BPP and BPA were presented, PA
was still beyond the reach of the current techniques. Then Mayr showed the decidability of
reachability for PA processes [May97c], and extended this into decidability of model-checking
for PA w.r.t. the EF fragment of CTL [May97b]. This was an important breakthrough,
allowing Mayr to successfully attack more powerful process algebras [May97a] while other
decidability results for PA were presented by him and other researchers (e.g. [Ku#96, Ku#97,
JKM98]).
A -eld asking for new insights: The decidability proofs from [May97b] (and the following
papers) are certainly not trivial. The constructions are quite complex and hard to
check. It is not easy to see in which directions the results and/or the proofs could be adapted
or generalized without too much trouble. Probably, this complexity cannot be avoided
with the techniques currently available in the -eld. We believe we are at a point where it
is more important to look for new insights, concepts and techniques that will simplify the
-eld, rather than trying to further extend already existing results.
Our contribution: In this paper, we show how tree-automata techniques greatly help
dealing with PA. Our main results are two Regularity Theorems, stating that Post   (L)
(resp. Pre   (L)) the set of con-gurations reachable from (resp. allowing to reach) a conguration
in L is a regular tree language when L is, and giving simple polynomial-time
constructions for the associated automata. Many important consequences follow directly,
including a simple algorithm for model-checking PA-processes.
Why does it work ? The regularity of Post   (L) and Pre   (L) could only be obtained
after we had the combination of two main insights:
1. the tree-automata techniques that have been proved very powerful in several -elds
(see [CKSV97]) are useful for the process-algebraic community as well. After all, PA
is just a simple term-rewrite system with a special context-sensitive rewriting strategy,
not unlike head-rewriting, in presence of the sequential composition operator.
RR n-0123456789
2. the syntactic congruences used to simplify notations in simple process algebras help one
get closer to the intended semantics of processes, but they break the regularity of
the behavior. The decidability results are much simpler when one only introduces
syntactic congruences at a later stage. (Besides, this is a more general approach.)
Plan of the paper: We start by recalling the basics of tree-automata theory (# 1) before
we introduce our de-nition for the PA process algebra (# 2). After we explain how sets of PA
processes can be seen as tree languages (# 3) we give a simple proof showing how Post   (t)
and Pre   (t) are regular tree languages and start listing applications to veri-cation problems.
We then move on to Post   (L) and Pre   (L) for L a regular language (# 5). These are our
main technical results and we devote # 6 to the important applications in model-checking.
We end up with an extension to reachability and model-checking under constraints (# 7) and
some simple but important techniques allowing to deal with PA processes modulo structural
equivalence (# 8).
Related work: Several recent works in the -eld use tree-automata to describe the behaviour
of systems. We use them to describe set of con-gurations.
The set of all reachable con-gurations of a pushdown automaton form a regular (word)
language. This was proven in [B#c64] and extended in [Cau92]. Applications to the model-checking
of pushdown automata have been proposed in [FWW97, BEM97].
The decidability of the -rst-order theory of the rewrite relation induced by a ground
term rewrite system relies on ground tree transducers [DT90] (note that PA is de-ned by a
conditional ground rewrite system).
Among the applications we develop for our regularity theorems, several have been suggested
by Mayr's work on PA [May97c, May97b] and/or our earlier work on RPPS [KS97a,
KS97b].
Regular tree languages and tree automata
We recall some basic facts on tree automata and regular tree languages. For more details,
the reader is referred to any classical source (e.g. [CDG
A ranked alphabet is a -nite set of symbols F together with an arity function
This partitions F according to arities: the set of
terms over F and call them -nite trees or just trees.
A tree language over F is any subset of T (F).
A (-nite, bottom-up) tree automaton A is a tuple hF ; Q; F; Ri where F is a ranked
alphabet, is a -nite set of states, F ' Q is the subset of -nal states, and R is
a -nite set of transition rules of the form f(q is the arity j(f)
of symbol f 2 F . Tree automata with "-rules also allow some transition rules of the form
The transition rules de-ne a rewrite relation on terms built on F [Q (seeing states from
Q as nullary symbols). This works bottom-up. At -rst the nullary symbols at the leaves
INRIA
The Regular Viewpoint on PA-Processes 5
are replaced by states from Q, and then the quasi-leaf symbols immediately on top of leaves
from Q are replaced by states from Q. We write t A
can be rewritten
(in some number of steps) to q 2 Q and say t is accepted by A if it can be rewritten into a
-nal state of A. We write L(A) for the set of all terms accepted by A. Any tree language
which coincide with L(A) for some A is a regular tree language. Regular tree languages are
closed under complementation, union, etc.
An example: Let F be given by F ffg. There is an
automaton accepting the set of all occurs an even number of times in t.
A is given by Q
g.
Let t be g(f(g(a); b)). A rewrites t as follows: g(f(g(a); b)) 7\Gamma! g(f(g(q 0
Hence t 7\Gamma! q 0 2 F so that t 2 L(A).
If we replace R by
we have an automaton accepting the set of all t where there is an even
number of g's along every path from the root to a leaf.
The size of a tree automaton, denoted by jAj, is the number of states of A augmented
by the size of the rules of A where a rule f(q 2. In this paper,
we shall never be more precise than counting jQj, the number of states of our automata.
Notice that, for a -xed F where the largest arity is m - 2, jAj is in O(jQj m ).
A tree automaton is deterministic if all transition rules have distinct left-hand sides
(and there are no "-rule). Otherwise it is non-deterministic. Given a non-deterministic tree
automaton, one can use the classical isubset constructionj and build a deterministic tree
automaton accepting the same language, but this construction involves a potential exponential
blow-up in size. Telling whether L(A) is empty for A a (non-necessarily deterministic)
tree automaton can be done in time O(jAj). Telling whether a given tree t is accepted by a
given (non-necessarily deterministic) A can be done in time polynomial in jAj
A tree automaton is completely speci-ed (also complete) if for each f 2 Fn and q
Q, there is a rule f(q adding a sink state and the obvious rules, any A
can be extended into a complete one accepting the same language.
2 The PA process algebra
For our presentation of PA, we explicitly refrain from writing terms modulo some simplication
laws (e.g. the neutral laws for 0). Hence our use of the IsNil predicate (see below),
inspired by [Chr93].
This viewpoint is in agreement with the earliest works on (general) process algebras like
CCS, ACP, etc. It is a key condition for the results of the next section, and it clearly does
not prevent considering terms modulo some structural congruence at a later stage, as we
demonstrate in section 8.
RR n-0123456789
6 D.Lugiez, Ph.Schnoebelen
2.1 Syntax
is a set of action names.
is a set of process variables.
is the set of PA-terms, given by the following abstract syntax
t;
Given t 2 EPA , we write Var(t) the set of process variables occurring in t and Subterms(t)
the set of all subterms of t (includes t).
A guarded PA declaration is a -nite set
a i
ng of process rewrite
rules. Note that the X i 's need not be distinct.
We write Var (\Delta) for the set of process variables occurring in \Delta, and Subterms (\Delta) the
union of all Subterms(t) for t a right- or a left-hand side of a rule in \Delta.
there is a rule iX a
! tj in \Deltag and \Delta(X) is S
a2Act \Delta a (X). Var ?
is the set of variables for which \Delta provides no rewrite.
In the following, we assume a -xed Var and \Delta.
2.2 Semantics
A PA declaration \Delta de-nes a labeled transition relation ! \Delta ' EPA \Theta Act \Theta EPA . We always
omit the \Delta subscript when no confusion is possible, and use the standard notations and
abbreviations: t w
inductively
de-ned via the following SOS rules:
a
a
a
a
(X a
a
a
a
a
where the predicate is inductively de-ned by
ae
true if
false otherwise.
The IsNil predicate is a syntactic test for termination, and indeed
Lemma 2.1. The following three properties are equivalent:
1.
2. t 6! (i.e. t is terminated),
3.
INRIA
The Regular Viewpoint on PA-Processes 7
Proof. (3 This derivation used has some X i
a i
induction over t to prove that
is obvious from the de-nition.
as a tree language
We shall use tree automata to recognize sets of terms from EPA . This is possible because
EPA is just a T (F) for F given by F kg. Of
course, we shall keep using the usual in-x notation for terms built with i:j or ikj.
We begin with one of the simplest languages in EPA :
Proposition 3.1. For any t, the singleton tree language ftg is regular, and an automaton
for ftg needs only have jtj states.
Similarly, an immediate consequence of Lemma 2.1 is
Corollary 3.2. L ? , the set of terminated processes, is a regular tree language, and an
automaton for L ? needs only have one state.
4 Regularity of the reachability set
For
Post   (t) def
denote the set of
iterated predecessors (resp. the set of iterated successors, also called the reachability set) of
t.
These notions do not take into account the sequences w 2 Act   of action names allowing
to move from some t to some t 0 in Post   (t). Indeed, we will forget about action names until
section 7 which is devoted to Pre   [C](t) and Post   [C](t) for C ' Act   .
Given two tree languages L; L 0 ' EPA , we let
4.1 Regularity of Pre
We de-ne (L t ) t2EPA , an in-nite family of tree languages, as the least solution of the following
set of recursive equations. The intuition is that these are quasi-regular equations satis-ed
RR n-0123456789
by Pre   (t).
Y a
Y a
Y a
Y a
Y a
(1)
Observe that all equations de-ne L t as containing all LY 's for Y a process variable allowing
a one step transition Y a
t.
Lemma 4.1. For any t 2 EPA , L
Proof. (Sketch) The proof that u
is an induction over the length of
the transition sequence from u to t, then a case analysis of which SOS rule gave the last
transition, and then an induction over the structure of t.
The proof that u 2 L t implies u
t is a -xpoint induction, followed by a case analysis
over which summand of which equation is used, and relies on simple lemmas about
reachability, such as it 1


The equations from (1) can easily be transformed into regular equations, just by introducing
new variables for sets ftg in the de-nitions for the L t:t 0 's. Now, because any given L t
only depends on a -nite number of L u 's and fug's, namely only for u's in Subterms(t) [
Subterms (\Delta), we have 1
Corollary 4.2. For any t 2 EPA , the set L t is a regular tree language.
and the corresponding tree automaton has O(j\Deltaj states. This entails
Theorem 4.3. For any t 2 EPA , Pre   (t), Pre(t) and Pre + (t) are regular tree languages.
4.2 Regularity of Post
We de-ne (L 0
two in-nite families of tree languages, as the least solution of the
following set of recursive equations. Our aim is that L 0
should coincide with
In section 5.1, we shall see that Corollary 4.2 holds even when \Delta is in-nite (but Var (\Delta) must be -nite).
INRIA
The Regular Viewpoint on PA-Processes 9
Post   (t) (resp. Post
X a
X a
(2)
Again, these can easily be turned into regular equations. Again, any given L 0
t or L 00
only
depends on a -nite number of L 0
u 's and fug's.
Corollary 4.4. For any t 2 EPA , the sets L 0
t and L 00
are regular tree languages.
and the corresponding tree automata have O(j\Deltaj states.
As with Pre   (t), we can easily show
Lemma 4.5. For any t 2 EPA , L 0
Post   (t) and L 00
hence the corollary
Theorem 4.6. For any t 2 EPA , Post   (t), Post(t) and Post + (t) are regular tree languages
that can be constructed eoeectively.
Theorems 4.3 and 4.6 will be generalized in sections 5 and 7. However, we found it
enlightening to give simple proofs of the simplest variants of our regularity results.
Already, Theorems 4.3 and 4.6 and the eoeective constructibility of the associated automata
have many applications.
4.3 Some applications
Theorem 4.7. The reachability problem iis t reachable from t 0 ?j is in P.
Proof. Combine the cost of membership testing for non-deterministic tree automata and the
regularity of Pre   (t 0 ) or the regularity of Post   (t).
For a dioeerent presentation of PA and ! \Delta , [May97c] shows that the reachability problem is
NP-complete. In section 8, we describe how to get his result as a byproduct of our approach.
Many other problems are solved by simple application of Theorems 4.3 and 4.6:
boundedness. Is Post   (t) in-nite ?
RR n-0123456789
covering. (a.k.a. control-state reachability). Can we reach a t 0 in which Y
(resp. do not occur).
inclusion. Are all states reachable from t 1 also reachable from t 2 ? Same question modulo
a regularity preserving operation (e.g. projection).
liveness. where a given \Delta live if, in all reachable states, at least one transition
from \Delta 0 can be -red.
5 Regularity of Post
(L) and Pre
(L) for a regular language
In this section we prove the regularity of Pre   (L) and Post   (L) for a regular language L.
For notational simplicity, given two states q; q 0 of an automaton A, we denote by q k q 0
state q 00 such that q k q 0 A
possibly using "-rules.
5.1 Regularity of Pre
Ingredients for A Pre   : Assume AL is an automaton recognizing L ' EPA . A Pre   is a
new automaton combining several ingredients:
ffl A? is a completely speci-ed automaton accepting terminated processes (see Corollary
3.2).
ffl AL is the automaton accepting L.
ffl We also use a boolean to record whether some rewriting steps have been done.
States of A Pre   : A state of A Pre   is a 3-tuple (q ?
where Q ::: denotes the set of states of the relevant automaton.
Transition rules of A Pre   : The transition rules of A Pre   are de-ned as follows:
type 0: all rules of the form 0 7\Gamma! (q
7\Gamma! q L .
type 1a: all rules of the form X 7\Gamma! (q ? ; q L ; true) s.t. there exists some u
7\Gamma! q L .
type 1b: all rules of the form X 7\Gamma! (q
7\Gamma! q L .
type 2: all rules of the form (q
type 3a: all rules of the form (q
state of A? .
INRIA
The Regular Viewpoint on PA-Processes 11
type 3b: all rules of the form (q
Lemma 5.1. For any t 2 EPA , t A Pre
there is some u 2 EPA and some p 2 N
such that t p
u, u A?
Proof. By structural induction over t. There are three cases:
1. Because A Pre   has no "-rules, we only have to observe that its rules of
type 0, 1a and 1b exactly correspond to what the lemma requires.
2.
required that, for
A Pre
there is a type 3 rule (q 1
The induction hypothesis entails there are t 1
corresponding to the
rewrite of t 1 and t 2 by A Pre   . Now if A Pre   used a type 3b rule, then b
. If we used a type 3a rule, then q 1
is a -nal state, therefore u 1 2 L? is a terminated process, hence t 1 :t 2
and
Conversely, assume
7\Gamma! q L . Then u is some
for
In the -rst case the ind. hyp. entails t 1
A Pre
AL
A Pre
Now we can use a type 3b rule to show t A Pre
with u AL
L .
In the second case,
AL
? a -nal state of A? . We
can use a type 3a rule to show t A Pre
3. This case is similar to the previous one (actually it is simpler).
If we now let the -nal states of A Pre   be all states (q q L is a -nal state of
AL , then t
! u for some u accepted by AL ioe A Pre   accepts t (this is where we use the
assumption that A? is completely speci-ed.)
Theorem 5.2. (Regularity)
(1) If L is a regular subset of EPA , then Pre   (L) is regular.
(2) Furthermore, from an automaton AL recognizing L, is it possible to construct (in polynomial
time) an automaton A Pre   recognizing Pre   (L). If AL has k states, then A Pre
needs only have 4k states.
RR n-0123456789
Proof. (1) is an immediate consequence of Lemma 5.1. Observe that the result does not
need the -niteness of \Delta (but Var (\Delta) must be -nite).
(2) Building A Pre   eoeectively requires an eoeective way of listing the type 1a rules. This
can be done by computing a product of AX , an automaton for Post + (X), with A? and
AL . Then there exists some u
7\Gamma! q L ioe the the language
accepted by the -nal states f(q a -nal state of AX g is not-empty. This gives
us the pairs q ? ; q L we need for type 1a rules. Observe that we need the -niteness of \Delta to
build the AX 's.
5.2 Regularity of Post
Ingredients for A Post   : Assume AL is an automaton recognizing L ' EPA . A Post   is a
new automaton combining several ingredients:
Automata A? and AL as in the previous construction, but this time we need to assume
each of them is a completely speci-ed automata.
A \Delta is a completely speci-ed automaton recognizing the subterms of \Delta. It has all
states q s for s 2 Subterms (\Delta). We ensure it A \Delta
by taking as transition
rules
belongs to Subterms (\Delta). In addition, the
automaton has a sink state q ? and the obvious transitions so that it is a completely
speci-ed automaton.
ffl Again, we use a boolean b to record whether rewrite steps have occurred.
States of A Post   : The states of A Post   are 4-uples (q ?
Transition rules of A Post   : The transition rules are:
type 0: all rules of the form 0 7\Gamma! (q
type 1: all rules of the form X 7\Gamma! (q
7\Gamma! q L , and
type 2: all "-rules of the form (q
s is a rule in \Delta
with X AL
7\Gamma! q L .
type 3: all rules of the form
type 4a: all rules of the form
INRIA
The Regular Viewpoint on PA-Processes 13
type 4b: all rules of the form
is a -nal state of
A? .
Lemma 5.3. For any t 2 EPA , t A Post
there is some u 2 EPA and some
such that u p
t, u AL
Proof. We -rst prove the ()) direction by induction over the length k of the rewrite t A Post
We distinguish four cases:
1. and we used a type 0 or type 1 rule. Taking
sati-es the requirements.
2. k ? 1 and the last rewrite step used a type 2 "-rule: Then the rewrite has the form
z -
true). By ind. hyp., there is a u 0 and a p 0 s.t.
t. Now u
The existence of the type 2 rule entails
t. Taking the requirements.
3. k ? 1 and the last rewrite step used a type 4 rule: Then t is some t 1 :t 2 and the
type 4 rule applied on top of two rewrite sequences t i 7\Gamma! (q i
2.
The ind. hyp. gives us, for
If the last rule was a type 4a rule, then b
t. Taking the requirements.
Otherwise the the last rule was a type 4b rule. Then q 1
? is a -nal state and t 1
A?
entails that t 1 is a terminated process. Hence
t. Again,
taking the requirements.
4. k ? 1 and the last rewrite step used a type 3 rule: This case is similar (actually
simpler) to the previous one.
For the (() direction, we assume u p
t with the accompanying conditions (a.c.), and
proceed by induction over the length of the transition sequence (i.e. over p), followed by
structural induction over u. There are -ve cases:
1. and the a.c.'s ensure we can use a type 0 rule to show t A Post
2. 0: Like the previous case but with a type 1 rule.
3. 0: Then the sequence has the form X 1
t. Here the a.c.'s read
Subterms (\Delta). If we now take a q 0
RR n-0123456789
14 D.Lugiez, Ph.Schnoebelen
s.t.
L (one such q 0
must exist) and let b 0 be false ioe the ind. hyp.
gives us t A Post
there must be a type 2 "-rule (q
We use it to show t A Post
4.
t is a combination of some u 1
with Additionally, if
For 2, The rewrites t A?
7\Gamma! q L and u A \Delta
used some t i
A?
AL
L and u i
A \Delta
If we now de-ne b i according to p i , the ind.
hyp. entails that, for
A Post
There are two cases. If t 1 2 L? then q 1
? is a -nal state of A? and A Post   has a type
4b rule (q 1
that we can use. If t 1 62 L? ,
then There is a type 4a rule that we can use.
5. Similar to the previous case (actually it is simpler).
If we now let the -nal states of A Post   be all states (q q L is a -nal state of
AL , then A Post   accepts a term t ioe u
t for a u accepted by AL ioe t belongs to Post   (L).
Theorem 5.4. (Regularity)
(1) If L is a regular subset of EPA , then Post   (L) is regular.
(2) Furthermore, from an automaton AL recognizing L, is it possible to construct (in polynomial
time) an automaton A Post   recognizing Post   (L). If AL has k states, then A Pre
needs only have O(k:j\Deltaj) states.
Proof. Obvious from the previous construction.
Our results relate t and Pre   (t) (resp. Post   (t)). A natural question is to ask if the
relation i
!j (i.e. f(t; u) j t
ug is recognizable in some sense. The most relevant notion of
recognizability related to our problem is linked to ground tree transducers, GTT's for short,
details. Since it can be shown that the
relation induced by a ground
rewrite system is recognizable by a GTT, we tried to extend this result to our PA case where
the rules are ground rewrite rules with simple left hand sides, but where there is a notion of
pre-x rewriting. Unfortunately, this pre-x rewriting entails that our
! is not stable under
contexts and the natural extensions of GTT that could handle such conditional rules are
immediately able to recognize any recursively enumerable relation.
6 Model-checking PA processes
In this section we show a simple approach to the model-checking problem solved in [May97b].
We see this as one more immediate application of our main regularity theorems.
INRIA
The Regular Viewpoint on PA-Processes 15
We consider a set P of atomic propositions. For
Mod (P ) denotes the set of PA processes for which P holds. We only consider propositions
P such that Mod (P ) is a regular tree-language. Thus P could be it can make an a-labeled
step right nowj, ithere is at least two occurences of X inside tj, ithere is exactly one occurence
of X in a non-frozen positionj,
The logic EF has the following syntax:
and semantics
Thus EX' reads iit is possible to reach in one step a state s.t. 'j and EF' reads iit is possible
to reach (via some sequence of steps) a state s.t. 'j.
De-nition 6.1. The model-checking problem for EF over PA has as inputs: a given \Delta, a
given t in EPA , a given ' in EF. The answer is yes ioe t
If we now de-ne Mod(') def
Mod
Mod
Theorem 6.2. (1) For any EF formula ', Mod (') is a regular tree language.
(2) If we are given tree-automata AP 's recognizing the regular sets Mod (P ), then a tree-
automaton A' recognizing Mod(') can be built eoeectively.
Proof. A corollary of (3) and the regularity theorems.
This gives us a decision procedure for the model-checking problem: build an automaton
for Mod (') and check whether it accepts t. We can estimate the complexity of this approach
in term of j'j and n alt (').
We de-ne n alt (') the number of alternation of negations and temporal connectives in '
as
RR n-0123456789
Theorem 6.3. (Model-checking) An automaton for Mod (') can be computed in time2 j'jj\Deltaj2 O(j'jj\Deltaj)
Proof. We assume all automata for the Mod (P )'s have size bounded by M (a constant).
We construct an automaton for Mod (') by applying the usual automata-theoretic constructions
for intersection, union, complementation of regular tree languages, and by invoking
our regularity theorems for Pre and Pre   . All constructions are polynomial except for
complementation. With only polynomial constructions, we would have a 2 O(j'j) size for
the resulting automaton. The negations involving complementation are the cause of the
non-elementary blowup.
Negations can be pushed inward except that they cannot cross the temporal connectives
EF and EX. Here we have one exponential blowup for determinization at each level of
alternation. This is repeated n alt (') times, yielding the given bound on the number of
states hence the overall complexity.
The procedure described in [May97b] is non-elementary and today the known lower
bound is PSPACE-hard. Observe that computing a representation of Mod(') is more general
than just telling whether a given t belongs to it. Observe also that our results allow
model-checking approches based on combinations of forward and backward methods (while
Theorem 6.2 only relied on the standard backward approach.)
7 Reachability under constraints
In this section, we consider reachability under constraints. Let C ' Act   be a (word)
language over action names. We write t C
that t 0 can be reached from t under the constraint C. We extend our notations and write
Pre   [C](L), Post   with the obvious meaning.
Observe that, even if we assume C is regular, the problem of telling whether t C
!, i.e.
whether Post   [C](t) is not empty, is undecidable for the PA algebra. This can be proved
by a reduction from the intersection problem for context-free languages as follows: Let \Sigma
be an alphabet and # some distinguished symbol. We use two copies a; a of every letter
a in \Sigma [ f#g. Context-free languages can be de-ned in BPA (PA without k), that is, for
any context-free language L 1 (resp. L 2 ) on \Sigma, we can de-ne PA rules such that X 1
w:#
w:#
These rules don't overlap. We now introduce the regular
an
holds ioe
is undecidable.
INRIA
The Regular Viewpoint on PA-Processes 17
In this section we give suOEcient conditions over C so that the problem becomes decidable
(and so that we can compute the C-constrained Pre   of a regular tree language).
Recall that the shu-e w k w 0 of two -nite words is the set of all words one can obtain
by interleaving w and w 0 in an arbitary way.
De-nition 7.1. ffl
m )g is a (-nite) seq-decomposition of C ioe for
all w; w 0 2 Act   we have
m )g is a (-nite) paral-decomposition of C ioe for all w; w
we have
The crucial point of the de-nition is that a seq-decomposition of C must apply to all
possible ways of splitting any word in C. It even applies to a decomposition w:w 0 with
so that one of the C i 's (and one of the C 0
contains ''. Observe that the
formal dioeerence between seq-decomposition and paral-decomposition comes from the fact
that w k w 0 , the set of all shu-es of w and w 0 usually contains several elements.
De-nition 7.2. A family Cng of languages over Act is a -nite decomposition
system ioe every C 2 C admits a seq-decomposition and a paral-decomposition only using C i 's
from C .
Not all C ' Act   admit -nite decompositions, even in the regular case. Consider
(ab)   and assume
is a -nite paral-decomposition. Then for every k, there is
a shu-e of a k and b k in C. Hence there must be a
. Now if
then there there must exist a shu-e w 00 of a k and b k 0
with w 00 2 C. This is only
possible . Hence all i k 's are distinct, contradicting -niteness.
A simple example of a -nite decomposition system is i.e. the set
of all singleton languages with words shorter than k. Here the paral-decomposition of fwg
is f(fw 1
g)g where the w i 's are all subwords 2 of w (and w 0
i is the
corresponding remainder). This example shows that decomposability is not composability:
not all pairs from C appears in the decomposition of some member of C.
More generally, for any linear weight function ' of the form '(w) def
with
N, the sets C ('=k)
belong to -nite decomposition system.
Assume C is a -nite decomposition system. We shall show
Theorem 7.3. (Regularity)
For any regular L ' EPA and any C 2 C , Pre   [C](L) and Post   [C](L) are regular tree
languages.
A subword of w is any w 0 obtained by erasing letters from w at any position.
RR n-0123456789
Ingredients for A Post   [C] : We build A Post   [C] in the same way as A Post   but states contain
a new C 2 C component.
States of A Post   [C] : The states of A Post   [C] are 5-uples (q ?
Transition rules of A Post   [C] : The transition rules are:
type 0: all rules of the form 0 7\Gamma! (q
type 1: all rules of the form X 7\Gamma! (q
type 2: all "-rules of the form (q
s is
a rule in \Delta with X AL
appears in the
seq-decomposition of C.
type 3: all rules of the form
appears in the paral-decomposition of C 00 .
type 4a: all rules of the form
type 4b: all rules of the form
state of A? s.t. (C; C 0 ) appears in the seq-decomposition of C 00 .
Lemma 7.4. For any t 2 EPA , t
A Post   [C]
there is some u 2 EPA and
some w 2 C such that u w
t, u AL
Proof. A Post   [C] is A Post   equipped with a new component and the proof follows exactly
the lines of the proof of Lemma 5.3. We refer to this earlier proof and only explain how we
deal with the new C components.
The ()) direction is as in lemma 5.3. The new observations in the 4 cases are:
1. that we can take
2. k ? 1 and the last rewrite step used a type 2 "-rule: Use the fact that w
3. k ? 1 and the last rewrite step used a type 4 rule: Use the fact that C:C 0 ' C 00 .
4. k ? 1 and the last rewrite step used a type 3 rule: Use the fact that w 1 2 C and
entail that there exists at least one shu-ing w of w 1 and w 2 s.t. w 2 C 00 .
INRIA
The Regular Viewpoint on PA-Processes 19
The (() direction is as in lemma 5.3. The new observations in the 5 cases are:
1. 0: The type 0 rules allow all C's containing ''.
2.
3. 0: Then the sequence has the form X a
t. Now if
there must be a (C in the seq-decomposition of C s.t. a 2 C 0 and w
that there is a type 2 rule C) we can use.
4.
and we have the type 4a rule we need. Otherwise there is a pair (C in the seq-
decomposition of C s.t. w This pair gives us the type 4b rule we
need.
5.
some shu-e of w 1 and w 2 . Therefore
there is a in the paral-decomposition of C s.t. w This pair
gives us the type 3 rule we need.
If we now let the -nal states of A Post   [C] be all (q is a -nal state of
AL , then A Post   [C] accepts a term t ioe t 2 Post   [C](t). (The set of -nal states can easily be
adapted so that we recognize Post
Ingredients for A Pre   [C] : Same as in the construction of A Pre   , with an additional C 2 C
component.
States of A Pre   : A state of A Pre   is a 4-tuple (q ?
The -nal states are all (q is a -nal state of AL and C i the constraint
to satisfy.
Transition rules of A Pre   : The transition rules of A Pre   are de-ned as follows:
type 0: all rules of the form 0 7\Gamma! (q
type 1a: all rules of the form X 7\Gamma! (q ? ; q L ; true; C) s.t. there exists some u
with u A?
7\Gamma! q L .
type 1b: all rules of the form X 7\Gamma! (q
type 2: all rules of the form
appears in
the paral-decomposition of C 00 .
RR n-0123456789
type 3a: all rules of the form
is a -nal state of A?
and (C; C 0 ) appears in the seq-decomposition of C 00
type 3b: all rules of the form
Lemma 7.5. For any t 2 EPA , t
A Pre   [C]
there is some u 2 EPA and some
u, u A?
Proof. A Pre   [C] is A Pre   equipped with a new component and the proof follows exactly the
lines of the proof of Lemma 5.3. We refer to this earlier proof and only explain how we deal
with the new C components.
1. X: The conditions on the C component for the existence of rules of type 0,
1a and 1b agree with the statement of the lemma.
2.
A Pre
there is a type 3
rule C). Also, the ind. hyp. gives t i
In the type 3b case, w 1 2 C. In the type 3a case, we use C
Here we have either (1)
In the -rst case we apply the induction hypothesis with C itself on t 1 and some C 0
containing " on t 2 , then we can use a type 3b rule. In the second case, there must be
a in the seq-decomposition of C, with w and we just have to use
the ind. hyp. and a type 3a rule.
3. This case is similar to the previous one. The (() direction uses the pair
accouting for w in the paral-decomposition of C. The ()) direction uses the
crucial fact that whenever t i
shu-ing w of w 1 and w 2 , in particular for the w that C must contain.
7.1 Applications to model-checking
The above results let us apply the model-checking method from section 6 to an extended
EF logic where we now allow all hCi' formulas for decomposable C. The semantics is given
by Mod (hCi') def
INRIA
The Regular Viewpoint on PA-Processes 21
Decomposability of C is a quite general condition. It excludes the undecidable situations
that would exist in the general regular case and immediately includes the extensions proposed
in [May97b].
Observe that it is possible to combine decomposable constraints already in the model-checking
algorithm: when C 2 C and C are decomposable, we can deal with hC "
directly (i.e. without constructing a -nite decomposition system containing C and C 0 )
because it is obvious how to extend the construction for A Pre   [C] to some A Pre   [C;C 0 ] where
several C components are dealt with simultaneously.
We can also deal with hC [ C 0 i' and hC:C 0 i' directly since Pre   [C [ C 0 ](L) and
Pre   [C:C 0 ](L) are Pre   [C](L) [ Pre   [C 0 ](L) and Pre   [C](Pre   [C 0 ](L)) for any C; C 0 and
L.
8 Structural equivalence of PA terms
In this section we investigate the congruence j induced on PA terms by the following
equations:
This choice of equations is motivated by the fact that several recent works on PA (and
extensions) only consider processes up-to this same congruence. Our techniques could deal
with variants.
It is useful to explain how our de-nition of PA compares with the de-nition used
in [May97c, May97b]. We consider a transition system between terms from EPA . The
terms Mayr considers for his transition system can be seen as equivalence classes, modulo
j, of our EPA terms. Write [t] j for the set ft g. The transition relation used by
Mayr coincides with a transition relation de-ned by
a
In the following, we speak of iPAj j when we mean the transition system one obtains with
j-classes of terms as states, and transitions given by (4).
Our approach is more general in the sense that we can de-ne the other approach in
our framework. By contrast, if one reasons modulo j right from the start, one loses the
information required to revert to the other approach.
For example, the reachability problem ido we have t
u ?j from Theorem 4.7 asks for
a very precise form for u. The reachability problem solved in [May97c] asks for u modulo j.
In our framework, this can be stated as igiven t and u, do we have t 0
RR n-0123456789
22 D.Lugiez, Ph.Schnoebelen
and (see below). In the other framework, it is impossible to state our problem.
(But of course, the -rst motivation for our framework is that it allows the two regularity
theorems.)
The rest of this section is devoted to some applications of our tree-automata approach
to problems for PAj . The aim is not exhaustivity. Rather, we simply want to show that
our framework allows solving (not just stating) problems from the other framework and its
variants.
8.1 Structural equivalence and regularity
are the associativity-commutativity axioms satis-ed by : and k. We call
them the permutative axioms and write t =P u when t and t 0 are permutatively equivalent.
are the axioms de-ning 0 as the neutral element of : and k. We call them the
simpli-cation axioms and write t & u when u is a simpli-cation of t, i.e. u can be obtained
by applying the simpli-cation axioms from left to right at some positions in t. Note that
& is a (well-founded) partial ordering. We write . for (&) \Gamma1 . The simpli-cation normal
form of t, written t#, is the unique u one obtains by simplifying t as much as possible (no
permutation allowed).
Such axioms are classical in rewriting and have been extensively studied [BN98]. j
coincide with (=P because the permutative axioms commute with the
simpli-cation axioms, we have
This lets us decompose questions about j into questions about =P and questions about &.
We start with =P .
Lemma 8.1. For any t, the set [t] =P
ug is a regular tree language, and an
automaton for [t] =P needs only have m:(m=2)! states if
Proof. (Sketch) This is because [t] =P is a -nite set with at most (m=2)! elements. (The
exponential blowup cannot be avoided.)
The simpli-cation axioms do not have the nice property that they only allow -nitely
many combinations, but they behave better w.r.t. regularity. Write [L] & for fu j t &
Lemma 8.2. For any regular L, the sets [L] . , [L] & , and [L]# are regular tree languages.
From an automaton AL recognizing L, we can build automata of size O(jAj) for these three
languages in polynomial time.
Proof. 1. [L] . : u is in [L] . ioe u is some t 2 L with additional 0's that can be simpli-ed
out. Hence an automaton accepting [L] . is obtained from AL by adding a new state q 0
for the subterms that will be simpli-ed. We also add rules 0 7\Gamma! q 0 , q 0 k q 0 7\Gamma! q 0 , and
INRIA
The Regular Viewpoint on PA-Processes 23
accepting these subterms, and, for any q in AL , rules q:q 0 7\Gamma! q, q 0 :q 7\Gamma! q,
simulating simpli-cation.
2. have been simpli-ed. A simple
way to obtain an automaton for [L] & is to synchronize the automaton AL accepting L with
the complete automaton A 0 recognizing terms built with 0, : and k only. A 0 has only two
states: q 0 and q 6=0 .
Once the two automata are synchronized, we have t 7\Gamma! (q; q 0
7\Gamma! q and t A0
We simulate simpli-cation of nullable terms with additional "-rules. Namely, whenever there
is a rule (q
we add an "-rule (q
add a symmetric rule if q 0
do the same for : instead of k.
Now a routine induction on the length of derivations shows that s 7\Gamma! (q; q 0 ) ioe 9t 2 L
7\Gamma! q.
3. [L]#: The simplest way to see regularity is to note that [L]# is
Note that for a regular L, [L] =P and [L] j are not necessarily regular [GD89]. However we
have
Proposition 8.3. For any t, the set [t] j is a regular tree language, and an automaton for
needs only have m:(m=2)! states if
Proof. Combine (5) with lemmas 8.1 and 8.2.
8.2 Structural equivalence and behaviour
Seeing terms modulo j does not modify the observable behaviour because of the following
standard result:
Proposition 8.4. j is a bisimulation relation, i.e. for all t j t 0 and t a
! u there is a
The proof is standard but tedious. We shall only give a proof sketch.
Proof. For any single equation l = r in the de-nition of j, we show that the set
f(loe; roe)g of all instances of the equation is a bisimulation relation. A complete proof of this
for takes the better part of p 95 of the book [Mil89] and the other equations can be
dealt with similarly, noting that IsNil() is compatible with j. Then there only remains to
prove that the generated congruence is a bisimulation. This too is standard: the SOS rules
for PA obey a format ensuring that the behaviour of a term depends on the behaviour of its
subterms, not their syntax.
We may now de-ne a new transition relation between terms: t a
some u; u 0 . This amounts to the i[t] j
a
from (4) and is the simplest way to translate
RR n-0123456789
problems for PAj into problems for our set of terms.
We adopt the usual abbreviations
Proposition 8.5. For any w 2 Act   , t w
Proof. By induction on the length of w, and using Proposition 8.4.
8.3 Reachability modulo j
Now it is easy to prove decidability of the reachability problem modulo j: t
Post   (t)"
Recall that [u] j and Post   (t) are regular tree-languages one can build eoeectively.
Hence it is decidable whether they have a non-empty intersection.
This gives us a simple algorithm using exponential time (because of the size of [u] j ).
Actually we can have a better result 3 :
Theorem 8.6. The reachability problem in PAj , igiven t and u, do we have t
in NP.
Proof. NP-easiness is straightforward in the automata framework: We have t
for some u 0 s.t. note that ju 00 j - juj. A simple algorithm
is to compute u#, then guess non-deterministically a permutation u 00 , then build automata
A 1 for [u 00 ] & and A 2 for Post   (t). These automata have polynomial-size. There remains to
checks whether A 1 and A 2 have a non-empty intersection to know whether the required u 0
exists.
Corollary 8.7. The reachability problem in PAj is NP-complete.
Proof. NP-hardness of reachability for BPP's is proved in [Esp97] and the proof idea can be
reused in our framework. We reduce 3SAT to reachability in PAj . Consider an instance P
of 3SAT. P has m variables and n clauses, so that it is some
every \Gammag. We de-ne the following
r i;j for
(Note that j).) The (R1) rules pick a valuation v for the X r 's, the (R3) rules
use v to list satis-ed clauses, the (R2) rules discard unnecessary elements. Finally
Other applications are possible, e.g.:
First proved in [May97c]
INRIA
The Regular Viewpoint on PA-Processes 25
Proposition 8.8. The boundedness problem in PAj is decidable in polynomial-time.
Proof. [t] j can only reach a -nite number of states in PAj ioe t can only reach a -nite
number of non-j terms in PA. Now because the permutative axioms only allow -nitely
many variants of any given term, Post   (L) contains a -nite number of non-j processes ioe
[Post   (L)]# is -nite.
8.4 Model-checking modulo j
The model-checking problem solved in [May97b] considers the EF logic over PAj . Translated
into our framework, this amounts to interpret the temporal connectives in terms of ) instead
of !: if we write Mod j (') for the interpretation modulo j, we have
Mod
Additionally, we only consider atomic propositions P compatible with j, i.e. where t
and t j u imply u
Model-checking in PAj is as simple as model-checking in PA:
Lemma 8.9. For any EF-formula ' we have Mod j
Proof. By structural induction over ', using Prop. 8.5 and closure w.r.t. j for the hCi'
case.
The immediate corollary is that we can use exactly the same approach for model-checking
in PA with or without j.
Conclusion
In this paper we showed how tree-automata techniques are a powerful tool for the analysis
of the PA process algebra. Our main results are two general Regularity Theorems with
numerous immediate applications, including model-checking of PA with an extended EF
logic.
The tree-automata viewpoint has many advantages. It gives simpler and more general
proofs. It helps understand why some problems can be solved in P-time, some others in
NP-time, etc. It is quite versatile and many variants of PA can be attacked with the same
approach.

Acknowledgments

We thank H. Comon and R. Mayr for their numerous suggestions,
remarks and questions about this work.
RR n-0123456789
26 D.Lugiez, Ph.Schnoebelen



--R

Decidability of bisimulation equivalence for processes generating context-free languages
More in-nite results
Verifying in-nite state processes with sequential and parallel composition
Reachability analysis of pushdown auto- mata: Application to model-checking
Rewriting and All That.

On the regular structure of pre-x rewriting
Tree automata and their application
Decidable subsets of CCS.
Decidability and decomposition in process algebras.
Applications of Tree Automata in Rewriting
The theory of ground rewrite systems is decidable.
Petri nets
A direct symbolic approach to model checking pushdown systems (extended abstract).
The reachability problem for ground TRS and some extensions.


A model for recursive-parallel programs
A formal framework for the analysis of recursive- parallel programs


Combining Petri nets and PA-processes
Model checking PA-processes
Tableaux methods for PA-processes
Communication and Concurrency.

--TR
Decidability of bisimulation equivalence for processes generating context-free languages
Process algebra
On the regular structure of prefix rewriting
Petri nets, commutative context-free grammars, and basic parallel processes
Tree languages
rewriting and all that
Efficient algorithms for pre* and post* on interprocedural parallel flow graphs
An automata-theoretic approach to branching-time model checking
Communication and Concurrency
A Formal Framework for the Analysis of Recursive-Parallel Programs
Combining Petri Nets and PA-Processes
Bisimulation Equivanlence Is Decidable for Normed Process Algebra
Decidable First-Order Transition Logics for PA-Processes
Deciding Bisimulation-Like Equivalences with Finite-State Processes
The Reachability Problem for Ground TRS and Some Extensions
Reachability Analysis of Pushdown Automata
How to Parallelize Sequential Processes
Infinite Results
Model Checking PA-Processes
An Automata-Theoretic Approach to Interprocedural Data-Flow Analysis
Regularity is Decidable for Normed PA Processes in Polynomial Time
Tableau Methods for PA-Processes

--CTR
Ahmed Bouajjani , Javier Esparza , Tayssir Touili, A generic approach to the static analysis of concurrent programs with procedures, ACM SIGPLAN Notices, v.38 n.1, p.62-73, January
Vineet Kahlon , Aarti Gupta, On the analysis of interacting pushdown systems, ACM SIGPLAN Notices, v.42 n.1, January 2007
Anne Labroue , Philippe Schnoebelen, An automata-theoretic approach to the reachability analysis of RPPS systems, Nordic Journal of Computing, v.9 n.2, p.118-144, Summer 2002
Markus Mller-Olm, Precise interprocedural dependence analysis of parallel programs, Theoretical Computer Science, v.311 n.1-3, p.325-388, 23 January 2004
Antonn Kuera , Philippe Schnoebelen, A general approach to comparing infinite-state systems with their finite-state specifications, Theoretical Computer Science, v.358 n.2, p.315-333, 7 August 2006
Denis Lugiez , Philippe Schnoebelen, Decidable first-order transition logics for PA-processes, Information and Computation, v.203 n.1, p.75-113, November 25, 2005
Kamal Lodaya, A regular viewpoint on processes and algebra, Acta Cybernetica, v.17 n.4, p.751-763, January 2006
verification of infinite-state systems;process algebra;tree automata