
<=<=
<=<=
<=<=
<=<=
<=
<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<=

<=
<= <=
<= <=
<=

<=

<=

<=
<=

<=

<=

<=
<=

<=

<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=
<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

<=
<=

Universität Stuttgart

Fakultät Informatik

?

Institut für Informatik

Breitwiesenstraße 20-22

D-70565 Stuttgart

Complexity Results for

Confluence Problems

Markus Lohrey

Report Nr. 1999/05


March 4, 1999

1


Abstract

We study the complexity of the confluence problem for restricted kinds 
of semi{ Thue systems, vector replacement systems and general trace 
rewriting systems. We prove that confluence for length{reducing 
semi{Thue systems is P{complete and that this complexity reduces to AC1 
in the monadic case (where all right{ hand sides consist of at most one 
symbol). For length{reducing vector replacement systems we prove that 
the confluence problem is PSPACE{complete and that the complexity 
reduces to NP and P, respectively, for monadic vector replacement 
systems and special vector replacement systems (where all right{hand 
sides are empty), respectively. Finally we prove that for special trace 
rewriting systems, confluence can be decided in polynomial time and that 
the extended word problem for special trace rewriting systems is 
undecidable.

1 Introduction

Rewriting systems that operate on different kinds of objects have 
received a lot of attention in computer science and mathematics. For all 
kinds of rewriting systems, confluence and termination are two of the 
most interesting properties. Together they guarantee the existence of 
unique normalforms.

Two of the most intensively studied types of rewriting systems are 
rewriting systems on free monoids, which are better known as semi{Thue 
systems [BO93], and rewriting systems on free commutative monoid, which 
are better known as vector replacement systems or Petri nets. Both of 
these types of rewriting systems may be seen as special cases of trace 
rewriting systems [Die90b]. Trace rewriting systems operate on free 
partially commutative monoids, which are in computer science better 
known as trace monoids. Trace monoids were introduced by [Maz77] into 
computer science as a model of concurrent systems.

Several decidability and undecidability results are known for the 
confluence problem for the different types of rewriting systems 
mentioned above. Let us just mention a few of these results. It is known 
that for length{reducing semi{ Thue systems confluence can be decided in 
polynomial time [BO81, KKMN85]. In contrast to this result there exists 
a trace monoid such that confluence is undecidable for length{reducing 
trace rewriting systems over this trace monoid [NO88]. In [Loh98] this 
result was even sharpened. It was shown that unless the underlying trace 
monoid is free or free commutative, confluence is undecidable for 
length{reducing trace rewriting systems. Concerning vector replacement 
systems it was shown in [VRL98] that confluence is decidable but 
EXSPACE{ hard for the class of all vector replacement systems.

In this paper we continue the investigation of the confluence problem 
for restricted kinds of trace rewriting systems. In Section 3 we prove 
that the confluence problem for length{reducing semi{Thue systems is not 
only solvable in polynomial time but furthermore P{complete, which 
roughly means that it is inherently sequential. On the other hand we 
prove that for the more restricted class of monadic semi{Thue systems 
(where monadic means that all right{hand sides consist of at most one 
symbol) there exists an e?cient parallel algorithm (more precisely an 
AC1{algorithm) that decides confluence. Concerning vector replacement 
systems we prove in Section 4 that for the length{reducing case, 
confluence is PSPACE{complete and that this complexity reduces for the 
monadic case and the special case (where special means that all 
right{hand sides are empty), respectively, to NP and P, respectively. 
Finally in Section 5 we prove that confluence is decidable for special 
trace rewriting systems in polynomial time which solves a question from 
[Die90b]. We end this paper by showing that in contrast to semi{Thue 
systems the extended word problem [BO85] is undecidable even for special 
trace rewriting systems that contain only one rule.

1


2 Preliminaries

In this section we will introduce some notations that we will use in 
this paper. Given an alphabet ?, ?? denotes the set of all finite words 
of elements of ?. The empty word is denoted by 1. As usual ?+ = ??nf1g. 
The number of occurrences of a 2 ? in the word s is denoted by jsja. The 
length of the word s is denoted by jsj. The set fs 2 ?? j jsj = ng is 
denoted by ?n. The set of all letters that occur in the word s is 
denoted by alph(s). The word s written in reverse order is denoted by 
srev. A context{free grammar G, briefly CFG, is a tuple G = (N; ?; P; S) 
where N and ? are disjoint alphabets of non{terminal symbols and 
terminal symbols, respectively, P is the set of productions which is a 
finite subset of N ? (N [ ?)?, and S 2 N is the start symbol. A 
production (A; ff) is usually written as A ) ff. Given A 2 N , we denote 
by L(G; A) the set of all elements in ?? that can be derived by G, 
starting from A. Finally L(G) = L(G; S). We say that G is 1{free if for 
every production (A ) ff) 2 P it holds ff 6= 1. Let a1; a2; : : : ; an 
be a fixed linear ordering of the alphabet ?. A commutative word over ? 
is a word of the form ae11 ae22 ? ? ? aen n , where
e1; : : : ; en 2 N. In particular 1 = a01 ? ? ? a0n and jae11 ? ? ? aen
n j = e1 + ? ? ? + en. The
set of all commutative words over ? is denoted by ??. The concatenation 
of two commutative words ad11 ? ? ? adn
n and ae11 ? ? ? aen
n is ad1+e1
1 ? ? ? adn+en
n . In this
way ?? becomes isomorphic to the free commutative monoid Nj?j . For a 
natural number n 2 N let ld (n) denote the logarithm of n to the base 2. 
Furthermore let bit(n) = bld (n)c + 1 if n > 0 and bit(0) = 1, i.e., 
bit(n) is the length of the binary representation of n. For ae11 ? ? ? 
aen
n 2 ?? we define bit(s) = Pn
i=1 bit(ei).
We assume that the reader is familiar with the basic notions of 
complexity theory, in particular with the complexity classes P, NP, and 
PSPACE, see for instance [Pap94]. In the following we introduce some 
notions concerning circuit complexity, see [BS90] for more details. All 
Boolean circuit that we consider in this paper are built from AND, OR, 
and NOT{gates. A Boolean circuit with n (linearly ordered) input nodes 
and exactly one output node accepts a language L ? fa; bgn in the 
obvious way. By encoding an arbitrary alphabet with more than two 
symbols into the alphabet fa; bg, a Boolean circuit can also accept a 
language L ? ?n, where ? is an arbitrary alphabet. Let F = fCn j n >= 0g 
be a family of Boolean circuits, where Cn accepts a subset of ?n. We say 
that F is uniform if the function n 7! Cn can be computed in 
deterministic logarithmic space. Note that this implies that there 
exists a polynomial p(n) such that Cn contains at most p(n) many gates. 
For k >= 0, ACk denotes the set of all languages L such that there 
exists a uniform family fCn j n >= 0g of Boolean circuits such that the 
following holds: There exists a constant c > 0 such that the depth of 
the circuit Cn (i.e. the length of the longest path from an input node 
to the unique output node) is at most c ? ld k(n), the fan{in (i.e. the 
number of inputs) of each AND and OR{gate is unbounded (but since the 
number of gates is bounded by a polynomial the same can be assumed for 
the fan{in), and finally Cn accepts the language ?n \ L. The class NCk 
is defined in the same way, but only gates of fan{in at most two are 
allowed. Finally NC = S
k>=0 NCk. The problems in NC are viewed as those problems that can

2


be e?ciently parallelized. By allowing circuits with more than one 
output node it is possible to define classes of functions that 
correspond to ACk, NCk, and NC. We omit the obvious formal definition, 
and just say that a particular function can be calculated for instance 
in ACk. In particular we use reduction functions between instances of 
computational problems that can be calculated in AC0 and which are 
therefore also computable in deterministic logarithmic space by well 
known results, see e.g. [Pap94], Theorem 16.1. Since an AND{gate of 
fan{in m can be replaced by a tree of height ld (m) which consists of 
AND{gates of fan{in two, and similarly for OR{gates, the following 
hierarchie is obvious.

NC0 ? AC0 ? NC1 ? AC1 ? NC2 ? ? ? ? ? NC ? P

For most of these inclusions it is unknown whether they are proper. In 
particular it is an open problem whether NC = P. It is generally 
believed that NC ( P. If this is true then problems that are P{complete 
under NC{reductions cannot be contained in NC, i.e., are inherently 
sequential.

In the following we introduce some notions from trace theory, see [DR95] 
for more details. An independence alphabet is an undirected graph (?; 
I), where ? is a finite alphabet and I ? ??? is an irreflexive and 
symmetric relation, called an independence relation. Given an 
independence alphabet (?; I) we define the trace monoid M (?; I) as the 
quotient monoid ??=?I , where ?I denotes the least equivalence relation 
that contains all pairs of the form (sabt; sbat) for (a; b) 2 I and s; t 
2 ??, which is a congruence on ??. An element of M (?; I), i.e., an 
equivalence class of words, is called a trace. The trace that contains 
the word s is denoted by [s]I . The neutral element of M (?; I) is the 
empty trace [1]I which will be also denoted by 1. Concatenation of 
traces is defined by [s]I [t]I = [st]I . Since for all words s; t 2 ??, 
s ?I t implies jsj = jtj and alph(s) = alph(t), we can define j[s]I j = 
jsj and alph([s]I ) = alph(s). The independence relation I can be lifted 
to M (?; I) by u I v if alph(u)?alph(v) ? I . For the rest of this 
section let (?; I) be an independence alphabet and let M = M (?; I). If 
I = (? ? ?)nId?, where Id? = f(a; a) j a 2 ?g, then M is isomorphic to 
the free commutative monoid Nj?j ' ??. On the other hand if I = ; then M 
is isomorphic to the free monoid ??. The following lemma is a 
generalization of Levi's lemma for traces [CP85], which states that for 
u1; u2; v1; v2 2 M it holds u1u2 = v1v2 if and only if there exist wi;j 
2 M (1 <= i; j <= 2) such that ui = wi;1wi;2, vi = w1;iw2;i (1 <= i <= 
2) and w1;2 I w2;1. The following lemma can be proved by induction on n 
+m using Levi's lemma for the case n = 2 = m.

Lemma 2.1. Let u1; : : : ; um; v1; : : : ; vn 2 M . Then it holds

u1u2 : : : um = v1v2 : : : vn

if and only if there exist wi;j 2 M (1 <= i <= m, 1 <= j <= n) such that

- ui = wi;1wi;2 : : : wi;n for every 1 <= i <= m,

- vj = w1;jw2;j : : : wm;j for every 1 <= j <= n, and

- wi;j I wk;l if 1 <= i < k <= m and 1 <= l < j <= n.

3


The situation in the lemma can be visualized by the diagram below, where 
n = m = 5. The i{th column corresponds to ui, the j{th row corresponds 
to vj and the intersection of the i{th column and the j{th row 
represents wi;j . Furthermore wi;j and wk;l are independent if one of 
them is north{west of the other one.

v5 w1;5 w2;5 w3;5 w4;5 w5;5
v4 w1;4 w2;4 w3;4 w4;4 w5;4
v3 w1;3 w2;3 w3;3 w4;3 w5;3
v2 w1;2 w2;2 w3;2 w4;2 w5;2
v1 w1;1 w2;1 w3;1 w4;1 w5;1

u1 u2 u3 u4 u5

Proof. We use induction on m + n. The case m = 1 or n = 1 is trivial. 
Thus let m > 1 and n > 1. Levi's lemma applied to the identity (u1 ? ? ? 
um?1)um = (v1 ? ? ? vn?1)vn gives four traces x, u, v and wm;n such that

u1u2 ? ? ? um?1 = xv; v1v2 ? ? ? vn?1 = xu; um = uwm;n; vn = vwm;n; u I 
v.

Next we apply the induction hypothesis to the identity u1u2 ? ? ? um?1 = 
xv. We obtain traces y1; y2; : : : ; ym?1 and w1;n; w2;n; : : : wm?1;n 
such that

x = y1y2 ? ? ? ym?1; v = w1;nw2;n ? ? ? wm?1;n;

ui = yiwi;n (1 <= i <= m? 1); yk I wi;n if 1 <= i < k <= m? 1.

Similarly, by the induction hypothesis applied to the identity v1v2 ? ? 
? vn?1 = xu there exist traces z1; z2; : : : ; zn?1 and wm;1; wm;2; : : 
: wm;n?1 such that

x = z1z2 ? ? ? zn?1; u = wm;1wm;2 ? ? ? wm;n?1;

vj = zjwm;j (1 <= j <= n ? 1); zi I wm;j if 1 <= j < i <= n ? 1.

Thus y1y2 ? ? ? ym?1 = x = z1z2 ? ? ? zn?1. The induction hypothesis 
applied to this identity gives traces wi;j (1 <= i <= m? 1, 1 <= j <= n 
? 1) such that

- yi = wi;1wi;2 : : : wi;n?1 for every 1 <= i <= m? 1,

- zj = w1;jw2;j : : : wm?1;j for every 1 <= j <= n ? 1, and

- wi;j I wk;l if 1 <= i < k <= m? 1 and 1 <= l < j <= n ? 1.

Altogether we now obtain the following:

- ui = yiwi;n = wi;1wi;2 : : : wi;n?1wi;n for every 1 <= i <= m? 1.

- um = uwm;n = wm;1wm;2 ? ? ? wm;n?1wm;n

- vj = zjwm;j = w1;jw2;j : : : wm?1;jwm;j for every 1 <= j <= n ? 1.

- vn = vwm;n = w1;nw2;n ? ? ? wm?1;n; wm;n

4


Finally we have to verify that wi;j I wk;l if 1 <= i < k <= m and 1 <= l 
< j <= n. For the case k < m and j < n this was already stated above.

- 1 <= i < k <= m ? 1 and 1 <= l < n: Since yk I wi;n and wk;l is a 
factor of yk it holds wi;n I wk;l.

- 1 <= i < m and 1 <= l < j < n: It holds zj I wm;l. Since wi;j is a 
factor of zj it holds wi;j I wm;l.

- 1 <= i < m and 1 <= l < n: Then wi;n is a factor of v and wm;l is a 
factor of u. Since u I v we have wi;n I wm;l.

Now we have covered all possibilities.

A trace rewriting system, briefly TRS, over the trace monoid M is a 
non{empty finite subset of M?M . In the rest of this section let R be an 
arbitrary TRS over the trace monoid M = M (?; I). If I = ;, i.e., M ' 
??, then R is also called a semi{Thue system, briefly STS, over ?? (see 
[BO93] for a detailed introduction into the theory of semi{Thue 
systems). On the other hand if I = (? ? ?)nId?, i.e., M ' Nj?j , then R 
is also called a vector replacement system, briefly VRS, over ?? (or a 
VRS in the dimension j?j). An element (l; r) 2 R is also denoted by l ! 
r. The set fl j 9r 2 M : (l; r) 2 Rg of all left{hand sides of R is 
denoted by dom(R). The set fr j 9l 2 M : (l; r) 2 Rg of all right{hand 
sides of R is denoted by ran(R). Given c = (l; r) 2 R and s; t 2 M , we 
write s !c t if s = ulv and t = urv for some u; v 2 M . We write s !R t 
if there exists a c 2 R with s !c t. The transitive (reflexive and 
transitive) closure of !R is denoted by !+R (!?R). The transitive, 
reflexive and symmetric closure of !R is denoted by $?R. It is a 
congruence relation on M . We say that R is terminating if there does 
not exist an infinite chain u1 !R u2 !R u3 !R ? ? ? in M . We say that a 
pair (u; v) 2 M ? M is confluent (with respect to R) if there exists a w 
2 M such that u !?R w and v !?R w. We say that R is confluent on the 
trace u 2 M if for all v1; v2 2 M with u !?R v1 and u !?R v2 there 
exists a w 2 M with v1 !?R w and v2 !?R w. We say that R is confluent if 
R is confluent on all u 2 M . We say that R is locally confluent if for 
all u; v1; v2 2 M with u !R v1 and u !R v2 there exists a w 2 M with v1 
!?R w and v2 !?R w. If R is terminating then by Newman's lemma [New43] R 
is confluent if and only if R is locally confluent. A trace u is 
irreducible (with respect to R) if there does not exist a v 2 M with u 
!R v. The set of all traces in M that are irreducible with respect to R 
is denoted by IRR(R). The trace v is a normalform of u if u !?R v and v 
2 IRR(R). We say that R is length{ reducing if jlj > jrj for every (l; 
r) 2 R. Obviously, if R is length reducing then R is also terminating. 
We say that R is monadic if R is length{reducing and ran(R) ? f1g [ ?. 
We say that R is special if ran(R) = f1g and 1 62 dom(R). Let COLR(M) 
(COMO(M ), COSP(M)) denote the set of all confluent TRSs over M that are 
length{reducing (monadic, special). The uniform word problem for a class 
C of TRSs over M is the following decision problem: Given a R 2 C and 
two traces u; v 2 M , does u $?R v hold?

5


Since we will investigate the complexity of algorithms that take a TRS 
as input, we have to define the length jjRjj of the TRS R. First assume 
that I 6= (???)nId?. In this case in general the best possible coding of 
a rule from R is to simply write down words over ? that represent the 
left- and right{hand side of the rule. Thus we define jjRjj = Pfjlj+ jrj 
j (l; r) 2 Rg. But if I = (???)nId?, i.e., if R is a VRS over ?? we can 
code R more e?ciently by using the binary notation. Therefore in this 
case we define jjRjj = Pfbit(l) + bit(r) j (l; r) 2 Rg. In this paper we 
always assume that a TRS R is represented as a string of length ?(jjRjj) 
(since the different rules of R must be separated by special markers, we 
use the ?{notation).

3 Semi{Thue systems

For terminating STSs confluence is known to be decidable [BO81]. This 
classical result is based on the so called critical pairs of a STS. Let 
R be a STS over ??. The set of critical pairs CP(R) is the set

CP(R) =f(sr1t; r2) j (l1; r1); (sl1t; r2) 2 Rg [

f(r1u; sr2) j (st; r1); (tu; r2) 2 R; t 6= 1g.

Note that CP(R) is finite. It is well known that R is locally confluent 
if and only if all critical pairs are confluent [NB72]. Since the last 
property can be decided effectively for the class of terminating STSs, 
confluence is decidable for this class. For length{reducing STSs, 
confluence can be even decided in polynomial time [BO81]. To the 
knowledge of the author, the best known algorithm for deciding COLR(??) 
is the O(jjRjj3) algorithm from [KKMN85]. In this section we prove that 
COLR(??) is moreover P{complete if j?j >= 2. Thus, COLR(??) seems to be 
inherently sequential. But this situation changes for the monadic case. 
At the end of this section we show that COMO(??) is contained in AC1.

In order to prove that COLR(??) is P{complete if j?j >= 2 we will first 
prove that the confluence problem is P{complete for the class of all 
STSs (without restriction on the cardinality of the underlying finite 
alphabet). Afterwards we will use the following lemma.

Lemma 3.1. Let k > 2 and ? = fa1; : : : ; akg. Let R be a 
length{reducing STS over ?. Let the injective morphism Ö : ?? ! fa; bg? 
be defined by Ö(ai) = abai+1bk?i+2 for i 2 f1; : : : ; kg and let Ö(R) = 
f(Ö(l); Ö(r)) j (l; r) 2 Rg. Then

(1) Ö(R) is length{reducing and can be calculated from R in AC0.

(2) If Ö(s) !Ö(R) u then u = Ö(t) and s !R t for some t 2 ?.

(3) Ö(s) !Ö(R) Ö(t) if and only if s !R t.

(4) R is confluent if and only if Ö(R) is confluent.

6


Proof. The first statement of the lemma is obvious (note that jÖ(ai)j = 
k+5 for all i 2 f1; : : : ; kg). The second statement follows from the 
following statement, where s and t are non{empty words:

If Ö(s) = u1Ö(t)u2 then u1 = Ö(v1) and u2 = Ö(v2) for some v1; v2 2 ??. 
(1)

Note that this statement does not hold for t = 1. Since we need (1) only 
for the case that t 2 dom(R) and since R is length{reducing, the 
restriction t 6= 1 does not matter. The if{direction from the third 
statement is obvious and the only if{direction follows from the second 
statement of the lemma and the injectivity of Ö. The if{direction of the 
fourth statement follows from the second statement of the lemma as 
follows. Let Ö(R) be confluent and let s; t; u 2 ?? such that s !R t and 
s !R u. Thus Ö(s) !Ö(R) Ö(t) and Ö(s) !Ö(R) Ö(u). Confluence of Ö(R) 
implies Ö(t) !?Ö(R) w and Ö(u) !?Ö(R) w for some w 2 fa; bg?. An

inductive generalization of the second statement of the lemma implies w 
= Ö(v) and t !?R v, u !?R v for some v 2 ??. Thus R is confluent. 
Finally, the only if{direction of the fourth statement of the lemma 
follows from (1) and the following statement:

If Ö(s) = uv, Ö(t) = vw then 9x; y; z 2 ??: u = Ö(x), v = Ö(y), w = 
Ö(z).

Together with (1), this statement implies that every overlapping of two 
left{ hand sides of Ö(R) results from an overlapping of two left{hand 
sides of R. In particular if (s; t) 2 fa; bg? is a critical pair of Ö(R) 
then s = Ö(u), t = Ö(v) for some u; v 2 ?? and (u; v) is a critical pair 
of R. Thus if R is confluent then (u; v) is confluent and thus also (s; 
t) is confluent with respect to Ö(R).

Theorem 3.2. COLR(??) is P{complete under AC0{reductions for every 
finite alphabet ? with j?j >= 2.

Before we prove Theorem 3.2 we will first investigate the uniform word 
problem for the class of confluent and length{reducing STSs. It is known 
that for a confluent and length{reducing STS the word problem is 
decidable in polynomial time [Boo82].

Theorem 3.3. The uniform word problem for the class of confluent and 
length{ reducing STS over fa; bg? is P{complete under AC0{reductions.

Proof. Our starting point for the proof of the theorem is the Generic 
Machine Simulation Problem, briefly GMSP, see e.g. [GHR95]. GMSP is the 
following decision problem.
INPUT: A deterministic Turing machine M, an input word w for M, and a 
word t 2 f#g?, where # is a new symbol which does not occur in the 
description of M.
QUESTION: Does M terminate on input w after <= jtj steps ?

It is known that GMSP is P{complete under AC0{reductions [GHR95]. In 
GMSP the Turing machine M is represented by its transition table. We 
will

7


(1a) qf x ! qf for all x 2 ?
(1b) xqf ! qf for all x 2 ?
(2a) ffq3i/ ! ffblp3(i?1)/ if ?(q; ?) = (p; b; R), 1 <= i <= m+ 1, ff 2 
?l [ f.g (2b) ffq3iar ! ffblp3(i?1) if ?(q; a) = (p; b; R), 1 <= i <= m+ 
1, ff 2 ?l [ f.g
(2c) alq3i/ ! p3(i?1)arbr/ if ?(q; ?) = (p; b; L), 1 <= i <= m+ 1
(2d) .q3i/ ! .p3(i?1)?rbr/ if ?(q; ?) = (p; b; L), 1 <= i <= m+ 1
(2e) clq3iar ! p3(i?1)crbr if ?(q; a) = (p; b; L), 1 <= i <= m+ 1
(2f) .q3iar ! .p3(i?1)?rbr if ?(q; a) = (p; b; L), 1 <= i <= m+ 1

Figure 1: The STS P(M;m), where a; b; c 2 ?, q 2 Qnfqfg, and p 2 Q.

reduce GMSP to the uniform word problem for confluent and 
length{reducing STSs over fa; bg?. Thus let (M;w;#m) be an instance of 
GMSP. Here M = (Q; ?; ?; ?; q0; qf ) is a deterministic Turing machine, 
where Q is the finite set of states, ? is the tape alphabet, ? 2 ? is 
the blank symbol, ? : Qnfqfg ? ? ! Q ? ? ? fL; Rg is the total 
transition function, q0 2 Q is the initial state, and qf 2 Q is the 
unique final state. The word w 2 (?nf?g)? is an input for M. Note that M 
terminates if and only if it reaches the final state qf . Let ?l = fal j 
a 2 ?g and ?r = far j a 2 ?g be two disjoint copies of ? with ?l \ Q = ; 
= ?r \ Q. The word wr results from w by replacing every a 2 ? by ar. Let 
. (left{end marker) and / (right{end marker) be additional symbols and 
let ? = Q [ ?l [ ?r [ f.; /g. We define the STS P(M;m) over ?? by the 
rules of Figure 1. The rules (1a) and (1b) make qf absorbing. The rules 
(2a) to (2f) simulate the machine M. Note that the state symbol is 
represented 3i times on the left{hand side and 3(i ? 1) times on the 
right{hand side. This makes P(M;m) length{reducing. It is also easy to 
see that P(M;m) can be computed from M and #m in AC0 (for this it is 
necessary that m is given in the unary representation #m since jjP(M; 
m)jj increases exponentially with bit(m)). Claim: P(M;m) is 
length{reducing and confluent. Furthermore M terminates

on input w after <= m steps if and only if .q3(m+1)
0 wr/ !?P(M;m) qf .

Confluence of P(M;m) is obvious, since only the rules (1a) and (1b) 
generate critical pairs. Since qf is absorbing, these critical pairs are 
confluent. Now assume that M does not terminate on input w after <= m 
steps. By simulating

m + 1 steps of M we obtain .q3(m+1)
0 wr/ !m+1
P(M;m) .uv/ 2 IRR(P(M;m))

for some u 2 ??l, v 2 ??r. But then .q3(m+1)
0 wr/ !?P(M;m) qf cannot hold

since also qf 2 IRR(P(M;m)) and P(M;m) is confluent. Now assume that M 
terminates on input w after <= m steps. Then for some j >= 1, u 2 ??l, 
and

v 2 ??r it holds .q3(m+1)
0 wr/ !?P(M;m) .uq3jfv/. By applying the rules (1a)

and (1b), the word .uq3jfv/ can be reduced to qf . Thus, the claim is 
proved.

Now consider the STS Ö(P(M;m)) over the alphabet fa; bg, where Ö is the 
coding function from Lemma 3.1. Then Ö(P(M;m)) is also confluent and 
length{reducing and can be calculated from P(M;m) (and hence from M and

8


#m) in AC0. Furthermore Ö(.q3(m+1)
0 wr/) $?Ö(P(M;m)) Ö(qf ) if and only if
Ö(.q3(m+1)
0 wr/) !?Ö(P(M;m)) Ö(qf ) (since Ö(P(M;m)) is confluent and Ö(qf )

irreducible with respect to Ö(P(M;m))) if and only if .q3(m+1)
0 wr/ !?P(M;m) qf
if and only if M terminates on w after <= m steps. This proves the 
theorem.

Proof of Theorem 3.2. As mentioned above, COLR(??) belongs to P. In 
order to prove the P{hardness of COLR(??) for j?j >= 2 it su?ces to 
prove the P{ hardness of COLR(fa; bg?).

Let (M;w;#m) be an instance of GMSP and let n = 3(m+1)+jwj+2. Let ? be 
the alphabet from the previous proof and let P(M;m) be the 
length{reducing and confluent STS from the previous proof. Let A and B 
be symbols which are not in ? and define the length{reducing STS 
R(M;w;m) over (?[fA;Bg)? by

R(M;w;m) = P(M;m) [ fAnB ! .q3(m+1)
0 wr/; AB ! qf g.

With the rule AnB ! .q3(m+1)
0 wr/ we generate an initial configuration for M.
Since the initial state q0 is represented 3(m+1) times in the initial 
configuration, at most m+1 steps of M will be simulated with the rules 
(2a) to (2f). Of course also R(M;w;m) can be computed from M, w, and #m 
in AC0. By the claim form the proof of Theorem 3.3 the machine M 
terminates on

input w after <= m steps if and only if .q3(m+1)
0 wr/ !?P(M;m) qf which clearly

holds if and only if .q3(m+1)
0 wr/ !?R(M;w;m) qf .

Claim : R(M;w;m) is confluent if and only if .q3(m+1)
0 wr/ !?R(M;w;m) qf .

First assume that R(M;w;m) is confluent. Since

AnB !R(M;w;m) An?1qf !n?1
(1b) qf and AnB !R(M;w;m) .q3(m+1)
0 wr/

and since qf 2 IRR(R(M;w;m)) it must hold .q3(m+1)
0 wr/ !?R(M;w;m) qf .

Now assume that .q3(m+1)
0 wr/ !?R(M;w;m) qf holds. Then the critical pair

(An?1qf ; .q3(m+1)
0 wr/) is confluent. In all other critical pairs one of the rules (1a) 
or (1b) must be involved. Since qf is absorbing these critical pairs are 
also confluent. This proves the claim.

Now consider the STS Ö(R(M;w;m)), where Ö is the coding function from 
Lemma 3.1. Then Ö(R(M;w;m)) is confluent if and only if R(M;w;m) is

confluent if and only if .q3(m+1)
0 wr/ !?R(M;w;m) qf if and only if M terminates
on input w after <= m steps.

In the rest of this section we will show that Theorem 3.2 does not hold 
any longer for monadic STSs unless NC = P. More precisely, we prove that 
COMO(??) is contained in AC1. To the knowledge of the author this result 
was never stated explicitly, but it easily follows from known results. 
We start with the uniform word problem for 1{free CFGs which is the 
following problem: INPUT: A 1{free CFG G over a terminal alphabet ? and 
a word s 2 ??. QUESTION: Is s 2 L(G) ?

9


The following result was implicitly proven in [Ruz80], see also [GHR95], 
pp. 176.

Lemma 3.4. The uniform word problem for 1{free CFGs is in AC1.

In [BJW82] it was shown that the question whether a pair (s; t) of words 
is confluent with respect to a monadic STS can be reduced to the word 
problem for CFGs. We present the construction from [BJW82] for 
completeness and in order to convince the reader that it can be carried 
out in AC0. Let R be a monadic STS over ??. With R we associate a 1{free 
CFG GR in the following way. Let ?l = fal j a 2 ?g and ?r = far j a 2 ?g 
be two disjoint copys of ? and let # be an additional symbol. For a word 
s 2 ??, sl and sr are defined in the obvious way. Then GR = (?l [ ?r [ 
fS; Sl; Srg; ? [ f#g; P; S), where P contains all productions of the 
form

S ) alSar j SSr j SlS j # for a 2 ?, al ) a, ar ) a for a 2 ? Sl ) sl, 
Sr ) srev
r for (s; 1) 2 R, al ) sl, ar ) srev
r for a 2 ?, (s; a) 2 R,
x ) Slx j xSl for x 2 ?l [ fSlg, x ) Srx j xSr for x 2 ?r [ fSrg.

Obviously, GR can be constructed from R by an AC0{circuit. Furthermore 
L(GR;Sl) = fs 2 ?+ j s !?R 1g, L(GR; al) = fs 2 ?? j s !?R ag and 
L(GR;Sr) = fs 2 ?+ j srev !?R 1g, L(GR; ar) = fs 2 ?? j srev !?R ag. 
Thus

L(GR) = fs#trev j s !?R u and t !?R u for some u 2 ??g.

Now the following theorem is easy to prove.

Theorem 3.5. COMO(??) is in AC1.

Proof. Let R be a monadic STS over ??. First we construct an AC0{circuit 
that calculates from R the set of all critical pairs. This is possible, 
since in parallel we can test for each pair of rules l1 ! r1 and l2 ! r2 
and for each factorization l1 = st with t 6= 1 whether l2 is a prefix of 
t or t is a prefix of l2 (using unbounded fan{in this is clearly 
possible in constant depth). If this is the case, we obtain a critical 
pair. In a second step we have to test in parallel whether each critical 
pair (s; t) 2 CP(R) is confluent. For this we construct in AC0 from R 
the 1{free CFG GR and test whether s#trev 2 L(GR) which can be done in 
AC1 by Lemma 3.4.

4 Vector replacement systems

In [VRL98] it was shown that confluence is decidable but EXSPACE{hard 
for the class of all vector replacement systems. Based on critical 
pairs, more feasible upper bounds can be obtained for the 
length{reducing case. Similarly to STSs, also VRSs yield finite sets of 
critical pairs [BL81]. Let R be a VRS over ??. The set CP(R) of critical 
pairs of R contains exactly all pairs (s; t) 2 ?? ??? such that there 
exist rules (k; p); (l; r) 2 R such that for all a 2 ? it holds jsja = 
max(jkja; jlja) ? jkja + jpja and jtja = max(jkja; jlja) ? jlja + jrja. 
Then R

10


is locally confluent if and only if all critical pairs are confluent. 
Note that there are at most jRj ? (jRj ? 1) many critical pairs that are 
not trivially confluent. For the length{reducing case, testing all 
critical pairs for confluence leads to a straight{forward 
PSPACE{algorithm for deciding confluence. In this section we will prove 
that confluence is moreover PSPACE{complete for the class of all VRSs 
(without restriction on the dimension), i.e., S
k>0 COLR(Nk ) is PSPACE{
complete. Note that the calculation of a normalform of a s 2 ?? with 
respect to a length{reducing VRS may involve a number of steps that is 
exponential in bit(s). Therefore the calculation of normalforms for the 
finitely many critical pairs does not lead to a polynomial time 
algorithm (as it is the case for STSs).

Theorem 4.1.
[

k>0
COLR(Nk ) is PSPACE{complete.

Proof. The following problem is known to be PSPACE{complete [Kar72]: 
INPUT: A deterministic linear bounded automaton M and an input w for M. 
QUESTION: Does M accept w ?
Let us fix a deterministic linear bounded automaton M = (Q; ?; .; /; ?; 
q0; qf ) and an input w 2 (?nf.; /g)? for M, where Q is the finite set 
of states, ? is the tape alphabet, . 2 ? is the left{end marker, / 2 ? 
is the right{end marker, ? : (Qnfqfg) ? ? ! Q ? ? ? fL; Rg is the 
transition function, q0 2 Q is the initial state, and qf is the unique 
final state. The transition function must be defined such that

- the read{write head never moves to the left (right) of . (/) and

- does not overwrite . (/) by a symbol different from . (/) and

- does not overwrite a tape symbol a 2 ?nf.; /g by . or /.

We identify each tape cell of M with a number from f0; : : : ; jwj + 1g, 
where cell 0 always contains the left{end marker . and cell jwj + 1 
always contains the right{end marker /. We assume that M starts with the 
read{write head scanning cell 0. Note that M accepts w if and only if it 
terminates on w if and only if it reaches the final state qf . 
Furthermore we may assume that the read{write head is always in cell 0 
if the final state qf is reached.

We will construct a VRS R(M;w) such that R(M;w) is confluent if and only 
if M accepts the input w, which proves the theorem. Our construction is 
based on the simulation of a linear bounded automaton by a Petri net 
from [JLL77]. Let us define the alphabet ? by

? = (f0; : : : ; jwj + 1g ?Q) [ (f0; : : : ; jwj + 1g ? ?) [ fA; $g.

Note that we consider pairs (i; q) 2 f0; : : : ; jwj + 1g ? Q and pairs 
(i; a) 2 f0; : : : ; jwj + 1g ? ? as single symbols. The symbol (i; q) 
means that M is in the state q and the read{write head is scanning cell 
i, whereas the symbol (i; a) means that cell i contains the tape symbol 
a. Since cell 0 always contains . and cell jwj + 1 always contains /, 
the symbols (0; .) and (jwj + 1; /) will be always

11


(1a) $(i; q)(i; a) ! (i + 1; p)(i; b) if ?(q; a) = (p; b; R), q 6= qf , 
i <= jwj (1b) $(i; q)(i; a) ! (i ? 1; p)(i; b) if ?(q; a) = (p; b; L), q 
6= qf , i >= 1 (2) (0; qf )x ! (0; qf ) if x 2 ?
(3a) (i; a)(i; b) ! (0; qf )
(3b) (i; p)(j; q) ! (0; qf )
(4a) An ! $m(0; q0)(0; .)(1; a1) ? ? ? (jwj; ajwj)(jwj + 1; /)
(4b) A2 ! (0; qf )

Figure 2: The VRS R(M;w), where p; q 2 Q, 0 <= i; j <= jwj + 1, and a; b 
2 ?.

present. Moreover since we assumed that M terminates if and only if it 
reaches the final state qf and the read{write head is in cell 0, the 
presence of the symbol (0; qf ) indicates that M has terminated. The VRS 
R(M;w) over ?? is shown in Figure 2, where we assume that w = a1a2 ? ? ? 
ajwj and m = jQj ? j?jjwj ? (jwj+2) and n = m+ jwj + 4 (we did not fix a 
linear ordering on ?, which is necessary for ??, but this can be done in 
an arbitrary way).

The rules (1a) and (1b) simulate M where the additional $ on the 
left{hand side is necessary in order to make these rules 
length{reducing. Rule (2) makes (0; qf ) absorbing. With the rules (3a) 
and (3b) it is possible to resolve critical pairs that result from the 
rules (1a) and (1b). In particular it is easy to see that the VRS that 
consists of the rules (1a), (1b), (2), (3a) and (3b) is confluent. With 
the rules (4a) and (4b) we intentionally create a critical pair. The 
first rule (4a) produces the encoding of the initial configuration of M. 
Since each simulation step of R(M;w) consumes a $, we have to make 
enough $'s available for the initial configuration. Since there are at 
most m = jQj ? j?jjwj ? (jwj + 2) different configurations for M, the 
automaton M either terminates after <= m steps or loops forever. Thus m 
many $'s su?ce. Note that in the binary representation of R(M;w) the m 
many $'s are represented by O(ld(m)) = O(ld(jQj) + jwj ? ld(j?j) + 
ld(jwj + 2)) many bits, which is polynomial in jwj and the length of the 
description of M. The same holds also for the number n = m+ jwj + 4 in 
the left{hand side of rule (4a) which is chosen such that (4a) is 
length{reducing. Finally rule (4b) writes the absorbing symbol (0; qf ). 
The proof that R(M;w) is confluent if and only if M accepts w is similar 
to the proof of Theorem 3.2. First note that An !(4b) An?2(0; qf ) !n?2 
(2) (0; qf ) 2

IRR(R(M;w) and An !(4a) $m(0; q0)(0; .)(1; a1) ? ? ? (jwj; ajwj)(jwj+1; 
/). If M does not accept w, i.e., if M does not terminate on input w, 
then by simulating m steps of M we obtain

$m(0; q0)(0; .)(1; a1) ? ? ? (jwj; ajwj)(jwj + 1; /) !mR(M;w)

(i; q)(0; .)(1; b1) ? ? ? (jwj; bjwj)(jwj + 1; /) 2 IRR(R(M;w))

for some i 2 f0; : : : ; jwj + 1g, q 2 Qnfqfg, and bj 2 ?nf.; /g (1 <= j 
<= jwj). Thus R(M;w) is not confluent. On the other hand if M accepts w, 
then M

12


reaches after k <= m steps the final state qf and terminates in cell 0. 
Hence

$m(0; q0)(0; .)(1; a1) ? ? ? (jwj; ajwj)(jwj + 1; /) !kR(M;w)

$m?k(0; qf )(0; .)(1; b1) ? ? ? (jwj; bjwj)(jwj + 1; /) !+(2) (0; qf ).

Since all other critical pairs of R(M;w) are confluent, R(M;w) is 
confluent.

One might ask whether confluence is also PSPACE{complete for VRSs in a 
su?- ciently large but fixed dimension. The usual technique of coding 
several symbols into two symbols that we applied for STSs does not work 
for VRSs. On the other hand there exists a simulation of a 3{counter 
machine with exponentially bounded counters (for which the acceptance 
problem is PSPACE{complete) by a VRS in the dimension 6 [Huy85]. But in 
this simulation unwanted critical pairs arise and it does not seem to be 
obvious whether these critical pairs can be resolved by adding a 
polynomial number of additional rules (like the rules (3a) and (3b) in 
the previous proof).
The following theorem follows easily from the previous proof by using 
the same arguments that we applied for the proof of Theorem 3.3.

Theorem 4.2. The uniform word problem for length{reducing and confluent 
VRSs is PSPACE{complete.

Similarly to the semi{Thue case, also for VRSs the complexity of the 
confluence problem decreases for the monadic case. This is the content 
of the next theorem.

Theorem 4.3.
[

k>0
COMO(Nk ) is in NP.

Proof. The theorem follows easily from the results of [Huy83, Esp97], 
which state that the reachability problem for communication{free Petri 
nets is in NP (in fact it is NP{complete). In terms of VRSs, a VRS R is 
communication{free, if for each left{hand side l 2 dom(R) it holds jlj = 
1. Using this result, we can decide S
k>0 COMO(Nk ) in NP as follows. Given a monadic VRS R over ?? we first 
construct the set of all critical pairs, as defined at the beginning of 
this section. Let (s; t) 2 ?? ? ?? be one of these critical pairs. We 
now guess a u 2 ?? with juj <= jsj and juj <= jtj. It su?ces to check in 
NP whether s !?R u and t !?R u. In order to verify whether s !?R u we 
proceed as follows. Let P be the following communication{free VRS over 
(? [ f$g)?, where $ 62 ? is a new symbol:

P = f(r; l) j (l; r) 2 R; jrj = 1g [ f($; l) j (l; 1) 2 Rg

Then s !?R u if and only if u$i !?P s for some 0 <= i <= jsj ? juj. Thus 
we simply have to guess such a number i (note that bit(i) is bounded by 
a polynomial in bit(s)) and check whether u$i !?P s, which is possible 
in NP by the results mentioned above. This concludes the proof.

13


Whether S
k>0 COMO(Nk ) is also NP{complete is left as an open question. If we 
further restrict the input to be a special VRS, then we can even give a 
simple deterministic polynomial time algorithm that decides confluence.

Theorem 4.4.
[

k>0
COSP(Nk ) is in P.

Proof. Let R be a special VRS over ??, where ? = fa1; : : : ; ang. In 
order to check whether R is confluent it su?ces to calculate for each 
critical pair (s; t) 2 ????? normalforms of s and t and to check whether 
these normalforms are equal. Thus we have to prove that a normalform of 
a s 2 ?? can be calculated in P. Let l1; : : : ; lm be the left{hand 
sides of R. Let s0 = s and for 1 <= i <= m let si be a normalform of 
si?1 with respect to the special one{rule VRS fli ! 1g. Then it is easy 
to see that sm is a normalform of s. Thus we have to show that the 
normalform of ad11 ? ? ? adn
n 2 ?? with respect to a rule
ae11 ? ? ? aen
n ! 1 can be calculated in P. But this is easy. For each 1 <= i <= n we 
have to calculate the integer{quotient qi = bdi=eic and take the minimum 
q = minfq1; : : : ; qng of these quotients. For 1 <= i <= n let fi = di 
? q ? ei. Then the normalform is af11 ? ? ? afn
n .

Also the problem whether S
k>0 COSP(Nk ) is P{complete must be left as an
open question.

5 Special trace rewriting systems

In contrast to the decidability results of the last two sections, there 
exists a trace monoid M such that COLR(M) is undecidable [NO88]. This 
result was sharpened in [Loh98], where it was shown that COLR(M) is 
decidable if and only if M is a free monoid or a free commutative 
monoid. In particular this implies that in general TRSs cannot have 
finitely many critical pairs (in contrast to STSs and VRSs). Furthermore 
these undecidability results lead to the question whether there exist 
restricted but non trivial classes of (length{reducing) TRSs for which 
confluence is decidable. In particular, in [Die90b] it was asked whether 
confluence is decidable for special TRSs and monadic TRSs, respectively. 
For the special case we answer this question positively in this section. 
In fact we will prove that confluence is decidable for a broader class 
of TRSs that satisfy the following condition, which we call condition 
(A): A TRS R over M (?; I) satisfies condition (A) if

(1) for all (l1; r1); (l2; r2) 2 R and all factorizations l1 = p1q1, l2 
= p2q2 with pi 6= 1 6= qi for i 2 f1; 2g, p1 I p2, and q1 I q2 it holds: 
There exist factorizations r1 = s1t1, r2 = s2t2 such that a I pi implies 
a I si and a I qi implies a I ti for all a 2 ?, i 2 f1; 2g.

(2) for all (l1; r1); (l2; r2) 2 R and all factorizations l1 = p1sq1, l2 
= p2sq2 with s 6= 1, p1 I p2, and q1 I q2 it holds: a I s implies ar1 = 
r1a and ar2 = r2a for all a 2 ?.

14


Input: A length{reducing TRS R over M (?; I) that satisfies condition 
(A) begin
forall ((l1; r1); (l2; r2))) 2 R?R do
forall factorizations l1 = p1sq1, l2 = p2sq2 with
s 6= 1, p1 I p1, q1 I q2 do
nf1 := NF(p1r2q1; R); nf2 := NF(p2r1q2; R);
if nf1 6= nf2 then
(?) return \R not confluent"
else
u := nf1(= nf2);
forall a 2 ? with a I p2sq1 or a I p1sq2 do
nf1 := NF(au; R); nf2 := NF(ua; R);
if nf1 6= nf2 then
(??) return \R not confluent"
endfor
endfor
endfor
(???) return \R confluent"
end

Figure 3: The algorithm CONFL

Note that condition (A2) implies that for every rule (l; r) 2 R if a I l 
then ar = ra.

Theorem 5.1. The following problem is decidable for every trace monoid M 
: INPUT: A length-reducing TRS R over M that satisfies condition (A). 
QUESTION: Is R confluent?

Proof. Let M = M (?; I) be a trace monoid and let R be a length{reducing 
TRS over M that satisfies condition (A). Let NF be an algorithm that 
computes an arbitrary normalform NF(u; R) of a given input trace u with 
respect to R. Consider the algorithm CONFL in Figure 3. We claim that 
CONFL outputs \R confluent" if and only if R is confluent. First we 
prove that R is not confluent if CONFL outputs \R not confluent". If 
CONFL executes line (?) then there exist rules l1 ! r1 and l2 ! r2 in R 
and factorizations l1 = p1sq1, l2 = p2sq2 such that s 6= 1, p1 I p2, and 
q1 I q2. Furthermore there exists a normalform u1 of p1r2q1 and a 
normalform u2 of p2r1q2 such that u1 6= u2. But then R is indeed not 
confluent since p2p1sq1q2 !R p2r1q2 !?R u2 and p2p1sq1q2 = p1p2sq2q1 !R 
p1r2q1 !?R u1. Now assume that CONFL executes line (??). Then it holds 
u1 = u2 = u but there exists an a 2 ? such that either a I p2sq1 or a I 
p1sq2 and there exist a normalform v1 of au and a normalform v2 of ua 
such that v1 6= v2. Assume that a I p2sq1. Since R satisfies condition

15


(A2) it follows ar1 = r1a and ar2 = r2a. Hence

p2p1sq1aq2 !R p2r1aq2 = ap2r1q2 !?R au !?R v1 and

p2p1sq1aq2 = p1p2sq1aq2 = p1ap2sq2q1 !R p1ar2q1 = p1r2q1a !?R ua !?R v2.

Thus, again R is not confluent. The case that a I p1sq2 can be dealt 
similarly by considering the trace p2ap1sq1q2 instead of p2p1sq1aq2.

Now assume that CONFL outputs \R confluent" in line (???). We have to 
show that R is confluent. By induction on the length of traces it su?ces 
to prove the following implication:

If R is confluent on all traces t0 with jt0j < jtj then R is confluent 
on t.

Thus, let t 2 M and assume that R is confluent on all traces t0 with 
jt0j < jtj. We have to prove that all pairs (t1; t2) such that t !iR t1 
and t !jR t2 for some i; j >= 0 are confluent. Of course the case i = 0 
or j = 0 is trivial. Let us assume for a moment that we have already 
considered all cases with i = 1 = j. Then we can apply the same 
arguments as in the (standard) proof of Newman's lemma: t !R s1 !?R t1 
and t !R s2 !?R t2 imply that there exists a trace s with si !?R s (i 2 
f1; 2g). Since js1j < jtj and s1 !?R t1, s1 !?R s it holds t1 !?R u and 
s !?R u for some trace u. Since also js2j < jtj and s2 !?R t2, s2 !?R s 
!?R u it holds t2 !?R v and u !?R v, i.e., t1 !?R u !?R v for some trace 
v.

Thus, it su?ces to consider arbitrary factorizations t = u1l1v1 = u2l2v2 
where (l1; r1); (l2; r2) 2 R. We have to prove that the pair (u1r1v1; 
u2r2v2) is confluent. Lemma 2.1 applied to the identity u1l1v1 = u2l2v2 
gives nine traces yi; pi; qi (i 2 f1; 2g) and s such that (see also the 
diagram below)

- l1 = p1sq1, l2 = p2sq2,

- u1 = y1p2w2, u2 = y1p1w1,

- v1 = w1q2y2, v2 = w2q1y2,

- t = y1p1w1p2sq2w2q1y2 = y1p2w2p1sq1w1q2y2,

- p1 I p2, q1 I q2, w1 I p2sw2q1, w2 I p1w1sq2.

v2 w2 q1 y2
l2 p2 s q2
u2 y1 p1 w1

u1 l1 v1

We have to show that the pair (y1p1w1r2w2q1y2; y1p2w2r1w1q2y2) is 
confluent. First assume that either y1 6= 1 or y2 6= 1. For the trace t0 
= p1w1p2sq2w2q1 = p2w2p1sq1w1q2 it holds jt0j < jtj and

t0 = p1w1l2w2q1 !R p1w1r2w2q1, t0 = p2w2l1w1q2 !R p2w2r1w1q2.

Thus the pair (p1w1r2w2q1; p2w2r1w1q2) is confluent. But then the same 
also holds for the pair (y1p1w1r2w2q1y2; y1p2w2r1w1q2y2). Thus we may 
assume that y1 = y2 = 1 and we have to consider the pair (p1w1r2w2q1; 
p2w2r1w1q2).

Next assume that s = 1, i.e., l1 = p1q1 and l2 = p2q2. First assume that 
also p1 = 1, i.e., l1 = q1. We have to show that the pair (w1r2w2q1; 
p2w2r1w1q2) is

16


confluent. Since w1r2w2q1 = w1r2w2l1 !R w1r2w2r1 it su?ces to prove that 
also p2w2r1w1q2 !R w1r2w2r1. This can be deduced as follows: Since q1 I 
w1q2, i.e., l1 I w1q2, condition (A2) (more precisely the remark after 
condition (A2)) for R implies w1r1 = r1w1 and q2r1 = r1q2. Thus

p2w2r1w1q2 = p2w2w1q2r1 (since r1w1q2 = w1q2r1)

= w1p2q2w2r1 (since w1 I w2, w1 I p2, and w2 I q2)

!R w1r2w2r1

Thus, we may assume that p1 6= 1. Similarly we may assume that also q1 
6= 1, p2 6= 1, and q2 6= 1. But then condition (A1) implies that there 
exist factorizations r1 = s1t1, r2 = s2t2 such that a I pi implies a I 
si and a I qi implies a I ti for all a 2 ?. In particular it holds

p2 I s1, w2 I s1, p1 I s2, w1 I s2, q2 I t1, w1 I t1, q1 I t2, w2 I t2.

Furthermore p2 I s1 implies s2 I s1 and q2 I t1 implies t2 I t1. Thus, 
we obtain

p2w2r1w1q2 = p2w2s1t1w1q2 = s1w1p2q2w2t1 !R s1w1s2t2w2t1 = s2w2s1t1w1t2,

p1w1r2w2q1 = p1w1s2t2w2q1 = s2w2p1q1w1t2 !R s2w2s1t1w1t2.

In the rest of the proof we assume that s 6= 1. But then we have one of 
the situations that are considered in the two outermost forall{loops of 
CONFL. Since we assume that CONFL outputs \R confluent" we know that 
there exists a trace u such that p1r2q1 !?R u and p2r1q2 !?R u. 
Furthermore since R satisfies condition (A2) and s I w1w2 it holds riwj 
= wjri for i; j 2 f1; 2g. Hence p1w1r2w2q1 = w2p1r2q1w1 !?R w2uw1 and 
p2w2r1w1q2 = w1p2r1q2w2 !?R w1uw2 and it su?ces to prove that the pair 
(w2uw1; w1uw2) is confluent. The case w1 = 1 = w2 is trivial. Thus 
assume w.l.o.g. w1 = wa, where a 2 ?. Since w1 I p2sw2q1 it follows a I 
p2sq1. Thus a 2 ? is one of the symbols that are considered in the 
innermost forall{loop of CONFL. It follows that there exists a trace v 
such that au !?R v and ua !?R v. Thus

wuaw2 !?R wvw2 and w1uw2 = wauw2 !?R wvw2. (2)

Next let us consider the trace t0 = p1wp2sq2w2q1 = p1wl2w2q1 (t0 results 
from t by replacing the factor w1 = wa by w). It holds jt0j < jtj and 
since w satisfies the same independencies as w1 it holds t0 = 
p2w2p1sq1wq2 = p2w2l1wq2. Thus we obtain (note that wr1 = r1w and wr2 = 
r2w)

t0 !R p1wr2w2q1 = w2p1r2q1w !?R w2uw and

t0 !R p2w2r1wq2 = wp2r1q2w2 !?R wuw2.

Hence there exists a trace x such that w2uw !?R x and wuw2 !?R x. It 
follows

w2uw1 = w2uwa !?R xa and wuaw2 = wuw2a !?R xa. (3)

17


Finally since wuaw2 !?R wvw2 by (2) and wuaw2 !?R xa by (3) and jwuaw2j 
= jw1uw2j <= jw1p1r2q1w2j < jp1w1p2sq2w2q1j = jtj (where the strict 
inequality follows from jr2j < jp2sq2j) there exists a trace z such that 
wvw2 !?R z and xa !?R z. Now we obtain w1uw2 !?R wvw2 !?R z from (2) and 
w2uw1 !?R xa !?R z from (3). Thus the pair (w1uw2; w2uw1) is confluent 
and the correctness of CONFL is proved.

Theorem 5.2. COSP(M) is in P for every trace monoid M .

Proof. For special VRSs we already proved the statement of the theorem. 
On the other hand if I 6= (? ? ?)nId? then CONFL runs in polynomial 
time. This follows from the following two facts: (i) For a fixed 
independence alphabet (?; I), the number of different factorizations l = 
psq of a trace l is bounded by a polynomial in the length of jlj. This 
follows from the fact that the number of prefixes of a trace t is 
bounded by a polynomial in jtj [BMS89]. (ii) A normalform of a trace t 
with respect to a length{reducing TRS R, which is not a VRS, can be 
calculated in time bounded by a polynomial in jtj and jjRjj, see 
[Die90c, Die90a, BD95, Ber95, BD96] for the normalform problem 1.

One might further ask, whether confluence can be decided for arbitrary 
monadic TRSs. We leave this as an open question.

We close this section with a simple problem that is decidable for 
monadic STSs but in general undecidable for special TRSs. A trace u 2 M 
(?; I) is said to be connected if there does not exist a factorization u 
= vw such that v 6= 1 6= w and v I w. A set L ? M (?; I) is connected if 
every trace in L is connected. A set L ? M (?; I) is recognizable if the 
set fs 2 ?? j 9u 2 L : u = [s]I g of all words that represent a trace in 
L is recognizable. This is just one of several different possibilities 
of defining recognizable trace languages, see e.g. chapter 6 of [DR95]. 
A fundamental result of Ochma?nski [Och85], states that the class of all 
recognizable trace languages in M (?; I) is the smallest class C that 
contains all singleton subsets of M (?; I) and that is closed under (i) 
union, (ii) concatenation of two languages (where the concatenation of 
L1 and L2 is L1L2 = fu1u2 j u1 2 L1; u2 2 L2g) and (iii) the 
star{operator restricted to connected languages, i.e., if L 2 C is 
connected then also L? = fu1u2 ? ? ? un j n >= 0; u1; u2; : : : ; un 2 
Lg 2 C. Given a TRS R over M and a set L ? M we denote by ??R(L) = fv 2 
M j 9u 2 L : u !?R vg the set of all descendants of L with respect to R. 
It is known that if L ? ?? is a recognizable word language and R is a 
monadic STS then also ??R(L) is recognizable [BO85]. But already for 
special TRSs that contain only one rule this fact does not hold in 
general, as the following example shows.

Example 5.3. Let ? = fa; b; cg and I = f(a; c); (c; a)g. Since the trace 
u = [abc]I is connected, the language fug? is recognizable. Let R be the 
special TRS fb ! 1g. Assume that ??R(fug?) is recognizable. Since 
recognizable trace languages are closed under intersection, also the 
language ??R(fug?)\fa; cg? =

1The algorithms in [Die90c, Die90a, BD95, Ber95, BD96] are all non 
uniform, i.e., the TRSs is fixed. But it is easy to see that they run 
also in the uniform case in polynomial time.

18


f[ancn]I j n >= 0g would be recognizable. But this is not the case, see 
e.g. [DR95], pp 172.

For a class C of TRSs over a trace monoid M we define the extended word 
problem for C and M as follows [BO85]:
INPUT: A TRS R 2 C and two recognizable languages L1 and L2 of M . 
QUESTION: Do there exist u1 2 L1 and u2 2 L2 such that u1 $?R u2?

A simple consequence of the above mentioned closure of recognizable word 
languages under the operator ??R for a monadic STS R is that the 
extended word problem for monadic and confluent STSs is decidable 
[BO85]. In contrast to this, the following theorem holds.

Theorem 5.4. There exists a trace monoid M = M (?; I), a special TRS R 
over M of the form R = fa ! 1g, where a 2 ?, and a recognizable language 
L1 ? M such that the following problem is undecidable.
INPUT: A recognizable language L2 ? M .
QUESTION: Do there exist u1 2 L1 and u2 2 L2 such that u1 $?R u2?

Proof. It is well{known that the Post Correspondence Problem, briefly 
PCP, is undecidable over a two{element alphabet. Furthermore it can be 
required that every solution of the PCP has to start with a 
distinguished pair. Thus the following problem is undecidable, which is 
called the modified PCP over fa; bg: INPUT: A set f(s1; t1); : : : ; 
(sn; tn)g of pairs with si; ti 2 fa; bg? for 1 <= i <= n. QUESTION: Does 
there exist a i1i2 ? ? ? ik 2 f1; : : : ; ng? with s1si1si2 ? ? ? sik = 
t1ti1 ti2 ? ? ? tik ?

Let P = f(s1; t1); : : : ; (sn; tn)g be an instance of the modified PCP 
over fa; bg. Let fa; bg be a copy of fa; bg and let # be an additional 
symbol. Let ? = fa; b; a; b; #g and define an independence relation I on 
? by the following graph:

b

a

a

b #

Thus the symbols in fa; bg and fa; bg pairwise commute whereas # is 
dependent from all symbols. For a word s 2 fa; bg? the word s is defined 
in the obvious way. Let L1 = f[a#a]I ; [b#b]Ig? and L2 = 
f[s1#t1]Igf[si#ti]I j 1 <= i <= ng?. By Ochma?nski's theorem both L1 and 
L2 are recognizable subsets of M (?; I). Let R = f# ! 1g. Thus R is 
special and confluent. Now the PCP P has a solution if and only if

9u1 2 L1; u2 2 L2; v 2 IRR(R) : u1 !?R v; u2 !?R v if and only if

9u1 2 L1; u2 2 L2; v 2 M (?; I) : u1 !?R v; u2 !?R v if and only if

9u1 2 L1; u2 2 L2 : u1 $?R u2

where the last equivalence holds since R is confluent.

19


It might be an interesting problem to characterize those trace monoids 
for which the extended word problem for confluent and monadic (or 
special) TRSs is decidable.

6 Conclusion

In this paper we have investigated the complexity of the confluence 
problem for restricted kinds of semi{Thue systems, vector replacement 
systems and general trace rewriting systems. We would like to close this 
paper with a list several questions that remain unsolved.

- What is the complexity of the confluence problem for length{reducing 
vector replacement system if the dimension is fixed? Note that in 
Theorem 4.1, the dimension is not fixed.

- Are the upper bounds given in Theorem 4.3, Theorem 4.4 and Theorem 5.2 
sharp, i.e., are the decision problems, considered in these theorems, 
also hard for the given complexity classes?

- Is confluence decidable for general monadic trace rewriting systems. 
This question was already asked in [Die90b]?

References

[BD95] M. Bertol and V. Diekert. On e?cient reduction-algorithms for 
some trace rewriting systems. In H. Common and J.-P. Jouannaud, editors, 
Term Rewriting., number 909 in Lecture Notes in Computer Science, pages 
114{126, Berlin-Heidelberg-New York, 1995. Springer.

[BD96] M. Bertol and V. Diekert. Trace rewriting: Computing normal forms 
in time O(n log n). In C. Puech and R. Reischuk, editors, Proceedings of 
the13th Annual Symposium on Theoretical Aspects of Computer Science 
1996, number 1046 in Lecture Notes in Computer Science, pages 269{280, 
Berlin-Heidelberg-New York, 1996. Springer.

[Ber95] M. Bertol. E?cient rewriting in cograph trace monoids. In H. 
Reichel, editor, Proceedings of the10th Fundamentals of Computation 
Theory (FCT '95), Dresden (Germany) 1995, number 965 in Lecture Notes in 
Computer Science, pages 146{155, Berlin-Heidelberg- New York, 1995. 
Springer.

[BJW82] R.V. Book, M. Jantzen, and C. Wrathall. Monadic thue systems. 
Theoretical Computer Science, 19:231{251, 1982.

20


[BL81] A. M. Ballantyne and D. S. Lankford. New decision algorithms for 
finitely presented commutative semigroups. Comput. and Maths. with 
Appls., 7:159{165, 1981.

[BMS89] A. Bertoni, G. Mauri, and N. Sabadini. Membership problems for 
regular and context free trace languages. Information and Computation, 
82:135{150, 1989.

[BO81] R.V. Book and C.P. O'Dunlaing. Testing for the church-rosser 
property (note). Theoretical Computer Science, 16:223{229, 1981.

[BO85] R.V. Book and F. Otto. Cancellation rules and extended word 
problems. Information Processing Letters, 20:5{11, 1985.

[BO93] R.V. Book and F. Otto. String{Rewriting Systems. Springer{Verlag, 
1993.

[Boo82] R.V. Book. Confluent and other types of Thue systems. Journal of 
the ACM, 29(1):171{182, January 1982.

[BS90] R.P. Boppana and M. Sipser. The complexity of finite functions. 
In Jan van Leeuwen, editor, Handbook of Theoretical Computer Science 
(Volume A: Algorithms and Complexity). Elsevier and MIT Press, 1990.

[CP85] R. Cori and D. Perrin. Automates et commutations partielles. 
R.A.I.R.O. | Informatique Th?eorique et Applications, 19:21{32, 1985.

[Die90a] V. Diekert. Combinatorial rewriting on traces. In C. Choffrut 
et al., editors, Proceedings of the7th Annual Symposium on Theoretical 
Aspects of Computer Science (STACS'90), Rouen (France) 1990, number 415 
in Lecture Notes in Computer Science, pages 138{151, 
Berlin-Heidelberg-New York, 1990. Springer.

[Die90b] V. Diekert. Combinatorics on Traces. Number 454 in Lecture 
Notes in Computer Science. Springer, Berlin-Heidelberg-New York, 1990.

[Die90c] V. Diekert. Word problems over traces which are solvable in 
linear time. Theoretical Computer Science, 74:3{18, 1990.

[DR95] V. Diekert and G. Rozenberg, editors. The Book of Traces. World 
Scientific, Singapore, 1995.

[Esp97] J. Esparza. Petri nets, commutative context{free grammars, and 
basic parallel processes. Fundamenta Informatica, 30:23{41, 1997.

[GHR95] R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. Limits to Parallel 
Computation: P -Completeness Theory. Oxford University Press, 1995.

21


[Huy83] D. T. Huynh. Commutative grammars: The complexity of uniform 
word problems. Information and Control, 57:21{39, 1983.

[Huy85] D. T. Huynh. Complexity of the word problem for commutative 
semigroups of fixed dimension. Acta Informatica, 22:421{432, 1985.

[JLL77] N. D. Jones, L. H. Landweber, and Y. E. Lien. Complexity of some 
problems in petri nets. Theoretical Computer Science, 4:277{299, 1977.

[Kar72] R. M. Karp. Reducibility among combinatorial problems. In R. E. 
Miller and J. W. Thatcher, editors, Complexity of Computer Computations, 
pages 85{103. Plenum Press, New York, 1972.

[KKMN85] D. Kapur, M. S. Krishnamoorthy, R. McNaughton, and P. 
Narendran. An O(jT j3) algorithm for testing the Church-Rosser property 
of Thue systems. Theoretical Computer Science, 35(1):109{114, January 
1985.

[Loh98] M. Lohrey. On the confluence of trace rewriting systems. In V. 
Arvind and R. Ramanujam, editors, Foundations of Software Technology and 
Theoretical Computer Science, volume 1530 of Lect. Notes Comput. Sci., 
pages 319{330, 1998.

[Maz77] A. Mazurkiewicz. Concurrent program schemes and their 
interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977.

[NB72] M. Nivat and M. Benois. Congruences parfaites et quasi{parfaites. 
Seminaire Dubreil, 25(7{01{09), 1971{1972.

[New43] M. H. A. Newman. On theories with a combinatorial definition of 
\equivalence". Annals Mathematics, 43:223{243, 1943.

[NO88] P. Narendran and F. Otto. Preperfectness is undecidable for Thue 
systems containing only length-reducing rules and a single commutation 
rule. Information Processing Letters, 29:125{130, 1988.

[Och85] E. Ochma?nski. Regular behaviour of concurrent systems. Bulletin 
of the European Association for Theoretical Computer Science (EATCS), 
27:56{67, October 1985.

[Pap94] C.H. Papadimitriou. Computational Complexity. Addison Wesley, 
1994.

[Ruz80] W. L. Ruzzo. Tree{size bounded alternation. Journal of Computer 
and System Sciences, 21:218{235, 1980.

[VRL98] R. M. Verma, M. Rusinowitch, and D. Lugiez. Algorithms and 
reductions for rewriting problems. In Proceedings 9th Conference on 
Rewriting Techniques and Applications, Tsukuba (Japan), volume 1379 of 
Lecture Notes in Computer Science, pages 166{180. Springer-Verlag, 1998.

22