Table of Contents

Partial Commutation and Traces
1. Introduction : : : : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : : : : : : : 3
2. Free Partially Commutative Monoids : : : : : : : : : : : : : : : : : 
: : : : : : : : : : 4
2.1 First Definitions and Basic Properties : : : : : : : : : : : : : : : 
: : : : : : : 4
2.2 Projection Techniques and Levi's Lemma : : : : : : : : : : : : : : : 
: : : : 7
2.3 Normal Forms : : : : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : 9
2.4 A Simple Algorithm to Compute Normal Forms : : : : : : : : : : : : : 
11
2.5 Möbius Functions and Normal Forms : : : : : : : : : : : : : : : : : 
: : : : : : 11
2.6 Bibliographical Remarks : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : 16
3. Combinatorial Properties : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : 16
3.1 Equations : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : : : : 16
3.2 Strong Homomorphisms and Codings : : : : : : : : : : : : : : : : : : 
: : : : : 19
3.3 Trace Codes : : : : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : : : 22
3.4 Bibliographical Remarks : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : 23
4. Recognizable Trace Languages : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : 24
4.1 Basic Facts about Recognizable and Rational Sets : : : : : : : : : : 
: : 24
4.2 Recognizability and Rational Operations : : : : : : : : : : : : : : 
: : : : : : 25
4.3 The Rank : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : : : 26
4.4 Recognizability and the Lexicographic Normal Form : : : : : : : : : 
: 29
4.5 The Star Problem and the Finite Power Property : : : : : : : : : : : 
: 30
4.6 An Algorithm to Compute Closures : : : : : : : : : : : : : : : : : : 
: : : : : : 33
4.7 Bibliographical Remarks : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : 38
5. Rational Trace Languages : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : 38
5.1 Unambiguous Languages : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : 38
5.2 Decidability Results : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : 40
5.3 Bibliographical Remarks : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : 42
6. Dependence Graphs and Logic : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : 43
6.1 Dependence Graphs : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : 43
6.2 Traces and Logic : : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : 46
6.3 Ehrenfeucht-Frä?ss?e-Games : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : 49
6.4 Bibliographical Remarks : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : 52
7. Asynchronous Automata : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : 52
7.1 Zielonka's Theorem : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : 52
7.2 Asynchronous Cellular Automata : : : : : : : : : : : : : : : : : : : 
: : : : : : : 54


2 Table of Contents

7.3 Changing Concurrent-Read to Exclusive-Read : : : : : : : : : : : : : 
: : 54
7.4 Changing Exclusive-Write to Owner-Write : : : : : : : : : : : : : : 
: : : : 55
7.5 The Construction for Triangulated Dependence Alphabets : : : : 56
7.6 Bounded Time-Stamps in a Distributed System : : : : : : : : : : : : 
: : 58
7.7 Bibliographical Remarks : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : 62
8. Infinite Traces : : : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : : : : : : 62
8.1 Real Traces : : : : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : : : 62
8.2 Asynchronous Büchi- and Muller Automata : : : : : : : : : : : : : : 
: : : 66
8.3 Complex Traces : : : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : 67
8.4 Topological Properties and the Domain of ffi-Traces : : : : : : : : 
: : : 69
8.5 Bibliographical Remarks and Further Reading : : : : : : : : : : : : 
: : : 72
References : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 
: : : : : : : : : : : : : : : : : : : : : : 73


Partial Commutation and Traces

Volker Diekert1 and Yves M?etivier2

1 Institut für Informatik, Universität Stuttgart
Breitwiesenstr. 20-22, D-70565 Stuttgart, Germany
2 LaBRI, Universit?e Bordeaux I, ENSERB,
351 cours de la Lib?eration, F-33405 Talence, France

1. Introduction

Parallelism and concurrency are fundamental concepts in computer 
science. Specification and verification of concurrent programs are of 
first importance. It concerns our daily life whether software written 
for distributed systems behaves correctly.

It is clear that a satisfactory notion of correctness has to be based on 
a rigorous mathematical model. Several formalisms have been proposed. 
Among others there are Petri nets, Hoare's and Milner's CSP and CCS, 
event structures, and branching temporal logics. The mathematical 
analysis of these models may become complicated, however. Based on the 
behavior of elementary net systems Mazurkiewicz introduced the concept 
of partial commutation to the computer science community. The abstract 
description of a concurrent process is then called a trace, being 
defined as a congruence class of a word (sequence) modulo identities of 
the form ab = ba for some pairs of letters.

The success of Mazurkiewicz' approach results from the fact that on one 
hand partial commutation copes with some important phenomena in 
concurrency and on the other hand it is close to the classical theory of 
free monoids describing sequential programs. In particular it is 
possible to transfer the notion of finite sequential state control to 
the notion of finite asynchronous state control. There is a satisfactory 
theory of recognizable languages relating finite semigroups, rational 
operations, asynchronous automata, and logic. This leads to decidability 
results and various effective operations.

The theory of partial commutation and of trace monoids has been 
developed both by its interpretation as a model for parallel computation 
and by its mathematical interest in algebra, formal languages, and 
combinatorics. Since the beginning in combinatorics by Cartier and Foata 
(1969) and the formulation of trace theory by Mazurkiewicz (1977) the 
theory has grown in breadth and depth. It led to significant results 
with interesting applications. The present contribution reflects some 
important topics including basic properties and infinite traces. Most of 
the results are from the monograph [34], but we covered also some new 
material. Each section gives a short bibliographical remark and leads to 
further references.


4 Volker Diekert and Yves M?etivier

Acknowledgments: This work has been partially supported by the ES- PRIT 
Basic Research Action No. 6317 ASMICS II and the French-German research 
program PROCOPE. We are indebted to Michael Bertol, Manfred Droste, Paul 
Gastin, Hendrik Jan Hoogeboom, Anca Muscholl, Holger Petersen, and Wies 
law Zielonka. Without the help of Michael Bertol the manuscript would 
not have been written in time. Last but not least, we thank Professors 
Grzegorz Rozenberg and Arto Salomaa for including our contribution in 
the present volume.

2. Free Partially Commutative Monoids

2.1 First Definitions and Basic Properties

Let ? be a finite alphabet, its elements are called letters. We denote 
by ?? the set of all words over ?. Formally, ?? with the concatenation 
operation forms the free monoid with the set of generators ?, the empty 
word, denoted by 1, plays the role of the unit element. For any word x 
of ??, jxj denotes the length of x and jxja denotes its a-length, i.e., 
jxja is the number of occurrences of a letter a in x. The notation 
alph(x) = fa 2 ? j jxja 6= 0g is used for the set of letters of ? 
actually appearing in the word x.

Throughout we mean by I ? ? ?? a symmetric and irreflexive relation over 
the alphabet ?, called the independence (or commutation) relation. 
Intuitively, (a; b) 2 I means that a and b act on disjoint sets of 
resources. As a consequence, the order in which they are performed does 
not matter, ab = ba. They can also be performed in parallel or 
simultaneously. For every letter a of ?, we denote by I(a) the set of 
letters which commute with a:
I(a) = fb 2 ? j (a; b) 2 Ig:

The pair (?; I) is called the independence alphabet and can be 
conveniently represented by an undirected graph (also called the 
commutation graph). The vertex set is ?, edges are between independent 
letters.

Example 2.1. Let ? = fa; b; c; dg and I = f(a; d); (d; a); (b; c); (c; 
b)g, then the commutation graph is given in the picture below.

a

c

b

d

(?; I) =

The complement ? ? ? n I of I is called the dependence relation D. 
Intuitively, two letters a and b such that (a; b) =
2 I are dependent and cannot
be executed simultaneously.


Partial Commutation and Traces 5

The pair (?; D) is called the dependence alphabet . Again, we identify 
(?; D) with an undirected graph (the non-commutation graph). In the 
pictures we omit always the self-loops. If we take the same example as 
above, the dependence alphabet is given by the following non-commutation 
graph.

a

c

b

d

(?; D) =

For any letter a of ?, D(a) denotes the set of letters which depend on 
a:

D(a) = fb 2 ? j (a; b) =
2 Ig:

Since I is irreflexive, we have a 2 D(a). We extend this notation for 
all A ? ? by setting:
D(A) = fb 2 ? j 9a 2 A : (a; b) 2 Dg:

The relation I induces an equivalence relation ?I over ??. Two words x 
and y are equivalent under ?I , denoted by x ?I y, if there exists a 
sequence z1; z2; : : : ; zk of words such that x = z1, y = zk, and for 
all i, 1 <= i < k, there exist words z0
i, z00
i , and letters ai, bi satisfying:

zi = z0
iaibiz00
i ; zi+1 = z0
ibiaiz00
i ; and (ai; bi) 2 I :

Thus, two words are equivalent by ?I if one can be obtained from the 
other by successive transpositions of neighboring independent letters. 
It is easy to verify that ?I is the least congruence over ?? such that 
ab ?I ba for all pairs (a; b) 2 I . The quotient of ?? by the congruence 
?I is the free partially commutative monoid induced by the relation I , 
it is denoted by M (?; I). The elements of M (?; I), which are 
equivalence classes of words of ?? under the relation ?I , are called 
traces . Consequently, M (?; I) is called trace monoid , too.

If I is empty, then M (?; I) is the free monoid ??; if any two different 
letters of ? commute, then M (?; I) is the free commutative monoid 
denoted by N? or simply by Nk where k = j?j. Other families of free 
partially commutative monoids are the direct products of free monoids:

??
1 ???
2 ? ? ? ? ???
n

and free products of free commutative monoids:

Nk1 ? Nk2 ? ? ? ? ? Nkn

For a word x of ?? the equivalence class of x under ?I is denoted by 
[x]I . Thus, [x]I is the set of words which are equivalent to a given 
word x, hence

[x]I = fy 2 ?? j y ?I xg:


6 Volker Diekert and Yves M?etivier

For instance, if we consider I defined above, we have:

[baadcb]I = fbaadcb; baadbc; badacb; badabc; bdaabc; bdaacbg:

Since the relation ?I is a congruence, the concatenation in M (?; I) is 
given by [x]I [y]I = [xy]I for all x; y 2 ??. The class of the empty 
word is called the empty trace, also denoted by 1. The definition of 
length, of a-length, and of the alphabet is invariant under the 
commutation of letters, hence it can be transferred to a trace from any 
representing word. We can write jtj, jtja, and alph(t) for a trace t and 
a letter a. Following the same example above with t = [baadcb]I we have 
jtj = 6, jtja = jtjb = 2, jtjc = jtjd = 1, and alph(t) = fa; b; c; dg. A 
trace t (word x; resp.) is called connected, if alph(t) (alph(x), resp.) 
induces a connected subgraph of (?; D). The trace t = [baadcb]I above is 
connected, but [ad]I is not.
Two traces u and v of M (?; I) are said to be independent and this fact 
is denoted by uIv, if
alph(u) ? alph(v) ? I :

Independence of traces is equivalent to the following condition:

uv = vu and alph(u) \ alph(v) = ;:

Trace monoids are placed between free and free commutative monoids. 
There are two canonical homomorphisms:

' : ?? ?! M (?; I)

x 7?! [x]I

and

ß : M (?; I) ?! N?

t 7?! (jtja)a2? :

The image ß(t) 2 N? is called the Parikh-image of t 2 M (?; I). The 
composition ?? '
?! M (?; I)
ß
?! N?

is the usual Parikh-mapping from words to vectors.

For sake of simplicity we sometimes use words to denote the 
corresponding trace. Thus, if x 2 ?? and the context M (?; I) is clear 
then we may write x 2 M (?; I) to denote in fact the class [x]I . 
Following the same convention, we view ? as a subset of M (?; I), too. 
If x is a word or a trace then x? is either the set of words fxn j n >= 
0g or the set of traces f[xn]I j n >= 0g. A trace language is any subset 
of M (?; I). If X ? ??, then the trace language '(X) ? M (?; I) is also 
denoted by [X ]. This allows to write

[X ] = f[x]I j x 2 Xg:


Partial Commutation and Traces 7

For any trace language T ? M (?; I), the language '?1(T ) consists of 
all representing words. The operation X 7! '?1([X]) can be viewed as a 
closure operation on languages. Therefore we prefer to write X instead 
of '?1([X]) or '?1('(X)). A subset X of ?? is said to be I-closed (or 
simply closed, if there is no ambiguity), if X = X .
For example, let I be defined as in Ex. 2.1, if X = (ad)? then

X = fx 2 fa; dg? j jxja = jxjdg:

2.2 Projection Techniques and Levi's Lemma

Let A ? ? be a subset and IA = (A?A)\I be the induced independence 
relation. We may define a canonical homomorphism ßA : M (?; I) ! M (A; 
IA ) by erasing all letters from a trace which do not belong to A, hence 
for a 2 ? we have:
ßA(a) = a, if a 2 A and ßA(a) = 1 otherwise:

Of particular interest is IA = ;. Then A is a clique of the dependence 
alphabet and ßA a projection onto the free monoid A?. This is in 
particular the case when A = fa; bg and (a; b) 2 D. (We shall write ßa;b 
instead of ßfa;bg.) The following proposition is called Projection 
Lemma. It states that every trace has a unique representation as a tuple 
of words. For (?; I) fixed this canonical representation is computable 
in linear time from any word defining the congruence class of a trace.

Proposition 2.1. Let u and v be two traces of M (?; I), then we have u = 
v if and only if
ßa;b(u) = ßa;b(v) for all (a; b) 2 D:

Proof. Clearly, the condition is necessary. Conversely, we prove by 
induction on the length of u (and of v). If u or v is the empty trace we 
have nothing to do. Let us suppose u = au0 and v = cv0; where a and c 
are letters of ? and where u0 and v0 are traces of M (?; I).

We assume first a 6= c. Since juja = jvja, we have jv0ja >= 1 and v0 = 
t0at00 with jt0ja = 0. If (a; b) 2 D, then ßa;b(u) = ßa;b(v) and hence 
(ct0)Ia. Finally v = ct0at00 = act0t00. Thus, we have reduced to the 
case a = c, or u = au0 and v = av00 for some traces u0; v00. The 
inductive hypothesis yields u0 = v00, hence u = v.

Since direct products of free monoids are cancellative, we deduce the 
same property for trace monoids.

Corollary 2.1. The monoid M (?; I) is cancellative, i.e., the equation 
uxv = uyv implies x = y for all u; v; x; y 2 M (?; I).

Another corollary shows the following version of an embedding theorem.

8 Volker Diekert and Yves M?etivier

Corollary 2.2. Let (?; D) =
k
S

i=1
(Ai; Di) be a union of subalphabets with

Ii = (Ai ? Ai) n Di, M i = M (Ai ; Ii), and ßi : M (?; I) ! M i the 
canonical homomorphism for 1 <= i <= k. Then we obtain a canonical 
injective homomorphism M (?; I) ?! M 1 ? ? ? ? ? M k
t 7?! (ß1(t); : : : ; ßk(t)):

The following proposition is called Levi's Lemma. It is one of the most 
important tools in trace theory.

Proposition 2.2. Let t, u, v, and w be traces of M (?; I). Then the 
following assertions are equivalent.

i) tu = vw
ii) There exist p; q; r; s 2 M (?; I) such that
t = pr; u = sq; v = ps; w = rq with alph(r) ? alph(s) ? I.

Proof. Clearly, ii) implies i). Conversely, we use an induction on the 
length of t. It t is the empty trace then the property is true with p = 
r = 1; q = w and s = v. Therefore we may assume that t = at0 for some a 
2 ?.

{ If jvja = 0 then necessarily aIv and w = aw0. As at0u = vaw0 and aIv 
we have t0u = vw0. Now applying the inductive hypothesis we find p; q; 
r0; s 2 M (?; I) such that

t0 = pr0; u = sq; v = ps; w0 = r0q and r0Is:

Let r = ar0; as aIv, we also have aIp and aIs. Hence

t = at0 = apr0 = par0 = pr

with rIs; and the result follows.
{ If jvja > 0, then v = av0. In this case we apply the inductive 
hypothesis with t0u = v0w. We find p0; q; r; s such that t0 = p0r; u = 
sq; v = p0s; w = rq and rIs. The desired formula is obtained considering 
t = at0 and p = ap0.

From this proposition, using an induction, we obtain the following more 
general form of Levi's Lemma:

Corollary 2.3. Let u; v; t1; : : : ; tn 2 M (?; I) be traces. Then the 
following assertions are equivalent.

i) uv = t1 ? ? ? tn,
ii) There exist p1; : : : ; pn; q1; : : : ; qn 2 M (?; I) such that u = 
p1p2 ? ? ? pn; v = q1 ? ? ? qn with piqi = ti and qiI(pi+1 : : : pn) for 
all 1 <= i < n.

Together with the existence of a positive weight, Levi's Lemma 
characterizes free partially commutative monoids. By a positive weight 
we mean any homomorphism fl : M ! N such that fl?1(0) = f1g. For trace 
monoids the length-function is a positive weight.


Partial Commutation and Traces 9

Proposition 2.3. A monoid M with a positive weight is isomorphic to a 
free partially commutative monoid if and only if for all x; y; z; t 2 M 
the equation xy = zt implies the existence of r; u; v; s 2 M such that x 
= ru, y = vs, z = rv, t = us, and uv = vu.

Proof. We need a proof only for the if-part.
Let ? = (M n f1g) n (M n f1g)2. A straightforward verification shows 
that ? generates M and that it is contained in any set generating M : it 
is the minimal generating set of M . We define the independence relation 
IM on ? by (x; y) 2 IM , if yx = xy in M .

Let ' be the canonical surjective homomorphism from ?? onto M ; it 
induces a surjective homomorphism ' : M (?; IM ) ! M . We prove by 
induction on the weight that ' is injective. Let t0; t00 2 M (?; IM ) 
such that '(t0) = '(t00). Using induction, we assume that every proper 
factor of t0 has exactly one inverse image. If t0 2 ? [ f1g then t0 = 
t00 since '?1(x) = fxg for all x 2 ? [ f1g. If t0 =
2 ? [ f1g then t0 = xy; t00 = zt with x; z 2 ? and
y 6= 1; t 6= 1. Since '(x)'(y) = '(z)'(t) and ' is surjective, the 
hypothesis about M implies that

'(x) = '(r)'(u); '(y) = '(v)'(s); '(z) = '(r)'(v); '(t) = '(u)'(s)

and '(uv) = '(vu);

where r; u; v; s are some traces of M (?; IM ). Since '(x), '(y), '(z), 
'(t) are proper factors of '(t0), we have

x = ru; y = vs; z = rv; and t = us:

{ If r 6= 1 or s 6= 1, then '(uv) is a proper factor of '(t0); it 
follows uv = vu in M (?; IM ). Hence t0 = ruvs = rvus = t00.
{ If r = s = 1; then u = x 2 ? and v = z 2 ?; thus, u; v 2 ? are 
independent elements and t0 = uv = vu = t00 are the same trace by 
definition of IM .

2.3 Normal Forms

Two main normal forms are defined in a free partially commutative 
monoid, the lexicographic normal form (studied first by Anisimov and 
Knuth [3]) and the Foata normal form. We assume that the alphabet ? is 
totally ordered, and we consider the corresponding lexicographic 
ordering < on ??. Let X be a set of words, the unique minimal element of 
X with respect to the lexicographic ordering (if it exists) is denoted 
by Min(X). A word x is said to be in the lexicographic normal form if it 
is minimal among the set of words which are equivalent to x; i.e.,

x = Min([x]):

As the lexicographic ordering is a total order and [x] is finite, each 
trace has a unique minimal representative.
Let I be the independence relation of Ex. 2.1 above, assuming that a < b 
< c < d; then the word baadbc is in lexicographic normal form.

10 Volker Diekert and Yves M?etivier

Proposition 2.4. A word x is the lexicographic normal form of a trace if 
and only if for all factorizations x = ybuaz, where y; u; z 2 ??; (a; b) 
2 I ; and a < b, there exists a letter of u which does not commute with 
a.

Proof. If x is minimal then, clearly, it satisfies the condition of the 
statement. Conversely, suppose there is a word w equivalent to x such 
that w < x; then x = x0bx00 and w = x0az0 with a < b. The words x and w 
are equivalent, thus aIb. Since jxja = jwja we have x00 = uav with juja 
= 0. Now from the equivalence between x and w we deduce that aIu. 
Therefore x does not satisfy the condition of the proposition.

From this we deduce immediately that the set LexNF of words in 
lexicographic normal form is a regular language; indeed it is equal to 
the following (star-free) set

LexNF = ?? n
[

(a;b)2I;a<b
??bI(a)?a??:

A word x of ?? is in the Foata normal form, if it is the empty word or 
if there exist an integer n > 0 and non-empty words xi (1 <= i <= n) 
such that

i) x = x1 ? ? ? xn;
ii) for each i; the word xi is a product of pairwise independent letters 
and xi is minimal with respect to the lexicographic ordering,
iii) For each 1 <= i < n and for each letter a of xi+1 there exists a 
letter b of xi such that (a; b) 2 D.

If we consider the factorization of Foata given above, each xi is called 
a step. Let I be defined by the first picture, the Foata normal form of 
baadcb is (b)(ad)(a)(bc).

Proposition 2.5. Every trace has a unique Foata normal form.

Proof. Let x be a word of ??. We prove the existence of a normal form by 
induction on the length of x. The result is trivial if x = 1. Let x = 
x0a with a 2 ?; let x0
1x0
2 ? ? ? x0
n be a decomposition in steps for x0. If aIx0 then let
i = 0, else let i be the integer such that x0
i is the right-most step containing
a letter b such that (a; b) 2 D.
Let x00 be the word obtained inserting a in x0
i+1 with respect to the lexicographic ordering. The decomposition x0
1x0
2 ? ? ? x0
ix00x0
i+2 ? ? ? x0
n is a normal
form for x.

We prove the uniqueness by contradiction. Assume that there exists a 
word x with two different normal forms. We choose x with minimal length, 
let x0
1x0
2 ? ? ? x0
n and x00
1 x00
2 ? ? ? x00
p be two step decompositions of x. As x has
minimal length and trace monoids are cancellative, Cor. 2.1, necessarily 
x0
1 and x00
1 are different: x0
1 = yay0 and x00
1 = yby00 with a 6= b. Thus,
x0
1x0
2 ? ? ? x0
n = yay0x0
2 ? ? ? x0
n and x00
1 x00
2 ? ? ? x00
p = yby00x00
2 ? ? ? x00
p . If b =
2 alph(y0) we
have x0
2 ? ? ? x0
n = z0bz00 with jz0jb = 0. As yay0z0bz00 ? yby00x00
2 ? ? ? x00
p necessarily bI(ay0z0) by Prop. 2.1. This yields a contradiction to the 
third condition


Partial Commutation and Traces 11

of the definition of a Foata normal form; thus b 2 alph(y0) and by 
symmetry a 2 alph(y00). Using once more the definition of the normal 
form, we have a < b and b < a. This yields the final contradiction and 
the result.

2.4 A Simple Algorithm to Compute Normal Forms

Let us describe a simple method which enables to compute normal forms. 
Let M (?; I) be a free partially commutative monoid, we use a stack for 
each letter of the alphabet ?. Let x be a word of ??; we scan x from 
right to left; when processing a letter a it is pushed on its stack and 
a marker is pushed on the stack of all the letters b (b 6= a) which do 
not commute with a. When all of the word has been processed we can 
compute either the lexicographic normal form or the Foata normal form.

{ To get the lexicographic normal form: it suffices to take among the 
letters being on the top of some stack that letter a being minimal with 
respect to the given lexicographic ordering. We pop a marker on each 
stack corresponding to a letter b (b 6= a) which does not commute with 
a. We repeat this loop until all stacks are empty.
{ To get the Foata normal form we take within a loop the set formed by 
letters being on the top of stacks; arranging the letters in the 
lexicographic order yields a step. As previously we pop the 
corresponding markers. Again this loop is repeated until all stacks are 
empty.

For example, with (?; I) as in Ex. 2.1 and the word badacb we get the 
stacks given below. The lexicographic normal form is baadbc, and the 
Foata normal form is (b)(ad)(a)(bc).

a

?
?
a
a
?

b
?
?
?
b

b

c
?
?
?

c

?
?
d
?

d

2.5 M?
obius Functions and Normal Forms

This section presents the relation between liftings of Möbius functions 
and normal forms for trace monoids. It will not be used in the sequel. A 
reader not being familiar with the basic notions might skip this 
section. It is worth mentioning however that the study of the Möbius 
function was really at the beginning of trace theory in combinatorics. 
In particular, Thm. 2.1 below is from the original Lecture Notes [13] by 
Cartier and Foata.

12 Volker Diekert and Yves M?etivier

Let M = M (?; I) and ' : ?? ?! M the canonical homomorphism. A set of 
normal forms (or a cross-section) is a subset S ? ?? such that ' induces 
a bijection between S and M . For example, LexNF is a set of normal 
forms. By OS we denote the characteristic function of S:

OS(w) = 1; if w 2 S and OS(w) = 0 otherwise.

We view OS as a function from ?? to Z. Functions from ?? (from M resp.) 
to Z are called formal power series . The set of all power series is 
denoted by Zhh??ii (by ZhhM ii resp.). A convenient notation of power 
series is

f =
X

w
f(w)w:

The set of power series is a ring by the usual addition and the 
noncommutative Cauchy-product.

(f + g)(w) = f(w) + g(w)

(f ? g)(w) =
X

uv=w
f(u)g(v)

The unit of this ring is 1 = Of1g, which fits perfectly to the notation 
of power series above. (More general, identifying w 2 M with Ofwg the 
notation above becomes a true identity on power series.) If f(1) 2 f?1; 
+1g, then there exists a unique power series f?1 such that f ? f?1 = f?1 
? f = 1, it is called the formal inverse of f . Clearly, (f?1)?1 = f .
There is a canonical ring homomorphism from Zhh??ii onto ZhhM ii, 
denoted (by abuse of language) again by '. We have ('(f))(t) = P
'(w)=t f(w)
for all f 2 Zhh??ii and t 2 M . Observe that S ? ?? is a set of normal 
forms if and only if '(OS) = OM . The function OM : M ?! Z is the 
constant function with value 1. An important combinatorial property of 
finitely generated free partially commutative monoids is that the formal 
inverse (OM )?1 2 ZhhM ii is a polynomial, i.e., only finitely many 
values are non-zero.

Definition 2.1. Denote by F = fF ? ? j (a; b) 2 I for all a; b 2 F; a 6= 
bg the set of independence cliques. For each F 2 F let [F ] 2 M be the 
trace [F ] = Q
a2F a. (The product is well-defined, since the elements of F commute.) 
The clique polynomial of M is defined as the formal power series

?M =
X

F2F
(?1)jF j[F ]:

Theorem 2.1. The clique polynomial ?M is the Möbius function of M (?; 
I), i.e., ?M is the formal inverse of the constant function with value 
1:

?M = (OM )?1:


Partial Commutation and Traces 13

Proof. We have to show (?M ? OM )(t) = 1, if t = 1 and (?M ? OM )(t) = 0 
otherwise. For t 2 M let min(t) be the set of minimal elements, i.e., 
min(t) = fa 2 ? j t = as for some s 2 M g.
Clearly, min(t) 2 F and we have

(?M ? OM )(t) =
X

t=[F ]?s

(?1)jF j:

Since M is left cancellative we can write

(?M ? OM )(t) =
X

F?min(t)

(?1)jF j:

Indeed, if t = [F ] ? s, then F ? min(t) and s is uniquely defined by F 
. Conversely, if F ? min(t), then F 2 F and there exists some unique s 2 
M such that t = [F ] ? s. Therefore the claim follows (with n = j 
min(t)j) from the well-known identity

X

F?min(t)

(?1)jF j =
X

k

?
n

k

?

(?1)k =

?
1 if n = 0;
0 otherwise.

Remark 2.1. For infinitely generated free partially commutative monoids 
Thm. 2.1 holds as well. The only difference is that ?M becomes a formal 
power series with infinitely many non-zero coefficients. The classical 
Möbius inversion formula is now a corollary. Let N0 = fn 2 N j n > 0g be 
the multiplicative monoid of positive integers. It is a commutative 
monoid, freely generated by the primes. The Möbius function from 
elementary number theory is

? : N0 ?! Z; ?(n) =

?
(?1)k if n is a product of k distinct primes, k >= 0
0 otherwise.

Thus, ? is the Möbius function of the monoid N0 . Let f; g : N0 ! Z be 
two functions. Möbius inversion states the equivalence:

8n : g(n) =
X

djn
f(d) () 8n : f(n) =
X

djn
?(d)g(
n

d
):

This is a direct consequence of Thm. 2.1 in the special case of the 
commutative monoid N0 , since the equivalence states g = f ? ON0 () f = 
?N0 ? g:

Definition 2.2. A lifting of the Möbius function ?M is a polynomial ? 2 
Zhh??ii such that first '(?) = ?M and second ' induces a bijection 
between the two sets fwF 2 ?? j ?(wF ) 6= 0g and f[F ] 2 M j F 2 Fg. It 
is called an unambiguous lifting if, in addition, ??1(w) >= 0 for all w 
2 ??.

Remark 2.2. If ? 2 Zhh??ii is an unambiguous lifting of ?M then we can 
write ? =
P
(?1)jwF jwF .


14 Volker Diekert and Yves M?etivier

The following corollary is a direct consequence of Thm. 2.1 and of the 
definition of an unambiguous lifting.

Corollary 2.4. If ? 2 Zhh??ii is an unambiguous lifting of ?M , then the 
formal inverse ??1 is the characteristic function over a set of normal 
forms.

Another way to obtain a set of normal forms is by complete rewriting 
systems. Let us recall some basic notions and facts.
A semi-Thue system is a set of rules R ? ?? ? ??. It defines a onestep 
reduction =) R
by ulv=)
R
urv for u; v 2 ??; (l; r) 2 R. By
?
=)
R
(and
?
()
R
,

resp.) we denote the reflexive and transitive closure (reflexive, 
symmetric and transitive closure resp.) of =)
R
. By ??=R we mean the quotient monoid

??=
?
()
R
.

Example 2.2. For an independence relation I ? ??? and a partial order < 
of ? let
S(I) = f(ab; ba) j (a; b) 2 Ig;
S(I ; <) = f(ba; ab) j (a; b) 2 I and a < bg:

Then we have ??=S(I) = M (?; I) and if for all (a; b) 2 I either a < b 
or b < a, then ??=S(I ; <) = M (?; I).

{ A semi-Thue system R is called Noetherian, if there is no infinite 
chain w1=)
R
w2=)
R
? ? ?,

{ it is called confluent , if for all u
?
(=
R
w
?
=)
R
v, there exists some z 2 ?? such

that u
?
=)
R
z
?
(=
R
v.

{ Confluence of Noetherian systems is equivalent with local confluence, 
i.e., for all u(=
R
w=)
R
v there exists some z 2 ?? such that u
?
=)
R
z
?
(=
R
v.

{ A system being both Noetherian and (locally) confluent is called 
complete.

{ For a complete system R, the set of irreducible words

Irr(R) = fw 2 ?? j6 9v : (w=)
R
v)g

is in canonical bijection with the quotient monoid ??=R. Hence, Irr(R) 
is a set of normal forms for the monoid ??=R.

Definition 2.3. Let (?; I) be an independence alphabet. A transitive 
orientation of I is a partial order < of ? such that first I+ = f(a; b) 
2 I j a < bg is a transitive relation and second, it holds either a < b 
or b < a for all (a; b) 2 I.


Partial Commutation and Traces 15

Lemma 2.1. i) Let < be a transitive orientation of I and the 
lexicographical order of ?? be defined by some linear extension of <. 
Then S(I ; <) is complete and the set of irreducible words is the set of 
lexicographic normal forms, Irr(S(I ; <)) = LexNF.
ii) Let R ? ?? ? ?? be any finite complete semi-Thue system such that 
??=R = M (?; I). Then there exists a transitive orientation < such that 
S(I ; <) ? R. In particular, by i) we have Irr(R) = LexNF.

Proof. i): By the characterization of lexicographic normal forms, c.f. 
Prop. 2.4, the following (infinite (!)) system is easily seen to be 
complete:

R = f(bua; abu) j a < b and aI(bu)g:

Of course S(I ; <) ? R and Irr(R) = LexNF. Since < is a transitive 
orienta-

tion, one can show that (bua; abu) 2 R implies bua
?
=)
S(I;<)
z for some z with

abu
?
=)
R
z. Since R is Noetherian, we have
?
=)
R
=
?
=)
S(I;<)
and i) follows.

ii): Consider the relation < satisfying a < b () (ba; ab) 2 R. The 
relation < is asymmetric and irreflexive and it holds a < b or b < a for 
all (a; b) 2 I . Moreover, an easy reflection shows a?b? ? Irr(R) for 
all a < b. Consider a < b < c and cnbnan for n >= 0. Then
bncnan ?
(=
R
cnbnan ?
=)
R
cnanbn

Since R is finite and complete, we have cnan =
2 Irr(R) for n large enough.
Hence, (a; c) 2 I but we do not have c < a. Therefore a < c, and < is 
transitive. Since < is asymmetric, the relation is a partial order, and 
it is a transitive orientation of I . The assertion follows.

There is a surprising relation between unambiguous liftings of Möbius 
functions, finite complete semi-Thue systems, and transitive 
orientations of I . We can state the following theorem.

Theorem 2.2. Let (?; I) be an independence alphabet M (?; I). Then the 
following assertions are equivalent.

i) There exists an unambiguous lifting of the Möbius function ?M . ii) 
There exists a finite complete semi-Thue system R such that ??=R = M . 
iii) There exists a transitive orientation of I.

In fact, Thm. 2.2 is a corollary of Prop. 2.1 and the following more 
precise theorem.

Theorem 2.3. i) Let ? 2 Zhh??ii be an unambiguous lifting. For (a; b) 2 
I define a < b by ?(ba) = 1. Then < is a transitive orientation, S(I ; 
<) is complete, and we have ??1 = OIrr(S(I;<)).
ii) Let < be a transitive orientation of I. Then there exists a unique 
unambiguous lifting ? such that ?(ba) = 1 for all a < b; (a; b) 2 I. 
This function ? is characterized by ? = (OIrr(S(I;<))?1.


16 Volker Diekert and Yves M?etivier

2.6 Bibliographical Remarks

The theory of free partially commutative monoids (trace theory) has its 
origins in combinatorics. The existence of the Foata normal form and the 
characterization of the Möbius function as the polynomial over the 
independence cliques is from [13]. In computer science trace theory 
became popular mainly by the work of Mazurkiewicz, see [69, 70]. Early 
ideas can also be found in the paper by Keller (1973), where the 
Projection Lemma is (implicitly) stated in [64, Lem. 2.5]. The 
Projection Lemma in the more general context of semi-commutations is due 
to Clerbout [15]. Levi's Lemma and the Projection Lemma, as stated here, 
can be found in a paper of Cori and Perrin [21]. Prop. 2.3 has been 
shown by Duboc [40]. The characterization of lexicographic normal forms, 
Prop. 2.4, is due to Anisimov and Knuth [3]. The simple algorithm to 
compute normal forms has been proposed by Perrin, see [84].

The characterization, when lexicographic normal forms are the 
irreducible words of some finite complete semi-Thue system, is from 
M?etivier and Ochma?nski [75] and Otto [82]. The bridge to unambiguous 
lifting of the Möbius functions is from Diekert [23]. A generalization 
of Thms. 2.2 and 2.3 has been conjectured in [24] and later been shown 
in [26].

3. Combinatorial Properties

3.1 Equations

Let M be any monoid. Two elements x; y 2 M are called conjugated , if xz 
= zy for some z 2 M . They are called transposed , if x = uv and y = vu 
for some u; v 2 M . Clearly, transposed elements are conjugated, and 
conjugacy is transitive. In free commutative monoids conjugacy is the 
identity relation. In free monoids conjugated elements are transposed. 
Moreover, if x = uv and y = vu, then u; v 2 r? for some word r. These 
results generalize immediately to direct products of free monoids. (The 
word r has however to be replaced by a tuple of pairwise independent 
words (r1; : : : ; rk) such that u; v 2 r? 1 ? ? ? r?
k.)
For trace monoids where the dependence relation D is not transitive, the 
situation is different. Let (?; D) = a ? b ? c. Then the traces abc and 
cba are not transposed, but they are conjugated: (abc)(aba) = 
(aba)(cba), since ac = ca. Note that abc and bca = bac are transposed, 
as well as bac and cba. Thus, the conjugation of abc and cba has been 
realized by two transpositions. This is a general fact: In trace monoids 
conjugacy is always equal to the equivalence relation generated by 
transposition.

Proposition 3.1. Let x; y; z 2 M (?; I) be traces. Then we have xz = zy 
if and only if there are traces z1; z2; u1; : : : ; uk, k >= 0, 
satisfying the following conditions

i) x = u1 ? ? ? uk, y = uk ? ? ? u1,


Partial Commutation and Traces 17

ii) uiIuj for 1 <= i < j ? 1 <= k ? 1,
iii) z1 = (u1 ? ? ? uk?1) ? ? ? (u1u2)u1,
iv) z = z1z2 with xIz2.

Proof. Using the Projection Lemma, Prop. 2.1, an easy reflection shows 
that the conditions imply xz = zy. For the converse let xz = zy. By 
Levi's Lemma, Prop. 2.2, we can write x = x0u, z = z0y0 = x0z0, and y = 
uy0 with uIz0. If x0 = 1 then we are done with x = y = u and z = z0. If 
x0 6= 1, then jz0j < jzj and we can use induction. Hence we may assume 
x0 = u1 ? ? ? uk, y0 = uk ? ? ? u1, uiIuj for 1 <= i < j ?1 <= k?1, z0
1 = (u1 ? ? ? uk?1) ? ? ? (u1u2)(u1) and z0 = z0
1z2
with x0Iz2. Putting uk+1 = u and z1 = x0z0
1 we obtain the result, since uIz2.

The diameter of a dependence alphabet (?; D) is the maximum over the 
lengths of the shortest paths connecting letters from ?; e.g., if M (?; 
I) is commutative, then the diameter is zero, if it is free and j?j >= 
2, then it is one. For (?; D) = a ? b ? c the diameter is two. Observe 
that some of the ui in Prop. 3.1 may be empty, this allows to regroup 
them. One can derive the following statement.

Corollary 3.1. Let (?; D) be a dependence alphabet of diameter d. Then 
traces x; y 2 M (?; I) are conjugated if and only if they can 
transformed into each other by at most d transpositions.

A basic problem is to determine the solutions of the equation xy = yx in 
trace monoids. As one might hope, the equation xy = yx holds if and only 
if there are pairwise independent and connected traces t1; : : : ; tk 
such that x; y 2 t?
1 ? ? ? t?
k. This will be seen from a more general approach (making proofs thereby 
simpler).

Consider X = fx; yg with x 6= y as an alphabet of two unknowns. A 
(non-trivial) equation in two unknowns e = f is a pair of (distinct) 
words e; f 2 X?. A solution of e = f is a homomorphism ? : X? ! M (?; I) 
such that ?(e) = ?(f ). If a solution ? is defined by ?(x) = u and ?(y) 
= v, we also say that (u; v) is a solution for e = f , or more 
conveniently we write that x = u and y = v. A solution (u; v) is called 
cyclic, if u; v 2 t? for some trace t.

Lemma 3.1. Let x = u, y = v with u; v 2 M (?; I) be a solution of a 
nontrivial equation e = f in unknowns fx; yg. The solution is cyclic, if 
one of the following conditions is satisfied:

i) M (?; I) is free, i.e., I = ;.
ii) ffß(u) = fiß(v) for some rational numbers ff; fi > 0, where ß(u), 
ß(v) denote the Parikh-images of u and v in N? .

Proof. Assume by contradiction that the assertion would be wrong. Let 
(u; v) be a pair where juj + jvj is minimal under the condition that (u; 
v) is a noncyclic solution for some non-trivial equation e = f 
satisfying i) or ii). Clearly,

18 Volker Diekert and Yves M?etivier

by cancellation and symmetry we may assume that e begins with x, f 
begins with y, and juj <= jvj. By Levi's Lemma we can write u = pw0 and 
v = pw with wIw0. If I = ;, then w0 = 1. However, the same is true for 
ii), because ffß(u) = fiß(v) with ff; fi > 0 and juj <= jvj imply juja 
<= jvja for all a 2 ?. Hence we have v = uw in both cases. Moreover, we 
may assume u 6= 1 and w 6= 1. Now replace the unknown y by xz. This 
yields a new non-trivial equation e0 = f 0 in the set of unknowns fx; 
zg. Clearly (u; w) is a solution of e0 = f 0 and we have juj + jwj < juj 
+ jvj. If I = ; then (u; w) is a cyclic solution by minimality of juj + 
jvj. If ffß(u) = fiß(v), then w 6= 1 implies ff > fi. Hence ffß(u) = 
fi(ß(u) + ß(w)) implies (ff ? fi)ß(u) = fiß(w) with (ff?fi); fi > 0. 
Again, by minimality of juj + jvj, we find that (u; w) is a cyclic 
solution. Thus, in both cases u; w 2 t? for some t, hence u; v 2 t? 
being a contradiction.

Remark 3.1. An equation e = f is called unbalanced , if the number of 
occurrences of x (or of y) in the left-hand side of the equation differs 
from that of the right-hand side. Of course, if (u; v) is a solution of 
an unbalanced equation e = f , then ffß(u) = fiß(v) with ff; fi > 0. In 
fact we may take ff = j(jejx ? jf jx)j and fi = j(jf jy ? jejy)j.

The lemma above yields therefore a special case:

Proposition 3.2. Every solution in trace monoids of an unbalanced 
equation in two unknowns is cyclic.

Lemma 3.2. Let x = u, y = v be a solution of a non-trivial equation in 
two unknowns in a trace monoid. Write u = u1 ? ? ? um, v = v1 ? ? ? vn 
such that ui; vj are connected and uiIuj ; viIvj for all i 6= j. Then 
for all (i; j) with 1 <= i <= m and 1 <= j <= n we have either alph(ui) 
= alph(vj) or uiIvj .

Proof. Let a 2 alph(u), b 2 alph(v) with (a; b) 2 D. Projection to fa; 
bg? and applying i) of Lem. 3.1 yields fa; bg ? alph(u) \ alph(v). The 
lemma follows.

Proposition 3.3. Let x = u, y = v be a solution of a non-trivial 
equation in two unknowns in a trace monoid. Then there are pairwise 
independent traces t1; : : : ; tk such that u; v 2 t?
1 ? ? ? t?
k.

Proof. By Lem. 3.2 we are reduced to the case where alph(u) = alph(v) 
and u is connected. Let a; b 2 alph(u), (a; b) 2 D. Choose ff; fi > 0 
such that ffjuja = fijvja. By Lem. 3.1 it is enough to show that ffjujb 
= fijvjb. By projection to fa; bg? and i) of the same lemma we find 
integers ta; tb > 0 such that juja = mta, jvja = nta, jujb = mtb, and 
jvjb = ntb. The above implies ffm = fin and this in turn ffjujb = 
fijvjb.

A connected trace r 2 M (?; I) is called a primitive root , if r = sn 
implies n = 1. From Prop. 3.3 and Lem. 3.2 we may derive the following 
corollaries:

Partial Commutation and Traces 19

Corollary 3.2. Every non-empty connected trace is the power of a unique 
primitive root. Moreover, if uv = vu 2 M (?; I), u 6= 1, and uv is 
connected, then u; v 2 r? for the primitive root r of u.

Corollary 3.3. Let u1; : : : ; uk 2 M (?; I) be pairwise commuting 
traces, i.e., uiuj = ujui for all i; j. Then there are pairwise 
independent and connected traces t1; : : : ; tm such that ui 2 t?
1 ? ? ? t?
m for all 1 <= i <= k.

The following consequence will be used in the next section.

Corollary 3.4. Let h : Nk ! M (?; I) be an injective homomorphism. Then 
? contains at least k pairwise independent letters.

Proof. Let ui be the image under h of the i-th unit-vector, 1 <= i <= k. 
According to Cor. 3.3 write ui = tni;1
1 ? ? ? tni;m
m . The matrix (ni;j)1<=i<=k;1<=j<=m
has rank at least k. Hence m >= k. It is enough to pick one letter from 
each alph(ti), 1 <= i <= m.

3.2 Strong Homomorphisms and Codings

A homomorphism between trace monoids h : M (?; I) ! M (?0 ; I 0) is 
given by a mapping h : ? ! M (?0 ; I 0) such that h(a)h(b) = h(b)h(a) 
for all (a; b) 2 I . We say that h is a strong homomorphism, if moreover 
we have h(a)I 0h(b) for all (a; b) 2 I . This means that independent 
letters are mapped to independent traces. In this section we show that 
the existence of injective strong homomorphisms is directly related to 
morphisms of graphs. By minor modifications the following 
correspondences could be made functorial, but we do not intend to 
introduce categories here.

Definition 3.1. A morphism H of dependence alphabets from (?0; D0) to 
(?; D) is a morphism of the underlying undirected graphs (with 
self-loops), i.e., H is a mapping H : ?0 ! ? on letters such that 
(H(a0); H(b0)) 2 D for all (a0; b0) 2 D0.

Example 3.1. Write (?; D) = (
Sk
i=1 Ai;
Sk
i=1 Ai ?Ai) and let (?0; D0) be the
disjoint union of the complete graphs (Ai; Ai ? Ai). We obtain a 
morphism H : (?0; D0) ?! (?; D) which is induced by set inclusions Ai ? 
?; 1 <= i <= k.

The following proposition is another variant of Prop. 2.1 and of Cor. 
2.2. The proof is an easy exercise.

Proposition 3.4. Let H : (?0; D0) ?! (?; D) be a morphism of dependence 
graphs and for each a 2 ? let h(a) 2 M (?0 ; I 0) be a trace such that 
alph(h(a)) = H?1(a). Then h induces a strong homomorphism h : M (?; I) 
?! M (?0 ; I 0). This homomorphism is injective if and only if H is 
surjective on vertices and edges.


20 Volker Diekert and Yves M?etivier

Example 3.2. Let H : (?0; D0) ! (?; D) as in Ex. 3.1 and let the 
homomorphism h of Prop. 3.4 be defined by h(a) = Q

a02H?1(a)
a0. Then h coincides with

the canonical injective homomorphism from Cor.2.2 in the special case 
where M i = A?
i for all 1 <= i <= k.

An injective homomorphism between trace monoids is denoted henceforth as 
a coding. According to [12] we call an injective strong homomorphism a 
strong coding. A strong coding allows to encode a trace in such a way 
that independency is preserved. The question arises whether there exists 
a strong coding for given dependence alphabets (?; D); (?0; D0). In 
general, the answer is at least NP-hard, due to the following fact 
rephrasing Cor. 3.4.

Proposition 3.5. Let (?; D) be a dependence alphabet and k >= 0. Then 
the following assertions are equivalent:

i) There exists a coding from Nk into M (?; I).
ii) There exists a strong coding from Nk into M (?; I).
iii) The dependence alphabet contains an independent set of size k.

Definition 3.2. A relational morphism H : (?0; D0) ?! (?; D) of 
dependence alphabets is a relation H ? ?0 ? ? such that (a0; b0) 2 D0 
implies H(a0) ? H(b0) ? D. It is called surjective on vertices and 
edges, if both for all a 2 ? there exists a0 2 ?0 with (a0; a) 2 H and 
for all (a; b) 2 D; a 6= b there exists (a0; b0) 2 D0, a0 6= b0 such 
that (a; b) 2 H(a0) ?H(b0).

The following result shows that there exists a strong coding

h : M (?; I) ?! M (?0 ; I 0)

if and only if there exists some relational morphism

H : (?0; D0) ?! (?; D)

being surjective on vertices and edges.

Theorem 3.1. i) Let h : M (?; I) ?! M (?0 ; I 0) be a strong coding and 
H = f(a0; a) 2 ?0 ? ? j a0 2 alph(h(a))g. Then H is a relational 
morphism being surjective on vertices and edges. ii) Let H : (?0; D0) ?! 
(?; D) be a relational morphism being surjective on vertices and edges. 
Then we can construct a strong coding h : M (?; I) ?! M (?0 ; I 0) such 
that H = f(a0; a) 2 ?0 ?? j a0 2 alph(h(a))g.

Proof. Part i) is easy and omitted. We sketch ii): First we order the 
alphabets, i.e., we assume ? = fa1; a2 : : :g with a1 < a2 < ? ? ? and 
?0 = fa0
1; a0
2; : : :g with a0
1 < a0
2 < ? ? ?. For each i = 1; 2; : : :, we define a set Hi
by Hi = fa0
j 2 ?0 j (a0
j ; ai) 2 Hg. If (ai; aj) 2 I , then Hi ? Hj ? I 0, since
H is a relational morphism. We have Hi 6= ; for all i, since H is 
surjective

Partial Commutation and Traces 21

on vertices; and if (ai; aj) 2 D; i 6= j, then there are b0 2 Hi; c0 2 
Hj with (b0; c0) 2 D0; b0 6= c0, since H is surjective on edges.
Assume that Hi = fa0
i1 ; : : : ; a0
ik g with a0
i1 < ? ? ? < a0
ik . Define the traces
?
!
Hi = a0
i1 ? ? ? a0
ik and
?
Hi = a0
ik ? ? ? a0
i1 . Thus,
?
!
Hi is the product of a0
il 2 Hi in

increasing order and
?
Hi is the product in decreasing order. Now define

h : M (?; I) ?! M (?0 ; I 0); h(ai) = (
?
!
Hi)i ?
Hi:

The equality H = f(a0; a) 2 ?0 ? ? j a0 2 alph(h(a))g is obvious. Let us 
show by contradiction that h is injective. Assume h(aix) = h(y), with ai 
2 ? and x; y 2 ?? such that aix 6= y. Then y must contain a letter 
depending on ai, hence we can write y = uajz with aiIu and (ai; aj) 2 D. 
By cancellation we may assume i 6= j. Therefore we find b0 2 Hi; c0 2 Hj 
with (b0; c0) 2 D0; b0 6= c0. The result now follows by projection onto 
fb0; c0g? and some few calculations left to the reader.

Remark 3.2. The proof of Thm. 3.1 is valid for countable alphabets as 
well, as long as we demand that fa0 2 ?0 j (a0; a) 2 Hg is finite for 
all a 2 ?.

Corollary 3.5. It is NP-complete to decide whether there exists a strong 
coding between trace monoids.

Proof. It is clearly in NP to decide whether there exists a relational 
morphism being surjective on vertices and edges. The hardness follows by 
Prop. 3.5, iii).

Corollary 3.6. There is a strong coding of M (?; I) into a k-fold direct 
product of free monoids, if and only if (?; D) has a covering by k 
cliques, i.e.,

(?; D) =
k
[

i=1
Ai;
k
[

i=1
(Ai ?Ai)

!

:

Little is known about the existence of codings. According to the 
following example we can construct codings in some cases, where strong 
codings do not exist.

Example 3.3. Let (?; D) =
a ? b
j j
d ? c
and (?0; D0) = p ? q [ r ? s. Al-

gebraically M 1 = M (?; D) is a free product of commutative monoids, M 1 
= N2 ? N2 , and M 2 = M (?0 ; D0) is a direct product of free monoids, M 
2 = fp; qg? ? fr; sg?. By Cor. 3.6 there is no strong coding of M 1 into 
M 2 . But there is a coding. Take any non-singular 2 ? 2-matrix with 
non-zero entries, say the matrix with columns
?1
1
?
and
?2
1
?
. Then define accordingly by
using the columns of the matrix as exponents for the letters:

h(a) =

?
p

r

?

; h(c) =

?
p2

r

?

; h(b) =

?
q

s

?

; and h(d) =

?
q2

s

?

:

An easy exercise shows that the homomorphism h : M 1 ?! M2 is a coding.


22 Volker Diekert and Yves M?etivier

3.3 Trace Codes

Codes over words are widely studied, see [5] for a comprehensive 
treatise. They play a fundamental role in computer science. There are 
well-known algorithms to test whether a finite (or regular) set X ? ?? 
is a code, i.e., whether it generates a free submonoid with basis X . In 
trace monoids the same question turns out to be undecidable.

Proposition 3.6. It is undecidable whether a finite subset X of the 
direct product fa; bg? ? fc; dg? generates a free submonoid (with basis 
X).

Proof. An instance of the Post correspondence problem (PCP) consists of 
two lists (u1; : : : ; un); (v1 : : : ; vn) with n >= 2; ui; vi 2 ?+ for 
1 <= i <= n. A special solution to this instance of the PCP is a finite 
sequence (1; i1; : : : ; ik; n) such that u1ui1 ? ? ? uikun = v1vi1 ? ? 
? vik vn. It is well-known that the existence of a special solution is 
undecidable. In order to reduce PCP to the problem above one employs 
markers. Let # be a new symbol; replace each letter a 2 ? in the words 
ui; 1 <= i <= n, by a#, and in the words vi; 1 <= i <= n, replace each 
letter a 2 ? by #a. Then, add the symbol # in front of the new word u1, 
and add # at the end of the new vn. We have now two lists of words ( 
~u1; : : : ; ~un); ( ~
v1; : : : ; ~
vn) over the new alphabet ? [ f#g. Using any coding
of (? [f#g)? into fc; dg?, we may view ~ui; ~
vi 2 fc; dg+ for 1 <= i <= n. Finally
define X = f(abi; ~ui) j 1 <= i <= ng [ f(abi; ~
vi) j 1 <= i <= ng. It is not difficult
to see that X generates a free submonoid (with basis X) of fa; bg? ? fc; 
dg? if and only if the given instance of PCP has no special solution.

Let M = M (?; I) be a trace monoid and X ? M be any subset. Define an 
independence relation IX ? X ?X by xIXy if and only if xy = yx in M . 
This yields a free partially commutative monoid M X = M (X; IX ) and the 
inclusion X ? M induces a homomorphism hX : M X ?! M . The set X is 
called a trace code, if hX is a coding.

Remark 3.3. i) If we can decide whether X ? M (?; I) is a trace code (X 
being finite), then we can decide whether X generates a free monoid, 
i.e., whether X is a code. Indeed, X is a code if and only if X is a 
trace code and IX is empty. Whether or not the converse is true remains 
unclear. ii) The question whether a finite subset X of M is a trace code 
can easily be reduced to the problem whether the intersection of two 
rational sets is empty. Define any total order < on X . For x 2 X let 
LexNF(x; X) ? X? be the rational set of lexicographic normal forms from 
M (X; IX ) having as first letter x. Let 'X : X? ?! M (X; IX ) the 
canonical homomorphism. Clearly, 'X restricted to some LexNF(x; X) is 
injective and hX('X (LexNF(x; X))) is a rational set of M (?; I). Now 
observe that X is a trace code if and only if hX('X(LexNF(x; X))) \ 
hX('X (LexNF(y; X))) = ; for all x; y 2 X , x 6= y. This finishes the 
reduction to the intersection problem.


Partial Commutation and Traces 23

This remark and the results of the next section imply the following 
fact.

Proposition 3.7. Let X ? M (?; I) be a finite set of connected traces. 
Then it is decidable whether X is a trace code.

Proof. In the terminology of the next section, LexNF(x; X) is 
star-connected by Cor. 4.3 below. Hence 'X(LexNF(x; X)) ? M (X; IX ) is 
star-connected, and since hX maps connected traces of M (X; IX ) to 
connected traces of M (?; I) (by definition of IX ), we see that hX('X 
(LexNF(x; X))) is recognizable, c.f. Thm. 4.1. There is an effective 
procedure testing the emptiness of the intersection of two recognizable 
sets.

Emptiness of the intersection of two rational sets is known to be 
decidable, if the independence alphabet is a transitive forest, [1]. 
Therefore we can state by the remark above:

Proposition 3.8. Let the independence alphabet be a transitive forest. 
Then it is decidable whether a finite set X ? M (?; I) is a trace code.

A transitive forest is the transitive closure of the descendant relation 
in a union of trees. Another characterization says that transitive 
forests are the elements of the smallest families of graphs containing 
the empty graph and being closed under disjoint union and complex 
product with a one point graph. It can be defined by forbidden 
structures, too. An independence alphabet is a transitive forest if and 
only if it does not contain neither C4 nor P4 as an induced subgraph. By 
C4 we mean the chordless cycle and by P4 the chordless path with 4 
letters.

The proof of Prop. 3.6 shows that the trace code property is undecidable 
in the monoid fa; bg? ?fc; dg?, which means that the independence 
alphabet is the graph C4. An undecidability result for P4 would have 
given a characterization theorem, but the decidability, even 
decidability in polynomial time, is known in this particular case.

Proposition 3.9. If (?; I) or (?; D) is a P4, then the trace code 
property can be decided in polynomial time.

If the trace code property can be decided for (?; I) or for (?; D), then 
it can be decided for all induced subgraphs and for all dependence 
alphabets, obtained by edge-contraction. Unfortunately, this is not 
enough to conclude that the undecidability of the trace code property 
can be characterized by some finite list of forbidden induced subgraphs. 
The classification of all independence alphabets where the (trace) code 
property is decidable is a challenge.

3.4 Bibliographical Remarks

Equations over traces have been studied first by Cori and M?etivier [19] 
and Duboc. The results of Sect. 3.1 are due to Duboc, see [40]. The 
results presented here are also exposed by Choffrut and by Duchamp and 
Krob in [34,

24 Volker Diekert and Yves M?etivier

Chapt. 3,4]. A celebrated result of Makanin states that it is decidable 
whether a system of equations with constants has a solution over words, 
[68]. The extension of the result to traces would be of great interest, 
but it has not been attacked yet.

The undecidability of the trace code property is due to Hotz and Claus 
[62] and Chrobak and Rytter [14]. This result and the proof techniques 
are close to a classical result of Greibach [57] showing that ambiguity 
of contextfree grammars is undecidable. The decidability for the 
intersection problem in case of transitive forests is from Aalbersberg 
and Hoogeboom [1]. It led directly to Prop. 3.8. After that result the 
characterization of dependence graphs where the trace code property is 
decidable concentrated on the graph P4. Hoogeboom and Muscholl [61] 
proved the positive result Prop. 3.9 for the code property (being 
therefore negative for completing the picture). It has been 
independently observed by Matiyasevich, who also proposed the notion of 
trace code. Matiyasevich announced another decidability result for the 
code-property provided the independence relation is acyclic (personal 
communication). The topic of free trace submonoids is also mentioned in 
the chapter by Choffrut of [34].

The question whether the existence of codings (injective homomorphisms) 
between trace monoids can be decided has been raised by Ochma?nski in 
[81], where among others a variant of Prop. 3.5 is stated. The notion of 
a strong coding has been defined by Bruy?ere et al. in [12]. Thm. 3.1 is 
the main result of [33]. It answers a question of the former paper and 
solves the problem above for strong codings. However, the decidability 
for codings is still open, some partial results and conjectures are in 
[11, 33].

4. Recognizable Trace Languages

4.1 Basic Facts about Recognizable and Rational Sets

Let M be a monoid with the unit element 1, a subset T of M is said to be 
recognizable if there exists a homomorphism ? from M to a finite monoid 
S such that T = ??1(F ) for some subset F ? S. We also say that the 
homomorphism ? recognizes T .

For a monoid M , an M?automaton A = (M; Q; ffi; q0; F ) consists of a 
finite set Q of states, an initial state q0 2 Q, a subset F ? Q of final 
states, and a transition function ffi from Q?M to Q satisfying the 
following conditions:

8q 2 Q ffi(q; 1) = q;

8q 2 Q; 8m1; m2 2 M ffi(q; m1m2) = ffi(ffi(q; m1); m2):

The subset T of M recognized by the automaton A is defined by

T = fm 2 M j ffi(q0; m) 2 Fg:


Partial Commutation and Traces 25

Let T ? M be any subset. The syntactic congruence ?T ? M ? M is defined 
by setting x ?T y if for all u; v 2 M we have uxv 2 T () uyv 2 T . The 
quotient monoid M=?T is called the syntactic monoid of T . The canonical 
homomorphism M ! M=?T recognizes T . If ' : ?? ! M is a surjective 
homomorphism, then the syntactic monoids of T ? M and of '?1(T ) ? ?? 
are isomorphic (via '). We have a classical result:

Proposition 4.1. Let ' : ?? ! M be a surjective homomorphism onto a 
monoid M and T ? M . Then the following assertions are equivalent.

i) The set T is recognizable.
ii) The syntactic congruence ?T is of finite index.
iii) There exists an M-automaton recognizing T .
iv) The set '?1(T ) is a recognizable (or regular) subset of ??.

The family of recognizable sets is denoted by Rec(M ). It is a Boolean 
algebra. The family of rational sets, denoted by Rat(M ), is inductively 
defined by starting from the finite subsets of M and the closure under 
the operations of union X [ Y , concatenation X ? Y = fxy 2 M j x 2 X; Y 
2 Y g, and iteration (or Kleene-star) X? = S
i>=0 X i, where X0 = f1g and X i = X(i?1) ? X
for i >= 1.
If we replace the iteration-operation by complementation, we obtain the 
family of star-free sets, denoted by SF(M ).

For finitely generated free monoids Kleene's Theorem asserts Rec(??) = 
Rat(??); and we can speak of regular languages without ambiguity. Due to 
Schützenberger, the star-free languages SF(??) have been characterized 
by the fact that they are recognized by some finite aperiodic monoid. (A 
finite monoid S is aperiodic if and only if there exists some p >= 0 
such that xp+1 = xp for all x 2 S.) For example, the language (ab)? ? 
fa; bg? is starfree (!), the language (aa)? ? fag? is not star-free. The 
commutative closure of the star-free language (ab)? is the non-regular, 
context-free language fw 2 fa; bg? j jwja = jwjbg.

The rational subsets of the free commutative monoid N? are exactly the 
semi-linear sets. There are semi-linear sets, which are not 
recognizable: Consider (ab)? ? Nfa;bg .

Star-free trace languages are recognizable by Cor. 4.1 below. For a 
trace monoid M = M (?; I) we therefore have the following situation with 
strict inclusions, in general:

SF(M ) ? Rec(M ) ? Rat(M ):

4.2 Recognizability and Rational Operations

A rational expression over words or traces is called star-connected , if 
the Kleene-star is used over connected languages, only. Let X ? ?? (X ? 
M (?; I), resp.) be a languages. A word t (trace t, resp.) is called an 
iterative factor of X , if ut?v ? X for some u; v.

26 Volker Diekert and Yves M?etivier

Remark 4.1. If all iterative factors of X are connected, then every 
rational expression for X is star-connected. Indeed, if the star is used 
over some word or trace t inside the expression for some rational 
language L, then t becomes an iterative factor of L.

Another operation for trace languages is called concurrent-star (or 
c-star for short). It is in fact the composition of two operations. For 
a language X we define Xc?? to be the Kleene-star (c(X))?, where c(X) is 
the set of connected components:

c(X) = fu 2 M (?; I) j u is connected; u 6= 1 and 9v : uv 2 X; uIvg:

Thus, Xc?? is the Kleene-star over the connected language of all 
connected components.

The family of c-rational trace languages is defined as the rational 
sets, but instead of the Kleene-star we allow the c-star operation, 
only. The following assertion is Ochma?nski's Theorem.

Theorem 4.1. Let ' : ?? ! M (?; I) be the canonical homomorphism and T ? 
M (?; I) be a trace language. Then the following assertions are 
equivalent.

i) T is recognizable.
ii) There exist a rational language X ? ?? such that every iterative 
factor of X is connected and '(X) = T .
iii) T is star-connected.
iv) T is a c-rational language.

Proof. The implication i) ) ii) follows from Lem. 4.1 below. ii) ) iii): 
As we have remarked above, if every iterative factor is connected, then 
X is star-connected.
iii) ) iv): Every star-connected expression is also a c-rational 
expression. iv) ) i): It remains to show that recognizable trace 
languages are closed under taking connected components, concatenation, 
and the Kleene-star over connected languages. The closure under taking 
connected components is trivial. The closure under concatenation is 
stated in Cor. 4.1, and the closure under Kleene-star over connected 
languages is stated in Cor. 4.2. In order to establish these results we 
shall use below the notion of rank as a tool.

Remark 4.2. In Thm. 6.1 we will see that, in addition to the 
equivalences above and just as for words, recognizable trace languages 
can also be characterized by monadic second-order logic.

4.3 The Rank

The rank is defined with respect to a fixed independence relation I ? 
???. Let X ? ?? be a subset of words and x; y 2 ??. By Cor. 2.3 we have 
xy 2 X

Partial Commutation and Traces 27

if and only if there are x0; y0; : : : ; xn; yn 2 ?? such that x0y0 ? ? 
? xnyn 2 X , [x] = [x0 ? ? ? xn], [y] = [y0 ? ? ? yn], and xiI(yi+1 ? ? 
? yn) for 0 <= i < n. For xy 2 X we define Rank(x; y; X) to be the least 
number n such that a factorization as above is possible. The rank of the 
language X is

Rank(X) = maxfRank(x; y; X) j xy 2 Xg

(with the convention Rank(;) = 0).
We say that X has a finite rank, if there exists an integer k such that 
Rank(X) = k.

For example, if we assume that aIb then, considering the set of couples 
f(an; bn) j n >= 0g, we see that Rank((ab)?) is infinite. The rank of 
a?b? is one.

Remark 4.3. A subset X of ?? has a rank equal to 0, if and only if for 
all couples (x; y) of words such that xy 2 X, there exist two words x0; 
y0 such that x0y0 2 X , x ? x0, and y ? y0, where ? is a shorthand of ?I 
.

Theorem 4.2. If a regular subset X of ?? has a finite rank, then [X ] is 
recognizable.

Proof. Let T = [X ]; we prove that the family fu?1T j u 2 M (?; I)g is 
finite. Let k be the rank of X: Let ? be a morphism from ?? to a finite 
monoid S recognizing X (i.e., X = ??1(?(X))) such that in addition

?(u) = ?(v) implies alph(u) = alph(v):

Clearly such an ? exists. Define a finite set R(u) for u 2 M (?; I) as 
follows

R(u) = f(s0; : : : ; sk) j u = [x0 ? ? ? xk]; si = ?(xi); xi 2 ??; 0 <= 
i <= kg:

Note that the number of different R(u) is bounded by 2jSj(k+1) : We 
prove that
if R(u) = R(u0), then u?1T = u0?1T : For this assume that R(u) = R(u0) 
and uv 2 T . We prove that u0v 2 T : Let x; y 2 ?? be words such that 
[x] = u; [y] = v; the set X has a finite rank equal to k and xy 2 X . 
Thus, for some xi, yi, 0 <= i <= k we have

x ? x0x1 ? ? ? xk;
y ? y0y1 ? ? ? yk;
x0y0x1y1 ? ? ? xkyk 2 X;
xjIyi for all i < j:

As the morphism ? recognizes X;

??1(?(x0y0x1y1 ? ? ? xkyk)) ? X:

Let ff = ??1(?(x0y0x1y1 ? ? ? xkyk)). Since xjIyi for all i < j we can 
deduce

ff = ??1(?(x0x1 ? ? ? xky0y1 ? ? ? yk))

= ??1(?(x0)?(x1) ? ? ? ?(xk)?(y0y1 ? ? ? yk)):


28 Volker Diekert and Yves M?etivier

Let x0 2 ?? such that [x0] = u0 and x0 admits x0
1; : : : ; x0
k as a decomposition
verifying ?(x0
0) = ?(x0); : : : ; ?(x0
k) = ?(xk). This is possible due to R(u) =
R(u0): Now

??1(?(x0
0)?(x0
1) ? ? ? ?(x0
k)?(y0y1 ? ? ? yk)) = ??1(?(x0x1 ? ? ? xky0y1 ? ? ? yk)):

Using the fact that ? is compatible with alphabets we obtain

ff = ??1(?(x0
0y0x0
1y1 ? ? ? x0
kyk)):

Finally, since ff ? X we have x0
0y0x0
1y1 ? ? ? x0
kyk 2 X and thus u0v 2 T :

Remark 4.4. Let us note that the converse of this theorem is false. For 
? = fa; bg with aIb, the closure of the set of words X = (ab)? ? (a? [ 
b?) is recognizable, since X = fa; bg?, but the rank of X is not finite.

Proposition 4.2. Given two sets of words X1 and X2, if they are closed, 
then the rank of the concatenated language X1X2 is at most 1.

Proof. Let xy 2 X1X2; by definition we have xy ? x1x2 with x1 2 X1 and 
x2 2 X2: Applying Levi's Lemma there exist x0
1; x0
2; x00
1 ; x00
2 2 ?? such that

x ? x0
1x00
1 ; y ? x0
2x00
2 ; x1 ? x0
1x0
2; x2 ? x00
1 x00
2 and x00
1 Ix0
2:

As X1 and X2 are closed we have x0
1x0
2 2 X1 and x00
1 x00
2 2 X2. Thus
x0
1x0
2x00
1 x00
2 2 X1X2 and the rank of X1X2 is at most 1.

Corollary 4.1. The family of recognizable trace languages is closed 
under concatenation.

Proposition 4.3. Let X be a set of connected words. If it is closed, 
then the rank of X? is finite.

Proof. We show that the rank of X? is bounded by 2j?j. Let xy 2 X?. By 
Cor. 2.3 we may write:

x ? p1 ? ? ? pn;
y ? q1 ? ? ? qn;
qiI(pi+1 ? ? ? pn) for 1 <= i < n;
(piqi) 2 X for 1 <= i <= n:

Consider an index i such that pi 6= 1 6= qi. Since piqi is connected, 
there exist letters ai 2 alph(pi) and bi 2 alph(qi) such that (ai; bi) 2 
D but biI(pi+1 ? ? ? pn). It follows that the letters bi are pairwise 
distinct. Hence there are at most j?j indices such that pi 6= 1 6= qi. 
Next we group the factors with index i where pi = 1 or qi = 1 into 
blocks. Note that every block belongs to X?. Therefore, for some k <= 
j?j we can rewrite x and y as follows.

Partial Commutation and Traces 29

x ? r0p1r1 ? ? ? pkrk;
y ? s0q1s1 ? ? ? qksk;
siI(pi+1ri+1 ? ? ? pkrk) for 1 <= i < n;
qiI(ri+1 ? ? ? pkrk) for 1 <= i < n;
ri; si 2 X? for 0 <= i <= n;
(piqi) 2 X for 1 <= i <= n:

We obtain the claim about the rank by r0s0(p1q1)r1s1 ? ? ? (pkqk)rksk 2 
X?.

By Thm. 4.2 and Prop. 4.3 we obtain the following missing piece of in 
the proof of the implication Thm. 4.1, iv) ) i).

Corollary 4.2. Let T be a recognizable trace language which is 
connected, then T ? is recognizable.

4.4 Recognizability and the Lexicographic Normal Form

Consider a total order on the alphabet and the set of lexicographic 
normal forms of traces LexNF. Recall that if T ? M (?; I) is 
recognizable and if '?1(T ) denotes the set of representing words, then 
X = '?1(T ) \ LexNF is a recognizable word language with T = [X ].

Lemma 4.1. Let X ? LexNF be a regular language. Then every iterative 
factor of X is connected. In particular, [X ] ? M (?; I) is a 
recognizable trace language.

Proof. We show a stronger assertion: Let w 2 LexNF such that w2 2 LexNF 
(this condition holds for every iterative factor of X), then w is a 
connected word.

Let t = [w] 2 M (?; I) and assume by contradiction that t is not 
connected, i.e., t = uv with u 6= 1, v 6= 1, and uIv. Then, assuming the 
first letter from w being from u, we can factorize w such that

w = a1x1a2x2a3x3a4x4 ? ? ? an?1xn?1anxn;

u = a1x1a3x3 ? ? ? akxk ;

v = a2x2a4x4 ? ? ? amxm

with ai 2 ?, xi 2 ??, fk; mg = fn?1;ng, and m = n, if n is even and k = 
n otherwise. Moreover, due to uIv we have a1 < ? ? ? < an.

Since w2 2 LexNF, all factors of w2 belong to LexNF, too. Hence, if n is 
even, then amxma1 2 LexNF. If n is odd, then n >= 3 and akxka1x1a2 2 
LexNF. In the first case, we have a1 < am and (amxm)Ia1; in the second 
case, we have a2 < ak and (akxka1x1)Ia2. Hence, a contradiction follows 
in both cases.

Note that Lem. 4.1 implies i) ) ii) of Thm. 4.1. The following statement 
is a corollary. It is also a consequence of Thm. 6.1 below which will be 
shown below without using results from this section.


30 Volker Diekert and Yves M?etivier

Corollary 4.3. For a trace language T ? M (?; I) let Min(T ) = fx 2 
LexNF j [x] 2 Tg. Then T is a recognizable trace language if and only if 
Min(T ) ? ?? is regular.

4.5 The Star Problem and the Finite Power Property

The star problem is to decide for a given recognizable trace language T 
? M (?; I) whether T ? is recognizable. It is not known whether the star 
problem is decidable. There is a close connection to the finite power 
property (FPP).

A language T ? M (?; I) is said to satisfy FPP, if T ? = (T [ f1g)k for 
some k >= 0. We say that FPP is decidable on M (?; I), if FPP for 
recognizable languages of M (?; I) is decidable.

If a recognizable language T satisfies FPP, then T ? is recognizable, 
too. The converse need not be true, e.g., let ; 6= ? ? ?. Then ? ? ? M 
(?; I) is recognizable, it is even star-free, but ? does not satisfy 
FPP.

Theorem 4.3 ([87]). If the independence alphabet (?; I) does not contain 
any C4 (cycle of four letters) as an induced subgraph, then both, the 
star problem and the finite power problem are decidable.

Remark 4.5. Thm. 4.3 applies to free commutative monoids. Note however 
that for commutative monoids the star problem and FPP are questions 
about semi-linear sets (or equivalently questions which can be 
formulated in Presburger arithmetic), hence the decidability is also 
clear from classical results, [43, 55].

Both, the star problem and FPP are semi-decidable. For FPP this is 
clear, simply compute T k until T k ? T k?1, k >= 1. For the star 
problem, the existence of a semi-algorithm to this problem is a 
consequence of the following fact:

Proposition 4.4. Let T ? M (?; I) be a recognizable trace language. Then 
T ? is recognizable if and only if there exists a recognizable language 
K ? M (?; I) n f1g such that both K2 ? K and (K n K2) ? (T n f1g) ? K. 
Moreover, if such a K exists, then K = T ? n f1g, and K n K2 is the 
minimal set of generators for T ?.

A semi-algorithm to decide the star problem computes all K, patiently, 
one after the other, testing each time the three inclusions K2 ? K and 
(K n K2) ? (T n f1g) ? K.

Let X ? ??. If X possesses the finite power property in ??, then [X ] 
possesses the finite power property in M (?; I). This implication may 
not be reversed, in general:

Example 4.1. Let ? = fa; bg, aIb, and X = (a2)? + (b2)? + ab + ba. This 
set does not possess the finite power property, since for all integer n, 
the word (ab)n belongs to Xn but not to X i for all i < n. Nevertheless, 
the subset [X ] of M (?; I) verifies [X ]? = [X ]3.


Partial Commutation and Traces 31

The basic relation between the star problem and FPP is due to the 
following proposition:

Proposition 4.5. Let T ? M (?; I) be recognizable and let b be a new 
letter. Define K = T ?b+ ? M (?; I)?b? . Then the following assertions 
are equivalent

i) T satisfies the finite power property.
ii) K satisfies the finite power property.
iii) K? is recognizable.

Proof. Without restriction we have 1 2 T . Clearly, if T ? = T k for 
some k >= 0, then we have Kk+1 = Kk. This proves i) ) ii) ) iii).
For the converse observe that if xbk 2 K? with x 2 M (?; I), k >= 1, 
then we must have x 2 T k0
for some k0 <= k. (In fact x 2 T k, since 1 2 T .) Now assume
that K? is recognizable. By the pumping lemma for regular languages 
(uvw- Theorem) there exists some n >= 0 such that whenever xbm 2 K? we 
find some k <= n with xbk 2 K?. As we have just seen this implies x 2 T 
k ? Tn, and hence T ? ? Tn.

As a final result of this section, let us show that FPP is decidable for 
connected languages. For this we recall the notion of distance function 
on automata. A path in the automaton A is a sequence C = (f1; : : : ; 
fn) of consecutive transitions fi = (qi; ai; qi+1), 1 <= i <= n. The 
integer n is called the length of the path C. The word w = a1 ? ? ? an 
is the label of C. The state q1 is the origin of the path and the state 
qn+1 its end. By convention, there is for each state q 2 Q a path of 
length 0 from q to q. Its label is the empty word 1: A path C from q to 
q0 is successful if q is an initial state, q0 is final, i.e., q 2 Q0 and 
q0 2 F . The set recognized by A, denoted by L(A) is defined as the set 
of labels of successful paths.
A distance automaton (A; d) is a pair where A = (?; Q; ?; Q0; F ) is a 
non-deterministic automaton and d is a distance function

d : Q? (? [ f1g) ?Q ?! f0; 1; 1g

satisfying for all (q; a; q0) 2 Q? (? [ f1g) ?Q the property d(q; a; q0) 
= 1 if and only if (q; a; q0) 62 ?.

For a path C, we note d(C) =
n
X

i=1
d(qi; ai; qi+1). The function d is extended

on Q??? ?Q by : d(q; w; q0) being the minimum of the d(C) over all paths 
C from q to q0 labeled by w. If there does not exist such a path, we set 
d(q; w; q0) = 1.

A distance automaton (A; d)) is called limited in distance, if there 
exists an integer k such that for all w 2 L(A) we have d(q; w; q0) <= k 
for some q 2 Q0 and q0 2 F .
The following result of Hashiguchi [59] will be used.

Theorem 4.4. It is decidable whether a finite distance automaton (A; d) 
is limited in distance.


32 Volker Diekert and Yves M?etivier

As in the word case this theorem can be used for the following 
assertion.

Theorem 4.5. Let T be a recognizable subset of M (?; I) such that each 
trace of T is connected. Then it is decidable whether T possesses the 
finite power property.

Proof. From Corollary 4.2 we know that T ? is recognizable. We describe 
a finite distance automaton recognizing T ? and having limited distance 
if and only if T ? has the finite power property.

To simplify notations we use a finite monoid S recognizing at the same 
time T and T ?; and where moreover the elements of S code the alphabet. 
Thus, we let ? be a homomorphism from M (?; I) onto S such that

{ T = ??1(?(T ));
{ T ? = ??1(?(T ?));
{ and ?(u) = ?(v) implies alph(u) = alph(v):

Note that ?(T ? n f1g) = ?(T ?) n f1g due to the assumptions above. We 
now give the description of the automaton. The states are tuples of 
various length (s0; s1; : : : ; s2m) 2 S2m+1 with m <= n, where n = j?j: 
Furthermore we have si 2 ?(T ?), if i is even. The si, where i is odd, 
are called active elements. There is a single initial state (1) where 1 
2 S denotes the unit element. There are two sorts of ffl?transitions.

{ The first one has distance zero and is always allowed if m < n: For 
any 0 <= i <= 2m we may perform the following operation

change (s0; : : : ; si; si+1; : : : ; s2m) to (s0; : : : ; si; 1; 1; 
si+1; : : : ; s2m):

This transition creates a new active component.
{ The other ffl?transition has distance one; it decides that an active 
component is not used anymore, since a factor is completed. For si 2 ?(T 
); i odd, we may perform with distance one:

change (s0; : : : ; si?1; si; si+1; : : : ; s2m) to (s0; : : : ; si?1 ? 
si ? si+1; : : : ; s2m)

Thus, with distance one a (2m + 1)-tuple is transformed into a (2m ? 1)- 
tuple. Now we describe the action of a letter. Let a 2 ?; there are two 
types of transitions. If i is odd and a is independent of the alphabets 
corresponding to sj where i < j, then we may perform:

reading a change (s0; : : : ; si; : : : ; s2m) to (s0; : : : ; si ? 
?(a); : : : ; s2m):

This transition has distance zero.

For i even, we allow the same transformation, if a is independent of the 
alphabet corresponding to sj where i < j and if, in addition, ?(a) 2 ?(T 
): In this case the transition has distance one.
The final states are the 1-tuples (s0) with s0 2 ?(T ?).


Partial Commutation and Traces 33

To see the correctness of this construction, observe first that when 
there is a path with label t from the initial to a final state with 
distance k then t 2 T k: Conversely, we have to prove that if t 2 T k 
then there is a path with distance k labeled with t starting at (1) and 
ending in some (s0) with s0 2 ?(T ?):

Let t = uv 2 T k, we can write u = u1 ? ? ? uk; v = v1 ? ? ? vk such 
that uivi 2 T , uivi 6= 1, and viIuj for all i < j: We call the index i 
active when ui 6= 1 and vi 6= 1: At most n indices can be active, since 
T is a connected language. Hence, if m is the number of active indices, 
we have m <= n: Let d = jfvi j vi = 1gj. The set fvi j vi = 1g contains 
the factors which are completed. We group the corresponding neighboring 
ui together into one factor, including those ui where ui = 1; and we 
rename them as ui with i even. We rewrite u = u0u1 ? ? ? u2m such that 
u1; u3; u5; : : : agree with the active ui from the old factorization. 
It follows that the ui, i even, are products such that ?(ui) 2 ?(T ?): 
Now, using an induction on juj one proves that reading u we may reach 
the state (?(u0); ?(u1); : : : ; ?(u2m)) with distance d: At the end of 
this procedure there are no active components anymore, hence m = 0, d = 
k. The result follows.

4.6 An Algorithm to Compute Closures

Let (?; I) be an independence alphabet. Given two words x and y of ??, 
the I-shuffle of x and y, denoted by xXIy, is the set of words of the 
form x1y1 ? ? ? xnyn with x = x1 ? ? ? xn, y = y1 ? ? ? yn , xi; yi 2 ?? 
for all 1 <= i <= n, and xjIyi for all 1 <= i < j <= n. The inclusion 
xXIy ? fx ? yg is straightforward. The I-shuffle is extended to sets by

XXIY =
[
fxXIy j x 2 X; y 2 Y g:

Remark 4.6. The standard shuffle operation X on words can not be 
expressed with the I-shuffle. We have bab 2 abXb, but never bab 2 abXIb, 
since (b; b) =
2 I . On the other hand:

xXy = xXIy for all xIy:

We will apply the I-shuffle mainly to closed languages. Then the 
I-shuffle becomes more powerful.

Lemma 4.2. For all x; y 2 ?? we have x ? y = xXIy:

We are now ready to define the procedure P . This procedure adds to X 
the words belonging to the sets:

z0(x1XIy1)z1 ? ? ? zn?1(xnXIyn)zn

where z0x1y1z1 ? ? ? zn?1xnynzn 2 X;xi; yi 2 ?+; z0; zi 2 ?? for all 1 
<= i <= n; n >= 0.


34 Volker Diekert and Yves M?etivier

There is no need to emphasize the factors zi explicitly. Observing that 
fzig = ziXI1 and allowing the factors xi (and/or yi) to be the empty 
word we obtain a more compact notation. Formally, let x be an element of 
??, then we define:

P (x) = fy 2 ? j y 2 (x1XIy1) ? ? ? (xnXIyn)
x = x1y1 ? ? ? xnyn; xi; yi 2 ??; 1 <= i <= n g:

The definition of P is extended in a natural way to a set X of words by

P (X) =
[

x2X
P (x):

For example, let a and b be two letters such that aIb. We have

P (a?b) = a?ba?;

P (fababg) = fabab; baab; abba; aabb; babag;

P 2(fababg) = P (fababg) [ fbbaag = fababg:

Due to the definition of P , for every set of words X we have P (X)[P (Y 
) = P (X [ Y ); P (X) ? P (Y ) ? P (X ? Y ); and (P (X))? ? P (X?): If X 
= X?, then we have P (X) = (P (X))?.

Moreover, we have X ? P (X) ? X, and X = P (X) if and only if X = X. 
Note also that for any word x = a1 ? ? ? anan+1, the n-fold application 
Pn computes the closure of x:

[x] = P (a1 ? P (? ? ? P (anan+1) ? ? ?)) ? Pn(x):

(The exponent n is an overestimation, Cor. 4.4 below yields that a dlog 
nefold application is enough in order to compute the closure of a word 
of length n.) We have

X =
[

i>=0
P i(X) = P ?(X):

Remark 4.7. The procedure P is a modification of the procedure S 
introduced by M?etivier [74] The procedure S adds to X the words 
belonging to the sets:
(x1Xy1) ? ? ? (xnXyn);

where x1y1 ? ? ? xnyn 2 X and for all i we have alph(xi) ? alph(yi) ? I 
. The relation between both procedures is as follows:

X ? S(X) ? P (X) ? Sj?j(X) ? P j?j(X) ? X:

Theorem 4.6. If X is recognizable, then P (X) is recognizable.

Partial Commutation and Traces 35

Proof. Let ? : ?? ?! S be a homomorphism onto a finite monoid S 
recognizing X , i.e., X = ??1(?(X)). As usual, we may assume that ?(x) = 
?(y) implies alph(x) = alph(y) for all x; y 2 ??. Thus, for p 2 S we 
define by alph(p) = alph(x) where p = ?(x). Define the state set Q = S ? 
S. We allow ffl-transitions and two types of a-transitions, a 2 ?.

ffi((p; q); 1) = (pq; 1) for all (p; q) 2 Q;
ffi((p; q); a) = (p; q?(a)) for all (p; q) 2 Q; a 2 ?;
ffi((p; q); a) = (p?(a); q) for all (p; q) 2 Q; a 2 ?; alph(q) ? fag ? I 
:

The initial state is (1; 1) and the final states are the pairs (p; 1) 
with p 2 ?(X). It is not difficult to see that the automaton just 
defined recognizes P (X).

The following example is due to Arnold. It shows that every finite 
iteration of P may fail to compute the closure of a recognizable set 
even when its closure is recognizable:

Example 4.2. Let ? = fa; bg with aIb, and X = (ab)?(f1g [ a+ [ b+). We

have X = ??, and by induction, we can prove that a3n+1
b3n+1
62 Pn(X) for
all n >= 0. Thus, for each integer n we have Pn(X) 6= X.

Remark 4.8. This behavior above is not a particular failure of the 
procedure P . In fact, let for a moment ~
P : P(??) ?! P(??) be any procedure satisfying
the following properties:

I ~
P (X [ Y ) = ~
P (X) [ ~
P (Y ),
II X ? ~
P (X) ? X,
III If X is recognizable, then ~
P (X) is recognizable.

Then possibly ~
Pn(X) 6= X for all n, even when X and X are recognizable. Indeed, assume 
that for ? = fa; bg with aIb we would have

~
Pn((ab)?(f1g [ a+ [ b+)) = ?? for some n 2 N:

Then ~
Pn((ab)?) [ ~
Pn((ab)?(a+ [ b+)) = ?? due to I. By II we obtain
~
Pn((ab)?) = fw 2 ? j jwja = jwjbg: Finally the latter set would be 
recognizable by III, hence a contradiction.

We deduce from the previous remark that neither P nor any other 
procedure satisfying I, II, and III provides us with a semi-algorithm to 
compute the I-closure on the class of recognizable languages. However, 
the following results show that we can use the procedure P to compute 
closures in the cases described in previous sections.

Proposition 4.6. Let (?; I) be an independence alphabet. For all 
I-closed subsets X1; X2 of ??, we have:

X1 ? X2 = P (X1 ? X2):

Proof. This follows from Lem. 4.2.


36 Volker Diekert and Yves M?etivier

Corollary 4.4. Let (?; I) be an independence alphabet and X1; : : : ; Xn 
be I-closed subsets of ??. Then we have:

X1 ? ? ? Xn = P dlog ne(X1 ? ? ? Xn):

Theorem 4.7. Let (?; I) be an independence alphabet and !(?; I) be the 
maximal number of pairwise independent letters. Let X be any I-closed 
subset of ?? containing connected words, only. Then we have:

X? = P 2j?j!(?;I)(X?):

Proof. Let w1; : : : ; wm 2 X n f1g be a list of m non-empty words, and 
w 2 ?? such that w 2 [w1 ? ? ? wm]. Each wi can be identified with a 
(scattered) subword ^
wi of w. More precisely, let n = jwj and w = a(1) ? ? ? a(n) with a(j) 2 
?. We say that a position j with a = a(j), 1 <= j <= n belongs to ^ wi, 
if

jw1 ? ? ? wi?1ja < ja(1) ? ? ? a(j)ja <= jw1 ? ? ? wi?1wija:

For each wi let first(i) (last(i) resp.) be the first (last resp.) 
position belonging to ^
wi. This yields an interval

int(i) = [first(i); last(i)] ? f1; : : : ; ng:

The crucial observation is due to the fact that all words of X are 
connected. As it can be seen from the proof of Prop. 4.3 (or be shown 
directly) there is no position j where more than j?j intervals 
intersect:

jfi j j 2 int(i)gj <= j?j for all 1 <= j <= n:

We now use at most j?j values blue, green, red, etc. in order to give a 
first coloring of w. We demand that positions belonging to the same ^ wi 
have
the same color and in addition that the colors of ^
wi and ^
wj are different if
int(i) \ int(j) 6= ; for all i 6= j. We need in fact a finer coloring 
(or a second coloring). To define this consider a certain color, say red 
. Let ^ wi1 ; : : : ; ^
wir ,
1 <= i1 <= ? ? ? <= ir <= n be the list of red subwords. We define a 
graph G(red) = (V (red); E(red)) with vertex set V (red) = f1; : : : ; 
rg and pq 2 E(red) if and only if p < q but first(ip) > last(iq). Since 
the intervals of the red subwords do not intersect, G(red) is a 
permutation graph. Hence it is a perfect graph and its chromatic number 
is equal to the cardinality of its largest clique. A clique in G(red) 
however corresponds to pairwise independent subwords. This is clear, 
since pq 2 E(red) implies alph( ^
wip) ? alph( ^
wiq ) ? I . Therefore at
most !(?; I) different shades of red suffice such that p and q have 
different colors for all pq 2 E(red). In total we need at most j?j!(?; 
I) colors such that the following invariant is satisfied:

Whenever i 6= j and int(i) \ int(j) 6= ; or i < j and first(i) > 
last(j); then i and j have different colors.


Partial Commutation and Traces 37

Finally, we mark a color, if all subwords having this color are factors 
of w, i.e., for all subwords ^
wi of a marked color it holds jint(i)j = jwij. Now let
k be the number of unmarked colors, k <= j?j!(?; I).
Since X is I-closed and we are interested in X? ; it is enough to prove 
by induction on k that for some permutation ö of f1; : : : ; mg we have

w 2 P 2k( ^
wö(1) ? ? ? ^
wö(m)):

If all colors are marked, i.e., k = 0, then we have w = ^ wö(1) ? ? ? ^
wö(m) and
the claim is true. Let k > 0. Since X is I-closed we may henceforth 
assume that wi = ^
wi for all i. We define a new word w0 by grouping the subwords with 
color k into factors. Assume that color k is purple (viewed as a shade 
of red). Then formally, let wi1 ; : : : ; wip be the list of all purple 
subwords in w, listed from left to right as they appear in w. Write w = 
u1 ? ? ? up such that each uq contains exactly one purple subword wiq ; 
1 <= p and such that the first letter of each u2; : : : ; up is purple 
too. Let u0
q (u00
q , resp.) denote the
scattered subword of uq containing the positions belonging to w1; : : : 
; wiq?1 (wiq+1; : : : ; wm, resp.). Then uq 2 [u0
qwiq u00
q ] and more precisely

uq 2 (u0
qXIwiq )XIu00
q :

Next, we define
w0 = (u0
1wi1u00
1) ? ? ? (u0
pwipu00
p):

Clearly, w 2 P 2(w0). Moreover, w0 2 [w1 ? ? ? wm] and the same coloring 
being inherited from w satisfies the invariant above. (This is the main 
point of the proof. It is not totally obvious since in w0 there may be 
new intersections of intervals.) Now the color k (= purple) can be 
marked. Hence, by induction w0 2 P 2(k?1)(wö(1) ? ? ? wö(m)) for some 
permutation ö. The result follows from

w 2 P 2(P 2(k?1)(wö(1) ? ? ? wö(m))) ? P 2j?j!(?;I)(wö(1) ? ? ? wö(m))):

Corollary 4.5. Let X be a recognizable set of words such that all its 
iterative factors are connected or, more general, let X be 
star-connected. Then there exists an integer n such that Pn(X) = X.

Proof. This can be seen by structural induction over the star-connected 
expression for X using Cor. 4.4 and Thm. 4.7.

Corollary 4.6. Let M (?; I) be a trace monoid. There exists an integer n 
such that for each subset X of ?? containing Min([X]) we have Pn(X) = X.

Proof. By Lem. 4.1 all iterative factors of the set of lexicographic 
normal forms LexNF are connected. By Cor. 4.5 there is an integer n such 
that Pn(Min([x])) = x for all x 2 ??. Hence Pn(X) = X , if Min([X]) ? X 
.

The hypothesis Min([X]) ? X is not always necessary.


38 Volker Diekert and Yves M?etivier

Example 4.3. Let ? = fa; bg with aIb and a < b. Let X = b+a+. Then

X = P (X) = b+XIa+ = ?? n (a? [ b?)

is recognizable. But Min(X) = a+b+ (and hence Min(X) \ X = ;).

4.7 Bibliographical Remarks

The investigation of recognizable subsets is central in the theory of 
traces. The closure under concatenation has been shown by Fliess [46], a 
much simpler proof for this result has been given by Cori and Perrin 
[21]. The recognizability of star-connected languages, Cor. 4.3, has 
been independently proved by Clerbout (for semi-commutations) [15], 
M?etivier [72], and by Ochma?nski [80]. The notion of iterative factor 
is from [71]. The notion of rank has been introduced by Hashiguchi [60] 
thereby allowing to shorten some proofs. The closure properties can also 
be deduced from logic, see [34, Chapt. 10] for details. Lem. 4.1 is from 
[80]; for a generalization to concurrency monoids see [36]. A 
straightforward proof of Cor. 4.3 by monadic second order logic (without 
involving c-rational operations) has been independently given by 
Courcelle [22].
The relation between the star problem and FPP in Sect. 4.5 is due to 
Richomme [87]. Preliminary results are shown in [49].

The procedure P has been defined first in a technical report being the 
basis of [76] where the results are shown with respect to the procedure 
S. This procedure is originally from the thesis [74], see also [25, 
Problem 246]. Thm. 4.7 is a positive answer to this problem and Cor. 4.6 
leads to another proof for showing that star-connected languages are 
recognizable.

5. Rational Trace Languages

This section contains some characterization- and decidability results 
about rational trace languages known in the literature. Due to the lack 
of space we deal with some few topics, only. In particular we do not 
speak about any counting techniques.

5.1 Unambiguous Languages

Definition 5.1. A trace language T ? M (?; I) is called k-sequential, k 
>= 1, if there is a regular word language L ? ?? such that '(L) = T and 
j'?1(t)\Lj <= k for all t 2 T . The family of k-sequential languages is 
denoted by Ratk(M ).


Partial Commutation and Traces 39

It is clear from Cor. 4.3 that every recognizable trace language is 1- 
sequential. The inclusion Ratk(M ) ? Rat(M ) is trivial for all k >= 1. 
It has been shown by Bertoni, Mauri, and Sabadini [6] that the following 
inclusions are proper for some independence alphabets:

Rec(M ) ? Rat1(M ) ? Rat2(M ) ? ? ? ? ?
[

k>=1
Ratk(M ) ? Rat(M ):

Example 5.1. Let (a; b) 2 I , then (ab)? ? M (?; I) is 1-sequential but 
not recognizable.

Example 5.2. Let (?; I) = a?b?c. Then the language T = (ab)?c? [a?(bc)? 
is 2-sequential but not 1-sequential. Clearly, T is 2-sequential. We 
sketch the proof for the fact that T is not 1-sequential. Assume by 
contradiction that there exists a regular language L ? fa; b; cg? such 
that '(L) = T and j'?1(t) \ Lj = 1 for all t 2 T . Consider a 
deterministic finite automaton accepting L. Replace all b-transitions by 
ffl-transitions. In this way we obtain an automaton A accepting a?c?. 
(Note that this automaton has no ffl-loops on accepting paths.) By the 
property of L there exists for amcm, m >= 0 exactly one accepting path 
in A, for amcn, m 6= n there are exactly two. Based upon a product 
automaton construction for A one can show that the following language is 
regular:

fw 2 a?c? j there exists more than one path of A accepting w g

We obtain a contradiction since famcn j n 6= mg is not regular.

Definition 5.2. The unambiguous rational operations are defined by the 
following restrictions of the rational operations.

{ The union X [ Y is allowed only if X \ Y = ;.
{ The concatenation X ? Y is allowed only if for all x; x0 2 X, y; y0 2 
Y the equality xy = x0y0 implies x = x0 and y = y0.
{ The Kleene-star X? is allowed only if X is the basis of a free monoid, 
i.e., only if x1 ? ? ? xm = y1 ? ? ? yn with xi; yj 2 X, 1 <= i <= m, 1 
<= j <= n implies m = n and xi = yi for all 1 <= i <= m.

The family of unambiguous rational languages, UR(M ), is the closure of 
the set of finite languages under unambiguous rational operations.

It is a classical result that regular languages are unambiguous 
rational. From this statement we may derive:

Proposition 5.1. The family of unambiguous rational trace languages 
coincides with the family of 1-sequential rational languages, i.e., UR(M 
) = Rat1(M ).


40 Volker Diekert and Yves M?etivier

Proof. The inclusion UR(M ) ? Rat1(M ) is shown by structural induction. 
For the converse, let T 2 Rat1(M ) and L ? ?? be a regular language such 
that '(L) = T and j'?1(t) \ Lj = 1 for all t 2 T . Then any unambiguous 
rational expression for L yields an unambiguous expression for T .

A well-known result of Eilenberg and Schützenberger [43] says that 
semilinear sets are unambiguous rational. This statement has a 
generalization:

Theorem 5.1. We have UR(M (?; I)) = Rat(M (?; I)) if and only if I is 
transitive, i.e., M (?; I) is a free product of commutative monoids.

Proof. A proof of the if-part by generating functions is given in [34, 
Chapt. 5]. For the converse let a, b, and c three distinct letters such 
that (a; b); (b; c) 2 I , but (a; c) =
2 I . Let T = (ab)?c? [ a?(bc)?. It is shown in Ex. 5.2 that T is not 
1-sequential, hence T 2 Rat(M (?; I)) n UR(M (?; I)).

Theorem 5.2. The family of rational trace languages is an effective 
Boolean algebra if and only if (?; I) is transitive.

Proof. For a proof of the if-part see [89]. The other direction is easy 
and shown in the next lemma.

Lemma 5.1. If (?; I) is not transitive, then Rat(M (?; I)) is not closed 
under intersection.

Proof. Take three distinct letters a, b, and c such that (a; b); (b; c) 
2 I , but (a; c) =
2 I . Consider T = (ab)?c? \a?(bc)?. We have T = fanbncn 2 M (?; I) j n 
>= 0g. If T would be rational, then ßa;c(T ) ? fa; cg? would be 
rational, too. However ßa;c(T ) = fancn 2 fa; cg? j n >= 0g. Hence, a 
contradiction.

5.2 Decidability Results

Consider the following six decision problems (proposed by Berstel [4, 
Thm. 8.4] for rational relations), where each instance consists of 
rational trace languages R; T ? M (?; I).

{ Intersection INT(?; I):
Question: Does R \ T = ; hold?
{ Inclusion INC(?; I):
Question: Does R ? T hold?
{ Equality EQU(?; I):
Question: Does R = T hold?
{ Universality UNI(?; I):

Question: Does R = M (?; I) hold?
{ Complementation COM(?; I):
Question: Is M (?; I) n R a rational (finite resp.) trace language? { 
Recognizability REC(?; I):
Question: Is R recognizable?


Partial Commutation and Traces 41

The intersection problem plays a special role. It turns out that it is 
the easiest among the problems above.

Theorem 5.3. INT(?; D) is decidable if and only if (?; I) is a 
transitive forest.

The proof of this result is given in [1]. Recall that transitive forests 
are characterized by forbidden induced subgraphs C4 and P4. In 
particular, every transitive independence alphabet (?; I) is a 
transitive forest.

Theorem 5.4. If the independence relation I is transitive, then all 
decision problems above are decidable.

Proof. The decidability of INT(?; I), INC(?; I), EQU(?; I), and UNI(?; 
I) follows from Thm. 5.2. The answer to COM(?; I) is always \yes" 
(decidable resp.). REC(?;D) is for commutative and free monoids a 
question about semi-linear sets being decidable by Presburger arithmetic 
[55]. In [89] it is shown that this property is preserved under taking 
free products of them yielding the result.

Theorem 5.5. If any of the problems

INC(?; I), EQU(?; I), UNI(?; I), COM(?; I), or REC(?; I)

is decidable, then the independence relation I is transitive.

Proof. All undecidability proofs for the problems above follow the same 
scheme. This scheme is due to Ibarra [63], who proved that universality 
of rational transductions from fa; cg? to b? is undecidable. Our 
notation is borrowed from [89]. Let us start with the following 
formulation of the PCP.

Instance: Two homomorphisms f : A+ ?! B+ and g : A+ ?! B+ Question: Does 
exist some word w 2 A+ such that f(w) = g(w).

Let C = A _[B be the disjoint union of the two alphabets and M = C? ? N. 
Consider the following two languages

W (f) = f(uf(u); n) 2 M j u 2 A+;n = jf(u)jg

W (g) = f(ug(u); n) 2 M j u 2 A+;n = jg(u)jg

The complements of W (f) and W (g) are rational languages. This can 
easily be seen by using a non-deterministic two-tape automaton: Assume, 
we want to accept all (x; n) 2 M not belonging to W (f ). (We assume 
that the number n 2 N is coded in unary on the second tape.) Of course, 
the automaton is able to guess and to check whether x 62 A+B+ or, if x = 
uv, u 2 A+, v 2 B+, but n 6= jf(u)j or v 6= n. Thus, we may assume that 
the input is of the form (x; n) where x = u1au2f(u1)vaw with a 2 A; u1; 
u2 2 A?, f(u1)vaw 2 B+, f(a) 6= va, but n = jf(u1au2)j, jvaj = jf(a)j, 
and jwj = jf(u2)j. (We put f(ui) = 1,

42 Volker Diekert and Yves M?etivier

if ui = 1; i = 1; 2.) The automaton reads non-deterministically u1 on 
the first tape and in parallel it scans jf(u1)j fields on the second 
tape. The automaton remembers the letter a and proceeds 
non-deterministically, on the first tape only, to the position of the 
word va. It checks that, indeed, va 6= f(a). It now accepts, if the rest 
of the input satisfies jwj = n? jvaj ? jf(u1)j. Hence, W (f) and W (g) 
are rational languages.
The following statements are equivalent.

i) The instance of the PCP has no solution, i.e., f(w) 6= g(w) for all w 
2 A+. ii) W (f) \ W (g) = ;
iii) W (f) [ W (g) = M (?; I)
iv) W (f) \ W (g) is finite.
v) W (f) [ W (g) is recognizable.
vi) W (f) \ W (g) is rational.

The implications i) ) ii) ) iii) ) iv) ) v) ) vi) are trivial. We show 
vi) ) i). Assume by contradiction that f(w) = g(w) for some w 2 A+. The 
trace language w+(f(w))+ ? N is recognizable. Now, if W (f) \ W (g) is 
rational, then

W (f) \ W (g) \ (w+(f(w))+ ? N) = f(wn(f(w))n; n ? jf(w)j) j n >= 1g

is again rational, since it is the intersection of a rational with a 
recognizable language. However, the projection to the first component 
yields the nonrational language

fwn(f(w))n j n >= 1g ? A+B+ ? C?:

Contradiction! So far, we have dealt with the monoid M (?; I) = C? ?N. 
Encoding C? into fa; cg?, we see that the results holds for M = fa; cg? 
? b? as well.

This shows that the problems UNI(?; I) by iii), REC(?; I) by v), and 
COM(?; I) by vi) (by iv) resp.) are undecidable, as soon as I is not 
transitive. A fortiori, (by the undecidability of UNI(?; I)) the 
problems EQU(?; I) and INC(?; I) are undecidable in this case.

5.3 Bibliographical Remarks

The presentation of Sect. 5. has been inspired by the work of Bertoni, 
Goldwurm, Mauri, and Sabadini [34, Chapt. 5] and by Sakarovitch [89]. 
The results of the present section can be found there. Prop. 5.1 is 
originally stated in [8]. Thms. 5.1 and 5.2 are from [2, 8, 88]. The 
problems of Sect. 5.2 have been considered for trace languages by 
Gibbons and Rytter [53] thereby showing that, up to INT(?; I), the other 
problems become undecidable for the dependence alphabet (?; D) = a ? b ? 
c. The decidability of REC(?; I) for a transitive independence relation 
is due to Sakarovitch [89]. The characterization by Thm. 5.3 has been 
obtained by Aalbersberg and Hoogeboom [1].


Partial Commutation and Traces 43

6. Dependence Graphs and Logic

6.1 Dependence Graphs

So far, a trace has been defined as a congruence class of a word modulo 
a partial commutation. A trace has also a unique representation as a 
labeled, directed, and acyclic graph, defining therefore a labeled 
partial order or a pomset, (partially ordered multiset). We start with 
an abstract definition. Let (?; D) be a dependence alphabet. A 
dependence graph is (an isomorphism class of) a node-labeled acyclic 
graph [V; E; >=], where

{ V is an at most countable set of vertices,
{ E ? V ?V is the edge (or arc) relation such that the directed graph 
(V; E) is acyclic and the induced partial order is well-founded.
{ >= : V ! ? is the node-labeling such that (>=(x); >=(y)) 2 D if and 
only if (x; y) 2 E [ E?1 [ idV .

Remark 6.1. A partial order is called well-founded, if every non-empty 
set has minimal elements. This assumption will become crucial in Prop. 
6.1 below. However, as long as we deal with finite traces only, 
well-foundedness has no significance. (Hence we can forget about it.) We 
are more general here, since we want a basis which allows to include a 
theory of infinite traces, c.f. Sect. 8..

The set of dependence graphs is denoted by G (?; D). It is a monoid, the 
empty graph 1 = [;; ;:;] is the neutral element and the concatenation of 
the dependence graphs [V1; E1; >=1] and [V2; E2; >=2] is defined as 
follows. First, we take the disjoint union of labeled acyclic graphs, 
and then we introduce additionally arcs from V1 to V2 between all nodes 
with dependent labels. Formally

[V1; E1; >=1] ? [V2; E2; >=2] =

[V1 _[ V2; E1 _[ E2 _[f(x; y) 2 V1 ? V2 j (>=1(x); >=2(y)) 2 Dg; >=1 _[ 
>=2]:

Remark 6.2. Let ff be any countable ordinal, e.g. ff = !; ff = !+1 or ff 
= !!. Consider any subset L ? G (?; D) and let g : ff ?! L be an 
arbitrary mapping.
Then we can easily define the ordered product

?!
Y

i2ff
g(i) 2 G (?; D)

as follows. As above, we take the disjoint union of the labeled graphs 
g(i) over all i 2 ff. Then we introduce additional arcs from a vertex x 
of the graph g(i) to a vertex y of g(j) for all i < j and (>=i(x); 
>=j(y)) 2 D. We define

Lff = f
?!
Y

i2ff
g(i) j g : ff ?! L is a mapping g:


44 Volker Diekert and Yves M?etivier

In particular, for L ? G (?; D) the !-product L! ? G (?; D) is defined. 
According to this definition we have the following situation for subsets 
containing the empty graph:

Lff =
S
fi<=ff(L n f1g)fi ; if 1 2 L:

In particular:
L! = L? [ (L n f1g)! ; if 1 2 L:

Finite dependence graphs form a submonoid of G (?; D). For a dependence 
graph t = [V; E; >=] and a letter a 2 ? let Va = fx 2 V j >=(x) = ag. 
This is a linearly ordered set, hence a well-order and therefore a 
countable ordinal. This ordinal is denoted by jtja and gives the 
a-length of t. It leads to a standard representation where V = f(a; i + 
1) j a 2 ?; 0 <= i < jtjag. The intended semantics is that (a; i + 1) 
denotes the (i + 1)-st node of V having label a. (The notation i + 1 is 
used to exclude limit ordinals, it is of no importance for the finite 
case.) We have >=(a; i) = a, and ((a; i); (b; j)) 2 E if and only if (a; 
b) 2 D and i < j.

Proposition 6.1. The monoid G (?; D) of dependence graphs is 
left-cancellative. Its submonoid of finite graphs is cancellative.

Proof. The result for finite dependence graphs is easily seen from the 
standard representation. For the general case one may use ordinal 
arithmetic.

A letter a 2 ? is given as a one-point graph, labeled with a. Let us 
denote this graph by 'G (a). Then 'G can be extended to a homomorphism

'G : ?? ! G (?; D):

Moreover: 'G (ab) = 'G (ba) for (a; b) 2 I , since 'G (ab) consists of 
two nodes, one labeled with a the other one labeled with b, and the 
graph has no edges. Thus, 'G factorizes and we obtain a homomorphism

'G : M (?; I) ?! G (?; D):

For t = a1 ? ? ? an 2 M (?; I), ai 2 ? for all 1 <= i <= n we have the 
following explicit description of 'G (t). We take any set of n nodes, 
say V = f1; : : : ; ng, then we label node i with ai and we put (i; j) 2 
E if and only if (ai; aj) 2 D and i < j.

Proposition 6.2. The monoid of traces M (?; I) can be identified with 
the submonoid of finite graphs of G (?; D). The homomorphism 'G above 
then becomes the canonical homomorphism ' : ?? ?! M (?; I).

Proof. Let t = [V; E; >=] be a finite dependence graph. Choosing a 
linear order of V which refines the partial order (V; E?), we may assume 
that V = f1; : : : ; ng with (i; j) 2 E only if i < j. An easy 
reflection yields 'G (>=(1) ? ? ? >=(n)) = t, hence 'G is onto. To see 
that 'G is injective, let

Partial Commutation and Traces 45

'G (u) = 'G (v) = [V; E; >=] and (a; b) 2 D. Consider the set Va;b = fx 
2 V j >=(x) 2 fa; bgg. Since (a; b) 2 D, this is a labeled linear order, 
which can be identified with a word of fa; bg?. From the very definition 
of 'G this word is equal to ßa;b(u) (where ßa;b(u) denotes the 
projection of u to fa; bg?). Hence ßa;b(u) = ßa;b(v) for all (a; b) 2 D. 
Therefore u = v by Prop. 2.1.

For the rest of this section we deal with finite traces only and we 
think of (?; D) as being fixed. In particular the size of (?; D) is 
viewed as a constant. As we have mentioned above, it is sometimes 
convenient to identify a trace t (or its dependence graph [V; E; >=]) 
with its induced labeled partial order [V; E?; >=]. (Following standard 
notations E? means the reflexive, transitive closure of E.) However, if 
t is of length n then both [V; E; >=] and [V; E?; >=] are 
representations of t of size ?(n2), since the dependence graph of an has 
n(n?1)
2 edges. Hence, often we content ourselves with representing t by its 
Hasse diagram [V; H;>=]. In the Hasse diagram all redundant edges have 
been removed. Thus, H ? E is the smallest subset such that H? = E?. In 
the Hasse diagram the in- and out-degree of every node is bounded by 
j?j. For a fixed alphabet it is therefore a representation which is 
linear in its length. For jtj = n the Hasse diagram has size ?(n) and it 
is computable in linear time.

Example 6.1. Let

a b

c

d

e
(?; D) = and t = [acebdac]

dependence graph a e d a

b c
c

a e d a

b c
c

Hasse diagram

The Hasse diagram allows a nice visualization of factors. We say that u 
is a factor of t, if we can write t = puq for some p; q 2 M (?; I). 
Given such a factorization t = puq and a representation of t by its 
Hasse diagram [V; H;>=] we can identify p, u and q as a partition of V = 
P _[ U _[ Q. We say that U ? V corresponds to some factor in this 
situation.

Proposition 6.3. Let [V; H;>=] ([V; E; >=] resp.) the Hasse diagram (the 
dependence graph, resp.) of a trace and U ? V . Then U corresponds to 
some factor if and only if for all x; y 2 U every directed path from x 
to y is entirely contained in [U; H \ (U ? U )] ( [U; E \ (U ? U )] 
resp.).


46 Volker Diekert and Yves M?etivier

Example 6.2. Let (?; D) as in the previous example.

a e d a

b c
c
t =

The polygon bdc is a factor of t, the dotted rectangle cbc is not.

Another advantage of the graph interpretation of traces is the existence 
of \visual proofs". Here is such a proof for Levi's Lemma, Prop. 2.2.

t

z

= p
u

q

v

x

y
=

The independence of u and v is clear since there is neither an arc from 
y to x nor from t to z.
The proof of Cor. 2.3 is no more difficult:

u

v
tn
p1 p2

q2
qn

pn

q1

t2
t1
= =

There are no arcs between pj and qi for i < j.

6.2 Traces and Logic

Many classical results about first- and monadic second-order logic are 
extendible from words to traces. Monadic second-order formulae are built 
up upon first-order variables x; y; : : : ranging over elements of V and 
secondorder variables X;Y; : : : ranging over subsets of V . There are 
four types of atomic formulae:

x 2 X , x = y, (x; y) 2 E, and >=(x) = a for a 2 ?.

We also allow Boolean constants true and false, the logical connectives 
_, ^, :, and quantification 9, 8 of first- and second-order variables. A 
first-order formula is a formula without any second-order variable. A 
sentence is a closed formula, i.e., a formula without free variables. 
Identifying a trace t 2 M (?; I) with its dependence graph t = [V; E; 
>=], every sentence ? has an obvious interpretation over t. Thus, the 
truth value of t j= ? is well-defined. The trace language defined by a 
sentence ? is L(?) = ft 2 M (?; I) j t j= ?g. We can speak therefore of 
first-order definability and of second-order definability of trace 
languages.


Partial Commutation and Traces 47

Example 6.3. Let b 2 ? be a letter. The trace (or word) language defined 
by an even number of b is definable in monadic second-order logic. We 
divide the set of positions where a letter b occurs in two disjoint sets 
X and Y . Then we say that between any two different positions of X 
there is at least one position of Y , and vice versa.

Example 6.4. Let ? have a linear ordering and let LexNF ? ?? be the set 
of words which are lexicographic normal forms of traces from M (?; I). 
Then LexNF is definable in first-order logic. In fact, by Prop. 2.4 a 
word is not in LexNF if and only if there are positions i; k such that i 
<= k, >=(i) > >=(k), and (>=(j); >=(k)) 2 I for all i <= j < k.

The predicate x = y, belonging to our syntax, is redundant as long as we 
work with dependence graphs. It could be viewed as an abbreviation of 
>=(x) = >=(y) ^ :(x; y) 2 E ^ :(y; x) 2 E, and >=(x) = >=(y) is the 
formula W
a2?(>=(x) = a^>=(y) = a). In general, transitive closure cannot be 
expressed in first-order logic. Due to the structure of dependence 
graphs we can do it here. A formula defining (x; y) 2 E+ (meaning that 
there is a non-empty path from x to y) can be written in first-order 
logic with the help of at most j?j ? 2 additional variables. In fact, 
(x; y) 2 E+ is equivalent with:

(x; y) 2 E_
_

k<=j?j?2
(9z1 ? ? ? 9zk : (x; z1) 2 E^
^

1<i<=k
(zi?1; zi) 2 E^(zk; y) 2 E)

There is also a first-order expression for the edge relation in the 
Hasse diagram. The assertion (x; y) 2 H is equivalent with:

(x; y) 2 E ^ :(9z : (x; z) 2 E+ ^ (z; y) 2 E+)

In the word case we have E = E+ and we prefer to write x < y instead of 
(x; y) 2 E, where < refers to the total order on positions in words.

Theorem 6.1. Let ' : ?? ?! M (?; I) be the canonical homomorphism and T 
? M (?; I) be a trace language.

i) Then T is definable in monadic second-order logic (first-order logic 
resp.) if and only if '?1(T ) has this property.
ii) Let LexNF ? ?? denote the set of lexicographic normal forms and K ? 
LexNF. Then K is definable in monadic second-order logic (first-order 
logic resp.) if and only if '(K) has this property.

Proof. i): First, let T = L(?) ? M (?; I) for some sentence ? . Let t = 
[V; E; >=] be any trace and w 2 ?? a representing word, i.e., '(w) = t. 
There is a bijective one-to-one correspondence between positions of w 
and nodes of V , and we have (x; y) 2 E if and only if x < y and (>=(x); 
>=(y)) 2 D in the word w. Thus, replacing every atomic formula (x; y) 2 
E by the first-order conjunction
x < y ^ (>=(x); >=(y)) 2 D;


48 Volker Diekert and Yves M?etivier

we obtain a sentence ~
? such that t j= ~
? is equivalent with w j= ? . Hence
'?1(T ) = L( ~
? ). For the converse let K = '?1(T ) \ LexNF. Since T = '(K) and LexNF 
is a first-order language, it is enough to prove the second part of the 
theorem.
ii): Let t = [V; E; >=] be a trace and let ^t = x1 ? ? ? xn 2 LexNF be 
its representation in lexicographic normal form. Every node x 2 V 
corresponds to some xi in ^t and vice versa. We write lex(x; y), if x 
corresponds to xi, y corresponds to xj , and if we have i < j. Thus, 
lex(x; y) means that the node x is before y in its lexicographic normal 
form. If this happens, then either (x; y) 2 E+ or there is some minimal 
index k such that i < k <= j, where xk corresponds to some node z 2 V 
such that (z; y) 2 E?. Moreover, since it is the lexicographic normal 
form we have >=(x) < >=(z) with respect to the ordering of the alphabet.
Based on this observation we obtain the following relation:

lex(x; y) = (x; y) 2 E+ or
>=(x) < >=(y) and :lex(y; x) or
>=(y) < >=(x) and 9z : >=(x) < >=(z) ^ lex(x; z) ^ (z; y) 2 E?:

Since the alphabet is finite, it is enough to unfold the recursion (2 ? 
j?j?1) times and the unfolded formula is a first-order formula (of 
exponential size in j?j) over traces. Now, let K ? LexNF be defined by a 
sentence ? . In ? we will use the symbol lex(x; y) as the atomic formula 
to denote the ordering between positions. We then replace lex(x; y) by 
the first-order formula above. We obtain a formula ~
? over traces. By construction, we have for all w 2 LexNF that w j= ? 
holds if and only if '(w) j= ~
? . The result follows.

By classical results on words, definability in monadic second-order 
logic is equivalent with recognizability. The counterpart of first-order 
logic over words generalizes directly to traces, too.

Corollary 6.1. Let T ? M (?; I) be a trace language. Then the following 
assertions are equivalent.

i) T is recognizable by some finite (finite and aperiodic, resp.) 
monoid. ii) T is recognizable (star-free, resp.).
iii) T is definable in monadic second-order (first-order, resp.) logic.

Proof. Due to Thm. 6.1 and well-known results about words, it is enough 
to show ii) , iii) for the assertion about first-order logic, only. Both 
directions are obtained analogously to the word case: The direction ii) 
) iii) is more simple (in first-order logic) and we sketch the main idea 
for the concatenation. Let t = [V; E; >=] be a trace and t = uw a 
factorization. Then u; w correspond to subsets U; W ? V . In fact, we 
find a finite set X = fx1; : : : ; xkg, 0 <= k <= j?j, such that U = fy 
2 V j 9xi 2 X : (y; xi) 2 E?g and W = fz 2 V j 8xi 2 X : (xi; z) =
2 E?g. By standard techniques, see [91], we can construct for given two 
first-order sentences ?1; ?2 a new first-order sentence specifying

Partial Commutation and Traces 49

those traces such that there exists a finite set X as above and the 
dependence graph restricted to U satisfies ?1, whereas the dependence 
graph restricted to W satisfies ?2. The implication iii) ) ii) follows 
from Thm. 6.2 below giving a more precise statement.

Example 6.5. Let (?; D) = a ? b ? c and T ? M (?; I) the trace language 
T = (acbcab)+. Since ac = ca, this is the set of traces

c

a

c

a

c

a

? ? ? b b
b
b

with an even number of b. By the method of the first example of this 
section, this trace language is definable in monadic second-order, but 
it is not firstorder-definable. On the other hand, the word language T = 
(acbcab)+ ? fa; b; cg? has a description by a first-order sentence. It 
is the set of words starting with acbcab and every occurrence of the 
factor ab is either the end or the word followed by another factor 
acbcab.

Remark 6.3. It is known by [79] that the commutative closure of a 
star-free word language is either still star-free or not recognizable 
anymore. The example above shows that for (?; D) = a?b?c the image of 
the word language (acbcab)+ in M (?; I) is recognizable, but not 
star-free. This means in particular that the result about the 
commutative closure of star-free languages can not be generalized to 
arbitrary trace monoids M (?; I). There is a precise characterization 
[79]: For all star-free word languages it holds that the I-closure is 
either star-free or not recognizable if and only if the dependence 
relation D is transitive.

6.3 Ehrenfeucht-Frä?ss?e-Games

Let t = [V (t); E(t); >=(t)] be any node-labeled graph. Then V (t) 
denotes the set of vertices, E(t) ? V (t) ? V (t) is the edge relation, 
and >=t : V (t) ! ? is the node-labeling. For the moment it is not 
necessary to put any further restrictions on E(t). Thus, the graphs may 
be finite or infinite, directed or undirected, cyclic or acyclic, etc. 
By a = (a1; : : : ; ak) we denote a k-tuple of nodes, a 2 V k, k >= 0. 
If x = (x1; : : : ; xk), then ?(x) denotes a firstorder formula with 
free variables x1; : : : ; xk. Any pair (t; a) yields a natural 
interpretation for ?(x). The interpretation of xi is ai for 1 <= i <= k. 
Thus, the expression (t; a) j= ?(x) has a well-defined truth value.

An Ehrenfeucht-Frä?ss?e-game has two players, Player I and Player II. 
The players take two structures (s; a) and (t; b) as above: s = [V (s); 
E(s); >=s], a 2 V (s)k, t = [V (t); E(t); >=t], and b 2 V (t)k. They 
first decide on the number of rounds m with m >= 0.

If m = 0, we say that Player II wins the game, if >=s(ai) = >=t(bi) and 
(ai; aj) 2 E(s) , (bi; bj) 2 E(t) for all 1 <= i; j <= k. If m >= 1, 
then Player I

50 Volker Diekert and Yves M?etivier

begins and takes either a vertex ak+1 2 V (s) or a vertex bk+1 2 V (t). 
Player II answers by taking either some bk+1 2 V (t) (if Player I has 
chosen in the graph s), or by taking some ak+1 2 V (s) (otherwise). This 
finishes the first round. The game is continued with (m ? 1) rounds over 
the new structures (s; (a1; : : : ; ak; ak+1)) and (t; (b1; : : : ; bk; 
bk+1)).

The relation '(m;k) is defined by setting (s; a) '(m;k) (t; b), if 
Player II has a winning strategy for a game on m rounds. The following 
lemmata are well-known facts in logic.

Lemma 6.1. The relation '(m;k) is an equivalence relation of finite 
index.

The quantifier depth of a formula is defined inductively. For atomic 
formulae it is zero, the use of the logical connectives does not change 
it, and adding a quantifier in front increase the quantifier depth by 
one. For example, the following formula has quantifier depth two:

8x((9y(>=(x) 6= >=(y))) _ (9z(>=(z) = b ^ ((x; z) 2 E _ >=(x) = a))))

Lemma 6.2. Let ?(x) be a first-order formula with free variables x1; : : 
: ; xk and (s; a) j= ?(x). If ?(x) has quantifier depth m and (s; a) 
'(m;k) (t; b),

then we have (t; b) j= ?(x), too.

Let us denote by [s; a; m; k] the equivalence class f(t; b) j (s; a) 
'(m;k) (t; b)g.

Lemma 6.3. Each equivalence class [s; a; m; k] can be specified by a 
firstorder formula ? [s; a; m; k](x) of quantifier depth m and with free 
variables x1; : : : ; xk.

Proof. For m = 0 this is clear. Consider m+ 1 and assume inductively 
that formulae for all classes [s; (a; ak+1); m; k + 1] are already 
specified. The next formula satisfies the requirement, it defines ? [s; 
a; m+ 1; k](x): V
ak+1( 9xk+1? [s; (a; ak+1); m; k + 1](x; xk+1)) ^

8xk+1(
_

ak+1
? [s; (a; ak+1); m; k + 1](x; xk+1)):

Observe that the conjunction
V
ak+1 and the disjunction
W
ak+1 can be made
finite by Lem. 6.1. Details are left to the reader.

Next, we need a concatenation on node-labeled graphs s = [V (s); E(s); 
>=s]. We adopt the definition for dependence graphs. Thus, we define s ? 
t by

[V (s) _[ V (t); E(s) _[ E(t) _[f(x; y) 2 V (s)?V (t) j (>=s(x); >=t(y)) 
2 Dg; >=s _[ >=t]:

Having this, we can state the following Congruence Lemma. Its proof is 
clear, since, due to the definition of concatenation, whether or not (x; 
y) 2 E(s ? t) for x 2 V (s); y 2 V (t) depends on the labels of x and y, 
only.

Partial Commutation and Traces 51

Lemma 6.4. Let u be any fixed node-labeled graph and fu1; : : : ; ung 
its ver-

tex set. Let (s; a) '(m;k1) (s0; a0) and (t; b) '(m;k2) (t0; b
0
).
Then it holds:

(s ? u ? t; (a; u1; : : : ; un; b)) '(m;k1+n+k2) (s0 ? u ? t0; (a0; u1; 
: : : ; un; b 0
)):

In order to close the bridge to the star-free sets, we need a finitely 
generated monoid. For convenience we restrict our attention therefore 
again to finite dependence graphs, only. It is a nice coincidence that 
we have the following fact.

Proposition 6.4. The set of traces (i.e., the set of finite dependence 
graphs) can be specified by a first-order sentence.

Proof. The first requirement for dependence graphs is a first-order 
statement

8x8y : (>=(x); >=(y)) 2 D , (x; y) 2 E _ (y; x) 2 E _ x = y:

The second requirement asks for acyclic graphs. Because of the first 
formula, it is enough to exclude cycles of short length; more precisely, 
we do not allow cycles of length less or equal j?j + 1. Short cycles 
however can be specified in first-order logic.

A dot-depth hierarchy for words can also be defined for traces. The 
empty set ; and the set of all traces M (?; I) are of dot-depth zero. To 
obtain level k of the dot-depth hierarchy, k >= 1, we define it here as 
the Boolean closure of the languages L ? a ? K, where a 2 ? and L; K are 
of level k ? 1.

Theorem 6.2. Let ? be a first-order sentence of quantifier depth m and 
L(?) = ft 2 M (?; I) j t j= ?g. Then L(?) is in the m-th level of the 
dot-depth hierarchy, and the corresponding star-free expression for L(?) 
can effectively been constructed.

Proof. We sketch the proof, only. For m = 0 the result is true. By 
induction, we assume the result to be correct for m and that the 
sentence ? has quantifier depth m+1 and it is in fact of the form ? = 
9x? 0(x). Consider the following union

T =
[
fU ? a ? V j a 2 ?; U = [u; (); m; 0]; V = [v; (); m; 0]; and uav j= ?g:

We now make several observations. The union is finite by Lem. 6.1. By 
induction and Lem. 6.3, it is a star-free expression of dot-depth m + 1. 
Since u 2 U , v 2 V , we have uav 2 T , hence L(?) ? T . The converse 
inclusion follows by known techniques from the Congruence Lemma (Lem. 
6.4) and Lem. 6.2.


52 Volker Diekert and Yves M?etivier

6.4 Bibliographical Remarks

Dependence graphs for traces have been considered first by Mazurkiewicz 
in [69]. In Anisimov and Knuth we find the description as labeled 
partial orders [3]. The characterization of recognizable trace languages 
by monadic secondorder logic over traces is due to Thomas [92]. Our 
proof follows Ebinger [41], see also [34, Chapt.10]. This allows to 
include the first-order statements in Thm. 6.1 and, as noted earlier, 
Cor. 4.3 is an immediate consequence. Independently Courcelle [22] gave 
another proof for Cor. 4.3 using monadic second-order logic over traces. 
The equivalence of i) and ii) of Cor. 6.1 has been shown by Guaiana, 
Restivo, and Salemi [58]. The equivalence to iii) is from [42]. Thm. 6.1 
and Cor. 6.1 have a generalization to concurrency monoids by Droste and 
Kuske [37, 39]. Our proof technique using Ehrenfeucht-Frä?ss?e-games 
follows [91]. It led to Thm. 6.2 being a partial analogue of a result of 
Thomas [90] on words.

7. Asynchronous Automata

7.1 Zielonka's Theorem

An asynchronous automaton A has a distributed finite state control such 
that independent actions may be performed in parallel. The set of global 
states is modeled as a Cartesian product Q =
Q

i2J
Qi, where the Qi are states

of the local component i 2 J and J is some index set. With each letter a 
2 ? we associate a read domain R(a) ? J and a write domain W (a) ? J . 
We henceforth assume that W (a) ? R(a) being a rather natural (but 
technically important) restriction. The transitions are given by a 
family of partially defined functions (throughout we deal for simplicity 
with deterministic automata, only): 0

@ffia :
Y

i2R(a)
Qi ?!
Y

i2W (a)
Qi

1

A

a2?
Thus, each a reads the status in the local components of its read domain 
and changes states in local components of its write domain. Accordingly 
to the read-and-write-conflicts being allowed, we distinguish four basic 
types:

{ Concurrent-Read-Exclusive-Write (CREW),
if R(a) \ W (b) = ; for all (a; b) 2 I .
{ Concurrent-Read-Owner-Write (CROW),
if R(a) \ W (b) = ; for all (a; b) 2 I and W (a) \ W (b) = ; for all a 
6= b. { Exclusive-Read-Exclusive-Write (EREW),
if R(a) \ R(b) = ; for all (a; b) 2 I .
{ Exclusive-Read-Owner-Write (EROW),
if R(a) \ R(b) = ; for all (a; b) 2 I and W (a) \ W (b) = ; for all a 6= 
b.

Partial Commutation and Traces 53

The local transition functions (ffia)a2? give rise to a partially 
defined transition function on global states

ffi : (
Y

i2J
Qi) ?? ?!
Y

i2J
Qi

where ffi
?
(qi)i2J ; a
?
= (q0
i)i2J is defined if and only if ffia
?
(qi)i2R(a)
?
is de-

fined. In this case we have q0
j =
?
ffia
?
(qi)i2R(a)
??

j
for j 2 W (a) and qj = q0
j

otherwise. If A is of any of the four types above, then it is clear that 
we can define the action of a trace t 2 M (?; I) on global states. It is 
convenient to denote this function again by ffi. Therefore, we may view 
it as a partially defined function ffi : Q ? M (?; I) ! Q. Given an 
initial state q0 2 Q and a set F ? Q, we obtain an M (?; I)-automaton. 
The automaton

A =

?
Q

i2J
Qi; (ffia)a2? ; q0; F

?

accepts the language L(A) = ft 2 M (?; I) j

ffi(q0; t) 2 Fg. If Q is finite, then L(A) is a recognizable trace 
language. As well-known in automata theory, we may add local dead states 
in order to have a totally defined transition function.

Before we continue we need some more notations. Let t 2 M (?; I) be a 
trace and a 2 ? be a letter. By @a(t) we denote the smallest prefix of t 
which contains all occurrences a of t. Thus, @a(t) is the trace of 
minimal length satisfying j@a(t)ja = jtja such that t = @a(t)q for some 
q 2 M (?; I). Viewing t as a labeled partial order, @a(t) contains all 
vertices with label a and the past of them. This notion is extended to 
subsets A ? ?. The trace @A(t) is the minimal prefix of t satisfying 
j@A(t)ja = jtja for all a 2 A. Note that @;(t) = 1, @?(t) = t, and @a(t) 
is a prefix of @A(t) for all a 2 A. Moreover, viewing t as labeled 
partial order, we find that @A(t) is the union of the @a(t), a 2 A.

Definition 7.1. A mapping ff : M (?; I) ! Q to some finite set Q is 
called asynchronous, if the following two conditions are satisfied.

i) The value ff(@A[B(t)) is computable from ff(@A(t)) and ff(@B(t)). ii) 
If t = @D(a)(t), then the value ff(ta) is computable from a 2 ? and the 
value ff(t).

A trace language T ? M (?; I) is recognized by an asynchronous mapping 
ff, if T = ff?1ff(T ).

The following theorem is far from being trivial. It is crucial for the 
general construction of asynchronous automata.

Theorem 7.1. A trace language is recognizable if and only if it is 
recognized by some asynchronous mapping.

We cannot go into details of the difficult only-if-part of the theorem. 
Once this has been shown, then the proof of the if-part (c.f. Prop. 7.1) 
yields Zielonka's Theorem as a corollary.


54 Volker Diekert and Yves M?etivier

Corollary 7.1. A trace language is recognizable if and only if it is 
recognized by some asynchronous automaton.

The next sections give explicit transformations between the different 
types of asynchronous automata. Therefore we have Zielonka's Theorem for 
all types considered here.

7.2 Asynchronous Cellular Automata

Definition 7.2. An asynchronous automaton A is called asynchronous 
cellular, if the state space Q can be decomposed as Q = Q

a2?
Qa such that

W (a) = fag and R(a) = D(a) = fb 2 ? j (a; b) 2 Dg for all a 2 ?.

Remark 7.1. Every CROW-type asynchronous automata can be viewed as 
asynchronous cellular by a trivial transformation (regrouping 
components) which does not change the number of reachable global states.

The following proposition yields the if-part of Thm. 7.1.

Proposition 7.1. Let ff : M (?; I) ! Q be an asynchronous mapping 
recognizing a trace language T . Then Q? is the state space of an 
asynchronous cellular automaton A with L(A) = T .

Proof. The tuple q0 = (ff(1))a2? is used as initial state. The global 
transition function is defined such that

ffi(q0; t) =

?

ff(@b(t))

?

b2?
:

The reason why this works is based on the equation @a(ta) = @D(a)(t)a, 
which holds for all t 2 M (?; I) and a 2 ?. In fact, consider a tuple 
(qb)b2D(a) with qb = ff(@b(t)). Due to the first condition of an 
asynchronous mapping, we can compute the value of ff(@D(a)(t)). By the 
second condition, we may compute ff(@D(a)(t)a), which is ff(@a(ta)). 
Therefore we can change the local state qa to the new local state q0
a = ff(@a(ta)). Finally, observe that for all
b 2 ?, b 6= a we have @b(ta) = @b(t). Hence, the new global state 
satisfies indeed ffi(q0; ta) = (ff(@b(ta))b2? . It is enough to define 
the final states by F = f(ff(@b(t)))b2? j t 2 Tg. The result follows.

7.3 Changing Concurrent-Read to Exclusive-Read

The original definition an asynchronous automaton demands an EREW-type 
with R(a) = W (a) for all a 2 ?. Obviously, EROW is even a stronger 
condition. (Recall our general assumption W (a) ? R(a) for a 2 ?). 
Therefore we content ourselves with the following proposition.


Partial Commutation and Traces 55

Proposition 7.2. For every asynchronous automaton A of CROW-type there 
exists an asynchronous automaton A0 of EROW-type with the same number of 
reachable global states and recognizing the same language, L(A) = L(A0).

Proof. By a remark above we may assume that the state space of A has the 
form Q =
Q

a2?
Qa and R(a) = D(a) = fb 2 ? j (a; b) 2 Dg for all a 2 ?.

Define P(a;b) = Qa for all b 2 D(a), a 2 ? by using different copies. 
The new set of global states is defined by P =
Q

a2?

Q

b2D(a)
P(a;b). For a 2 ? we define

the new partially defined transition function.

ffi0
a :
Y

b2D(a)
P(b;a) ?!
Y

c2D(a)
P(a;c)

(qb)b2D(a) 7?!
?
ffia
?
(qb)b2D(a)
??

c2D(a)

In A0 the write domain of a letter a is W 0(a) = f(a; c) j c 2 D(a)g. 
The read domain above has reduced to R0(a) = f(b; a) j b 2 D(a)g rather 
than putting artificially R0(a) [ W 0(a) (only in order to satisfy our 
restriction W 0(a) ? R0(a)). Thus, our construction realizes even an 
owner-read-ownerwrite (OROW) concept. In any case, it is clear how to 
define the initial state and the global final states in order to archive 
L(A) = L(A0). Note that, although the number of global states became 
larger, the number of reachable states did not change. In some sense the 
automaton did not change at all.

7.4 Changing Exclusive-Write to Owner-Write

Let A =

?
Q

i2J
Qi; (ffia)a2? ; q0; F

?

be a finite asynchronous automaton of

EREW-type. We are going to transform A into an asynchronous cellular 
automaton A0 recognizing the same language. Denoting by ni the 
cardinality of Qi we may assume that we have Qi = Z=niZ for all i 2 J . 
For each a 2 ? define
Pa =
Y

i2R(a)
Z=niZ:

An element of Pa is denoted in the following as a tuple (q(a; i))i2R(a). 
The set of global states of the asynchronous cellular automaton A0 is P 
= Q

a2?
Pa.

For every local state space Qi; i 2 J , there exist now several copies 
available for A0. For i 2 J let ?i = fa 2 ? j i 2 R(a)g. The idea of the 
construction is to split the information about a local state qi 2 Qi 
among the components with a 2 ?i such that the following invariant is 
satisfied

qi =
X

a2?i
q(a; i) mod ni:


56 Volker Diekert and Yves M?etivier

Without restriction the local initial state (q0)i is the value 0 2 Z=niZ 
for all i 2 J . In order to satisfy the invariant above we simply put

(p0)a = (0; : : : ; 0) 2
Y

i2R(a)
Z=niZ

and define p0 = (p0)a2? as the initial state of A0.
We have to explain how to perform an a-transition on a global state 
((q(b; i))i2R(b))b2? for some letter a 2 ?.

For every i 2 R(a) we read in the components Pb where b 2 ?i. Note that 
since we have started with an exclusive-read automaton this implies (a; 
b) 2 D. Thus, reading in all these components is allowed by the 
definition of an asynchronous cellular automaton. We simply compute the 
sum:

qi =
X

b2?i
q(b; i) mod ni 2 Z=niZ = Qi:

The transition function ffia of the automaton A is used to define a 
value q0 = ffia((qi)i2R(a)) being in fact a tuple q0 = (q0
j )j2W (a) with W (a) ? R(a).
The automaton A0 may change the values in the components of the local 
state space Pa as follows:

q0(a; i) = q(a; i) for i 2 R(a) n W (a);
q0(a; j) = q0
j ?
P
b2?jnfag q(b; j) for j 2 W (a):

The invariant above is verified again. It is therefore clear how to 
simulate A step by step and how to define final states in order to 
complete the transformation. We should add a remark on the size of the 
new automaton. A reasonable definition of the size of A is the sum j?j +
P
i2J jQij+ length of the program
which implements the family (ffia)a2? . (At first sight this definition 
might look strange, but it is a quite realistic measure.) With this 
notion of size, we can state the following proposition.

Proposition 7.3. For every asynchronous automaton of EREW-type we can 
construct in polynomial time an asynchronous cellular automaton 
recognizing the same language.

7.5 The Construction for Triangulated Dependence Alphabets

A surprisingly simple construction of asynchronous automata is known for 
triangulated dependence alphabets. An undirected graph is called 
triangulated, if all its chordless cycles are of length three. 
Particular cases are therefore complete graphs and acyclic graphs 
(acyclic means a disjoint union of trees). A dependence alphabet (?; D) 
is called triangulated, if the underlying undirected graph has this 
property. A perfect vertex elimination scheme of (?; D) is a linear 
ordering >= of ? such that for all a 2 ? the set

Partial Commutation and Traces 57

E(a) = fb 2 D(a) j a >= bg forms a clique (i.e., a complete subgraph; 
(E(a))? is therefore a free monoid). We may represent a perfect vertex 
elimination scheme by a list [a1; : : : ; an] such that ai >= aj if and 
only if i <= j. It is well-known, see e.g. the textbook of Golumbic [56, 
Thm. 4.1] that (?; D) has a perfect vertex elimination scheme if and 
only if it is triangulated. If e.g. (?; D) is acyclic, then any ordering 
which represents a topological sorting yields a perfect vertex 
elimination scheme. For a complete graph, every total order is a perfect 
vertex elimination scheme.

Let (?; D) be any dependence alphabet and let <= be a linear ordering of 
? such that for all a; b; c 2 ?, a <= b <= c, (a; c) 2 D and (b; c) 2 D, 
we have (a; b) 2 D, too. Thus, if ? = fa1; : : : ; ang, n = j?j is 
written in increasing order a1 < ? ? ? < an, then [an; : : : ; a1] is a 
perfect vertex elimination scheme of (?; D). Hence (?; D) is 
triangulated. Consider now a homomorphism to a finite monoid ? : M (?; 
I) ?! S.

Define for ? ? ? and sc 2 S (c 2 ? ) the ordered product ?!
Y

c2?
sc by

multiplying the elements according to the ordering in ?. Thus, ?!
Y

c2?
sc =

sc1 ? ? ? scm , if ? = fc1; : : : ; cmg, m >= 0, with c1 < ? ? ? < cm. 
All products of elements of S used here will be ordered ones. We are 
going to construct an asynchronous automaton A recognizing a trace 
language T = ??1(?(T )). The state set of A will be an n-fold direct 
product of S, n = j?j. Let A = (
Q

a2?
Qa; ffi; q0; F ) be the automaton with Qa = S for all a 2 ? such

that the global transition function

ffi : (
Y

a2?
Qa) ?? ?!
Y

a2?
Qa;

is defined for q = (qb)b2? and a 2 ? as follows:

ffi(q; a) = q0 with qb0 =

8
>
>
>
<

>
>
>
:

? ?!
Y

a<=c; (a;c)2D
qc
?
? ?(a) if b = a

1 if a < b; (a; b) 2 D
qb otherwise

Furthermore, let q0 = (1)a2? and F = f(qa)a2? 2
Q

a2?
Qa j
?!
Y

a2?
qa 2 ?(T )g.

Proposition 7.4. Let T ? M (?; I) be recognized by the homomorphism ? : 
M (?; I) ! S to the finite monoid S. Let A be the automaton defined 
above. Then A is asynchronous of EREW-type and we have L(A) = T .

Proof. The write-and-read domain of a letter a 2 ? is given by the index 
set R(a) = W (a) = fb 2 D(a) j a <= bg. Assume that for some a; b; c 2 
?, a <= b <= c we have (a; c) 2 D and (b; c) 2 D. Then (a; b) 2 D 
follows, due to

58 Volker Diekert and Yves M?etivier

the ordering. Hence, if (a; b) 2 I , then a and b have disjoint 
write-and-read domains. Thus, A is asynchronous of EREW-type. In 
particular, for any trace w 2 M (?; I), the global state ffi((1)a2? ; w) 
is well-defined. We denote this global state also by q0 ? w.
For (qa)a2? = q0 ? w the following two invariants can be shown:

i) a < b and (a; b) 2 I imply qb ?(a) = ?(a) qb.
ii) a < b <= c, (a; b) 2 I , and (a; c) 2 D imply qb qc = qc qb.

The proposition follows now from the following claim:

For (qa)a2? = q0 ? w we have
?!
Y

a2?
qa = ?(w):

The claim is satisfied for jwj = 0 since q0 = (1)a2? . By induction 
assume that the claim holds for q = q0 ? w and let q0 = q ? a for some 
letter a 2 ?.

Since
?!
Y

c2?
qc = (
?!
Y

c<a
qc) ? (
?!
Y

a<=c
qc), it is enough to show:

(
?!
Y

a<=c
qc) ?(a) = (
?!
Y

a<=c; (a;c)2D
qc) ?(a) (
?!
Y

a<b; (a;b)2I
qb):

However, this last formula is immediate from the two invariants above.

Remark 7.2. Note that as soon as the dependence graph contains a 
chordless cycle of length greater than three, the automaton constructed 
above is not asynchronous anymore. More precisely, for any ordering <= 
of the alphabet ? there exist letters a < b < c (on the cycle) 
satisfying (a; c) 2 D, (b; c) 2 D, but (a; b) 2 I . In this case 
however, c belongs to both read domains of a and of b.

7.6 Bounded Time-Stamps in a Distributed System

Suppose that in a distributed system some agents communicate by means of 
messages. Usually, to execute correctly the prescribed protocol the 
agents should have some knowledge about the relative order of messages. 
To this end, they add to every message a tag , called a time-stamp, 
enabling them to find out the necessary information about the ordering 
of messages. The importance of an appropriate stamping algorithm was for 
the first time emphasized by Lamport (1978) [67], to which we refer the 
reader for further discussion. In most cases, it is a relatively easy 
task to construct an appropriate stamping system if no bounds on the 
size of stamps are imposed. But if we allow only a finite set of 
time-stamps then the construction of an appropriate stamping system 
becomes difficult or sometimes even impossible. In this section we show 
how to use the result about asynchronous automata to construct a special 
finite time-stamp system.


Partial Commutation and Traces 59

The distributed system considered here consists of a finite set ? of 
agents and a finite set B of boxes. The agents communicate by messages 
that they leave in some boxes. Every agent a 2 ? has access only to a 
subset Dom(a) ? B of boxes (Referring to previous notations, we consider 
here Dom(a) = R(a) = W (a):) Conversely, for every box i 2 B, ?i = fa 2 
? j i 2 Dom(a)g is the set of agents which have access to i. If i 2 
Dom(a) then we say that the box i and the agent a are adjacent.

By Bi, for i 2 B, we shall denote the contents of the box i, i.e. the 
set of messages contained in i. We assume that at the beginning all 
boxes are empty, i.e., Bi = ; for all i 2 B.

Every message is a triple (m; a; d), where m is the contents of the 
message taken from some set M of possible contents; a 2 ? identifies the 
sender of the message, and finally d is a time-stamp from some set 
Stamps of time-stamps. Thus formally the Cartesian product U = M ? A ? 
Stamps is the set of all messages. In the following, by contents, 
sender, and stamp we shall denote the projection of U onto M , ?, and 
Stamps respectively. Furthermore, we assume that any box contains for 
any a 2 ? at most one message sent by a.

During their moves the agents not only will send new messages but also 
will retransmit messages sent by other agents. For this reason, besides 
messages left by agents adjacent to i, every box i 2 B can contain 
messages sent by other agents and retransmitted by agents from ?i.

A single move of each agent a 2 ? consists of four phases. During the 
first phase a reads the contents of all adjacent boxes, emptying them in 
this way. Let R be the set of messages that were read in this phase. In 
the second phase, for every b 2 ? n fag, if R contains messages sent by 
b then a selects the last of them (the most recent), denoted it ub. In 
the third phase, a chooses m 2 M that it wishes to send and computes a 
time-stamp d 2 Stamps. Let ua = (m; a; d).
Finally, in the last phase a transmits to all adjacent boxes all 
messages from the set fuc j c 2 ?g.

The entire move (consisting of reading, selecting, constructing a new 
message, and sending) is considered to be atomic. This implies that the 
access to every box is sequential, and moreover, at a given moment, an 
agent a has access either to all adjacent boxes or to none of them. Note 
that immediately after the move all boxes adjacent to a have the same 
contents: for every agent b 2 ?, they contain at most one message issued 
by b, namely the last message sent by b and known to a. We assume that 
for every message u 2 U the field contents(u) does not provide any 
information concerning the relative order of messages. Thus during the 
second phase of every move, agent a can use only the fields sender(u) 
and stamp(u) of u 2 R to find out for every b 2 ? n fag the last message 
in R sent by b.

To implement this system we should specify: the set Stamps, the 
algorithm selecting messages in the second phase of each move, and the 
algorithm assigning a stamp to the new message created in the third 
phase.

60 Volker Diekert and Yves M?etivier

A simple implementation exists if we allow the set Stamps to be 
infinite. Let Stamps = N, and assume that every agent is equipped with a 
counter initially set to 0. Then during its move, agent a increases its 
counter by 1 and takes the obtained value as the time-stamp d for its 
new message in the third phase, ua = (m; a; d). The selection procedure 
in the second phase of the move is trivial in this implementation. For 
every b 2 ? n fag, a takes all messages in R with the sender field equal 
to b and selects among them the one with the greatest stamp field.

The aim of this section is to present a different implementation with a 
bounded number of time-stamps. First we define some auxiliary notions. 
By a serial event we shall mean any finite sequence of elements of the 
set M??, SE = (M ??)?. Any occurrence of (m; a) 2 M ?? in a serial event 
x 2 SE represents a move performed by the agent a such that m is the 
contents of the new message sent by a during this move. Let us suppose 
that ff is an algorithm implementing the system. For every x 2 SE and i 
2 Box by Bff i (x)
we denote the contents of the box i after the execution of the serial 
event x in the implementation ff; Bff
i (x) can be defined in the following inductive
manner:

(i) for all i 2 Box, Bff
i (ffl) = ;,
(ii) if y = x(m; a) 2 SE then
(1) for all i 2 B n Dom(a), Bff
i (y) = Bff
i (x),
(2) to obtain the new contents of all boxes adjacent to a apply the 
algorithm ff to Bi = Bff i (x) with i 2 Dom(a).

Example 7.1. Let ? = fa; b; c; dg and B = fBab; Bbc; Bcd; Bdag, where 
Bxy with x; y 2 ?, denotes the box adjacent to x and y.
Let S = (m1; a)(m2; b)(m3; a)(m4; c)(m5; d) be a serial event and let Si 
denote the prefix of S of length i = 0; : : : ; 5.
The contents of the boxes after the execution of Si in the counter 
implementation that was considered previously are as follows.

After S0: Bab = ;, Bbc = ;, Bcd = ;, Bda = ;;
After S1: Bab = f(m1; a; 1)g, Bbc = ;, Bcd = ;, Bda = f(m1; a; 1)g; 
After S2: Bab = f(m1; a; 1); (m2; b; 1)g, Bbc = f(m1; a; 1); (m2; b; 
1)g, Bcd = ;, Bda = f(m1; a; 1)g;
After S3: Bab = f(m3; a; 2); (m2; b; 1)g, Bbc = f(m1; a; 1); (m2; b; 
1)g, Bcd = ;, Bda = f(m3; a; 2); (m2; b; 1)g;
After S4: Bab = f(m3; a; 2); (m2; b; 1)g, Bbc = f(m1; a; 1); (m2; b; 1); 
(m4; c; 1)g, Bcd = f(m1; a; 1); (m2; b; 1); (m4; c; 1)g, Bda = f(m3; a; 
2); (m2; b; 1)g; After S5: Bab = f(m3; a; 2); (m2; b; 1)g, Bbc = f(m1; 
a; 1); (m2; b; 1); (m4; c; 1)g, Bcd = f(m3; a; 2); (m2; b; 1); (m4; c; 
1); (m5; d; 1)g,
Bda = f(m3; a; 2); (m2; b; 1); (m4; c; 1); (m5; d; 1)g.

Let I be the independence relation over ? defined in the following way:

I = f(a; b) 2 ? ?? j Dom(a) \ Dom(b) = ;g:


Partial Commutation and Traces 61

To define time-stamps we need some definitions. First we define the set 
of prime elements, denoted P r(?; I); by

P r(?; I) = f@a(t) j a 2 ? and t 2 M (?; I)g:

We can associate to a message a trace which encodes the partial order 
corresponding to the communication between agents. As we want bounded 
timestamps, we define a map having a finite image and carrying enough 
information on a trace t to know the prefix order on the traces @a(t) 
for a 2 ?: We thus define a labeling >= from P r(?; I) into the set of 
positive integers by

>=(1) = j?j;

and for a 2 ?; t 2 M (?; I) such that ta 2 P r(?; I);

>=(ta) = minfi 2 N n f0g j 8b 2 ? n fag i 6= >=(@a(@b(t)))g:

From this mapping >= we construct for every trace t a mapping ?t from 
??? into N n f0g setting for any pair (a; b) of letters

?t(a; b) = >=(@a(@b(t))):

We denote by F (X ; Y ) the family of all partial mappings from X to Y: 
It turns out that the mapping ? associating with a trace t of M (?; I) 
the element ?t of F (? ??; f1; : : : ; j?jg) is asynchronous. Its 
importance is emphasized by the fact that all asynchronous mappings we 
need in the proof of Zielonka's Theorem are refinements of this basic 
mapping ?:
We set Stamps = F (?; f1; : : : ; ng), where n = j?j. Let tag be the 
mapping from P r(?; I) into Stamps defined in the following way:

8t 2 P r(?; I); 8a 2 ? : tag(t)(a) = >=(@a(t)):

Now the idea of the implementation fl is to assign to messages elements 
of Stamps in such a way that the following condition is satisfied (we 
recall that ?i = fa 2 ? j i 2 Dom(a)g).
Condition (? ): 8h 2 H , 8b 2 ?, 8i 2 B, 8t 2 M (?; I), 8k > 0: if

t = sender(h) 2 M (?; I);

j@b(@?i(t))jb = j@?i(t)jb = k > 0;

(m; b) is the k-th message of b in h,

then
(m; b; tag(@b(@?i(t)))) 2 Bfl
i (h):

If Condition (? ) holds, h 2 H , and t = sender(h), then for each i 2 B 
the time-stamps of the messages in the box i determine the mapping ?@?i 
(t).

62 Volker Diekert and Yves M?etivier

Lemma 7.1. Suppose that an implementation fl satisfies (? ). Let h 2 H, 
t = sender(h) 2 M (?; I). Then:

?@?i (t)(c; b) =

?
n if Bfl
i (h) does not contain messages sent by b
f(c) if (m; b; f) 2 Bfl
i (h).

Now we can present the details of the algorithm fl. Let a 2 ? and let h 
2 H be the history executed up to now. Let t = sender(h) 2 M (?; I). 
Inspecting the contents of box i, a can calculate ?@?i (t) for all i 2 
Dom(a). Now by the property of ? agent a obtains ?@D(a)(t). During the 
selection phase, a chooses for every b 2 ? n fag from the reading set R 
the message ub = (m; b; f) such that:
8c 2 ? f(c) = ?@D(a)(t)(c; b):

As ? is asynchronous, a can now get ?@a(ta). Let g be the mapping from ? 
into f1; : : : ; ng such that:

8c 2 ?; g(c) = ?@a(ta)(c; a):

Then g is the time-stamp for the new message that a creates during the 
third phase, ua = (m; a; g). To show the correctness of fl it suffices 
to observe that if Condition (? ) holds for a history h then it holds 
for the history h(m; a) for every (m; a) 2 M ??.

7.7 Bibliographical Remarks

Zielonka's Theorem is from [93]. Proofs based on the notion of 
asynchronous mappings can be found in [20, 24], and [34, Chapt.8]. 
Asynchronous cellular automata have been introduced in [94]. The 
transformations between different types of asynchronous automata have 
been studied in detail by Pighizzini [85]. The presentation of Sect. 7.4 
is from a lecture of Hoogeboom (Palermo 1996). The construction for 
triangulated dependence graphs is from Diekert and Muscholl [32]. It 
heavily uses the main idea from M?etivier [73], who developed this 
method for acyclic dependence graphs. Bertoni, Mauri, and Sabadini used 
in [7] a similar method for acyclic Petri nets, but the latter paper was 
not widely distributed. Bounded time-stamps are from [20].

8. Infinite Traces

8.1 Real Traces

An infinite word is a mapping u : N ?! ?. We can write u = u(0)u(1) ? ? 
? with u(i) 2 ?. The set of infinite words is denoted by ?!; hence ?1 = 
?? [ ?! is the set of finite and infinite words. The mapping 'G : ?? ?! 
G (?; D) from words to dependence graphs has a natural extension to ?1

Partial Commutation and Traces 63

For u = u(0)u(1) ? ? ? 2 ?! the dependence graph 'G (u) = [V; E; >=] is 
defined as follows: The vertex set is V = N with >=(i) = u(i). There is 
an arc (i; j) 2 E if and only if i < j and (u(i); u(j)) 2 D. The image 
'G (u) 2 G , u 2 ?1 is called real trace. The set of real traces is 
denoted by R(?; D). This set contains finite and infinite dependence 
graphs. For simplicity we write ' instead of 'G . Hence ' : ?1 ?! R(?; 
D) is a surjective mapping. A finitary language is a subset of M (?; I), 
i.e., a language over finite traces.

For a dependence graph g = [V; E; >=] we infer standard notations from 
the finite case. In particular, we can speak of alph(g), of g being 
connected, and of a decomposition into connected components. As usual, 
we write gIh, if alph(g) ? alph(h) ? I .

Let g = [V; E; >=] 2 G (?; D) and x 2 V be a vertex. By #x we mean the 
dependence graph being induced by the set fy 2 V j (y; x) 2 E?g. Thus, 
it is the dependence graph (having a unique maximal element), being 
induced by all nodes below or equal to x. By Prop. 6.1 we can write g = 
(#x)h for some uniquely determined h 2 G (?; D).

Remark 8.1. A dependence graph g = [V; E; >=] is a real trace, i.e., g = 
'(u) for some word u 2 ?1, if and only if #x is finite for all x 2 V . 
This property characterizes therefore R(?; D) ? G (?; D).

Having this notation, we may define the decomposition of a dependence 
graph into its real (standard) and transfinite part:

Definition 8.1. For a dependence graph g = [V; E; >=] 2 G (?; D) we 
define its real part Re(g) 2 R(?; D) to be the dependence graph being 
induced by the set fx 2 V j # x is finiteg. The transfinite part T r(g) 
2 G (?; D) is the dependence graph which is induced by the set fx 2 V j 
# x is infiniteg. The alphabet at infinity, alphinf(g) ? ?, is the set 
of labels

alphinf(g) = f>=(x) 2 ? j >=(x) appears infinitely often or #x is 
infiniteg:

The following proposition is obvious.

Proposition 8.1. Let g; h 2 R(?; D) be real traces. Then

alphinf(g) = f>=(x) 2 ? j >=(x) appears infinitely often g:

The product g ?h 2 G (?; D) is a real trace if and only if 
alphinf(g)?alph(h) ? I.

It is straightforward to define iterations and !-products for dependence 
graphs. Closing the family of rational languages over finite traces 
under the operation union, concatenation, Kleene-star, and !-product, we 
obtain the family of !-rational (or rational for short) dependence 
graphs Rat(G (?; D)). The family of rational real trace languages is 
defined by

Rat(R(?; D)) = fL ? R(?; D) j L 2 Rat(G (?; D))g:

Using Prop. 8.1 and well-known closure properties for the family of ! 
regular word languages Rat(?1) the following characterization can be 
shown.

64 Volker Diekert and Yves M?etivier

Proposition 8.2. The family of rational real trace languages is the 
smallest family containing Rat(M (?; I)) and being closed under union, 
concatenation with finitary languages on the left, Kleene-star and 
!-products over finitary languages.

Example 8.1. Let a; b; c 2 ?, (a; b) 2 I , (a; c) 2 D, t 2 M (?; I), and 
g 2 G (?; D). Then we have:

{ a!b! = (ab)! 2 Rat(R(?; D)).
{ a!c is not a real trace, Re(a!c) = a!, T r(a!c) = c, and alphinf(a!c) 
= fa; cg. Hence, alphinf(a!c) = alphinf(a!) if and only if a = c. { tg2 
2 R(?; D) if and only if g is finite.

Proposition 8.3. A real trace language L ? R(?; D) is rational if and 
only if it can be written as a finite union

L =
[

finite

RT!

over finitary rational trace languages R and T .

Guided by the notions on finitary languages we define the families of 
star-connected, c-rational, and star-free real trace languages. For 
star-connectedness: the Kleene-star and the !-product are allowed over 
finitary and connected languages, only.

For c-rational: the Kleene-star and the !-product are replaced by 
operations, where first we take the language of connected components and 
then apply the Kleene-star (!-product resp.) over this connected 
language.

For star-freeness: we start with the star-free finitary trace language. 
Then we take the closure under Boolean operations (with respect to R(?; 
D)) and under concatenation with finitary languages on the left. Neither 
Kleene-star nor !-product are allowed. It is easy to verify that for all 
A; B ? ? the set fg 2 R(?; D) j alph(g) ? A; alphinf(g) ? Bg is 
star-free. Note also that the language (ab)! is star-free, whether or 
not (a; b) 2 D.

In Sect. 6.2 we have defined first-order and monadic second-order 
sentences. Of course, being a dependence graph every real trace yields 
an interpretation for such a sentence.

Finally, we extend the notion of recognizability from infinite words to 
real traces. We say that a homomorphism ? : M (?; I) ?! S to a finite 
semigroup recognizes a real trace language L ? R(?; D), if for all 
infinite sequences s0s1s2 ? ? ? and t0t1t2 ? ? ? with ?(si) = ?(ti) for 
all i >= 0 we have the equivalence
s0s1s2 ? ? ? 2 L () t0t1t2 ? ? ? 2 L:

Definition 8.2. A real trace language L ? R(?; D) is called 
recognizable, if there exists some recognizing homomorphism ? : M (?; I) 
?! S to a finite semigroup S.


Partial Commutation and Traces 65

Let L ? R(?; D) be a real trace language. We define the syntactic 
congruence ?L? M (?; I) ? M (?; I) by setting u ?L v for u; v 2 M (?; I) 
if and only if for all x; y; z 2 M (?; I) we have:

xuyz! 2 L () xvyz! 2 L

x(uy)! 2 L () x(vy)! 2 L

As for infinite words we have the following proposition:

Proposition 8.4. A real trace language L ? R(?; D) is recognizable if 
and only if we have both, the syntactic congruence ?L is of finite index 
and the syntactic homomorphism ?L : M (?; I) ?! M (?; I)=?L recognizes 
L.

Proposition 8.5. Let ' : ?1 ?! R(?; D) be the canonical mapping, L ? 
R(?; D) be a real trace language, and K = '?1(L). Then the following 
assertions hold:

i) The syntactic monoids ??=?K and M (?; I)=?K are canonically 
isomorphic. ii) The syntactic homomorphism ?K : ?? ?! ??=?K recognizes K 
if and only if ?L : M (?; I) ?! M (?; I)=?L recognizes L.

Corollary 8.1. A real trace language L ? R(?; D) is recognizable if and 
only if '?1(L) ? ?1 is recognizable.

A word language K ? ?1 is called closed, if K = '?1'(K).

Proposition 8.6. A recognizable word language K ? ?1 is closed if and 
only if ab ?K ba for all (a; b) 2 I.

The implication \=)" in the proposition above is trivial and holds for 
every closed language. Unlike the finitary case the converse is less 
obvious. The proof uses Ramsey-factorization and the fact that the 
language K is recognized by the syntactic homomorphism ?K : ?? ?! ??=?K 
. The formal proof is left to the reader. The proposition above yields a 
decidability result immediately.

Corollary 8.2. It is decidable whether a recognizable word language is 
closed.

Bringing together the different notions introduced so far, we can state 
the following theorem.

Theorem 8.1. Let ' : ?1 ?! R(?; D) be the canonical mapping, L ? R(?; D) 
be real trace language, and ?L : M (?; I) ?! M (?; I)=?L be the 
syntactic homomorphism. Then the following assertions are equivalent.

i) L is a recognizable subset of R(?; D).
ii) '?1(L) is a recognizable subset of ?1.
iii) The syntactic congruence ?L is of finite index and ?Lrecognizes L. 
iv) L is star-connected.


66 Volker Diekert and Yves M?etivier

v) L is c-rational.
vi) L is definable in monadic second-order logic.
vii) The language L can be written as a finite union

L =
[

finite
RT!;

where R and T are finitary recognizable trace languages such that T = T 
?.

The first-order counterpart can be stated as follows:

Theorem 8.2. Under the same assumptions as above, the following 
assumptions are equivalent:

i) L is star-free.
ii) '?1(L) is star-free.
iii) The syntactic monoid M (?; I)= ?L is finite, aperiodic, and ?L 
recognizes L.
iv) L is definable in first-order logic.
v) The language L can be written as a finite union

L =
[

finite
RT!;

where R and T are finitary star-free languages such that T = T ?.

8.2 Asynchronous Büchi- and Muller Automata

A non-deterministic finite asynchronous cellular automaton A is a tuple 
A = (Q; s; (ffia)a2? ; T ) where Q =
Q

a2?
Qa is the set of global states, s = (sa)a2?

is the initial state, ffia ?
Q

b2D(a)
Qb

!

? Qa is the local transition relation,

and T = fT1; : : : ; Tng is the acceptance table for runs, and each Ti 
satisfies Ti =
Q

a2?
Ti;a for some Ti;a ? Qa.

The automaton is called deterministic, if the local transition relations 
ffia are partially defined functions.
A run r of A on a real trace g = [V; E; >=] is a labeling function r : V 
?! _S
a2?Qa satisfying the following conditions:

i) If >=(x) = a for x 2 V , then we have r(x) 2 Qa.
ii) Let x 2 V , >=(x) = a, and r(x) = qa. For each b 2 D(a) let qb 
either be r(xb), if there exists the maximal vertex xb with (xb; x) 2 E? 
and >=(xb) = b, or let qb = sb (the b-component of the initial state) 
otherwise. Then we have ?
(qb)b2D(a); qa
?
2 ffia:


Partial Commutation and Traces 67

We define the infinite behavior of a run r on g as follows:

inf(r) =
n
q 2 Q j q = (qa)a2? such that for each a 2 ? :

either r?1(qa) contains infinitely many vertices
or it contains the maximal vertex with label a,

or, if a =
2 alph(g), then qa = sa
o
:

For A a Büchi- and a Muller acceptance condition are defined. 
Accordingly A is called a Büchi- or Muller automaton. A real trace g 2 
R(?; D) is Büchiaccepted if there exist a run r on g and some Ti 2 T 
such that Ti ? inf(r). It is Muller-accepted if we demand equality Ti = 
inf(r) for some Ti 2 T .

Although the Muller acceptance is more powerful, it is easy to see that 
the non-deterministic models are equivalent in the sense that they lead 
to the same class of accepted languages.

Theorem 8.3. Let L ? R(?; D) be a real trace language. Then the 
following assertions are equivalent:

i) L is recognizable.
ii) L is accepted by some non-deterministic finite asynchronous cellular 
Büchi-automaton.
iii) L is accepted by some non-deterministic finite asynchronous 
cellular Muller-automaton.
iv) L is accepted by some deterministic finite asynchronous cellular 
Mullerautomaton.

Remark 8.2. The equivalence i) , iv) above generalizes McNaughton's 
Theorem to real traces. The original proof in [31] transforms via an 
implicit double exponential algorithm a given non-deterministic 
Büchi-automaton for a closed word language into a deterministic finite 
asynchronous cellular Mullerautomaton. This proof does not use the 
equivalence i) , ii). Therefore the acceptance of a recognizable 
language by some non-deterministic finite asynchronous cellular 
Büchi-automaton can be viewed as a corollary. But for this fact a much 
simpler and direct construction exists by [50].

8.3 Complex Traces

There is no convenient way to define a concatenation on real traces, in 
general. To see this consider the following two axioms:

I a!b! = a! for (a; b) 2 D
II a!b! 6= a! for (a; b) 2 I

There is an associative operation satisfying I and II if and only if D 
is transitive. Indeed: If D is transitive, then M (?; I) = ?? 1 ? ? ? ? 
? ??
k is a direct
product of free monoids. The sets ?1
i are monoids with a right-absorbent
multiplication if the left-hand side is an infinite word. This 
definition yields

68 Volker Diekert and Yves M?etivier

a concatenation on R(?; D) = ?1
1 ? ? ? ? ??1
k satisfying I and II. If D is not
transitive then consider a!b!c! with (a; b); (b; c) 2 D, a; b; c 
pairwise distinct, and (a; c) 2 I . An operation satisfying I and II is 
never associative:

(a!b!)c! = a!c! 6= a! = a!b! = a!(b!c!)

On the other hand, G (?; D) is a monoid and we may consider the greatest 
congruence respecting real parts. The quotient monoid by this congruence 
is called the monoid C (?; D) of complex traces . This monoid has a very 
convenient and concrete characterization.

Theorem 8.4. Let ?C denote the greatest congruence on G (?; D) 
satisfying Re(g) = Re(h) for all g ?C h. Then for all g; h 2 G (?; D) it 
holds:

g ?C h () (Re(g) = Re(h) and D(alphinf(g)) = D(alphinf(h))) :

Hence, the quotient monoid G (?; D)= ?C can be identified with the 
following set:

C (?; D) = f(Re(g); D(alphinf(g))) 2 R(?; D) ? P(?) j g 2 G (?; D)g:

By definition C (?; D) is a monoid and the concatenation is inherited 
from the concatenation of dependence graphs. It is necessary (otherwise 
the whole formalism would be rather useless) to have an explicit 
formula. First, we need a few more notations. Let g 2 G (?; D) be a 
dependence graph and A ? ? be a subset. We define ?A(g) as the maximal 
real prefix g being independent of A. If <= denotes the prefix ordering 
on G (?; D), then it is easy to see that every directed set of real 
traces has a real least upper bound. Therefore we have

?A(g) =
G
fp 2 M (?; I) j p <= g and alph(p) ?A ? Ig 2 R(?; D):

If p is a prefix of g, we denote by p?1g the unique dependence graph 
such that p(p?1g) = g, and by D(p?1g) we denote the set D(alph(p?1g)). 
We define

öA(g) = D(alphinf(g)) [ D(?A(g)?1g)
=
T
fD(p?1g) j p 2 M (?; I); p <= g; and alph(p) ?A ? Ig:

Note that we always have D(alphinf(g)) ? öA(g). Obviously, D(A) = D(A0) 
implies ?A(g) = ?A0(g) and öA(g) = öA0(g) for all g 2 G (?; D). The 
following formula yields the concatenation of complex traces:

(r; D(A)) ? (s; D(B)) = (r?A(s); öA(s) [ D(A [ B)):

The formula above is fundamental for the calculus on complex traces. 
Once one has defined when a complex trace is connected (there are 
several suitable choices, take any of them), it is straightforward to 
define the notion of rational, star-connected, and c-rational complex 
trace languages. We can go

Partial Commutation and Traces 69

even further and define an ff-product of a trace language for every 
ordinal ff. Details are left to the reader.
There are also many equivalent definitions of recognizable complex trace 
languages. We content ourselves with the following

Definition 8.3. A complex trace language L ? C (?; D) is called 
recognizable, if the language of real traces

LA = fr 2 R(?; D) j (r; D(A)) 2 Lg

is recognizable for all A ? ?.

Example 8.2. Let D = ??? be full. Then C (?; D) = ?1. For L ? ?1 we have 
L; = L\?? and L? = L\?!. The language L is recognizable if both L; ? ?? 
and L? ? ?! are recognizable in the classical sense.

Theorem 8.5. Let L ? C (?; D) be a complex trace language. Then the 
following assertions are equivalent:

i) L is recognizable.
ii) L is star-connected.
iii) L is c-rational.

8.4 Topological Properties and the Domain of ffi-Traces

Consider the following two functions from M (?; I) ? M (?; I) to N [ 
f1g:

`R(u; v) = supfn 2 N j 8p 2 M (?; I); jpj <= n : p <= u , p <= vg

`C (u; v) = supfn 2 N j 8p 2 M (?; I); jpj < n : D(p?1u) = D(p?1v)g

Note that D(p?1u) ? ? is defined only if p <= u. Thus, the equation 
D(p?1u) = D(p?1v) means that either p is a prefix of both traces u and v 
or of none. The functions `R and `C yield two ultra-metrics on M (?; I):

dR(u; v) = 2?`R(u;v)

dC (u; v) = 2?`C(u;v):

Theorem 8.6. The completion of the metric space (M (?; I); dR) is R(?; 
D); the completion of (M (?; I); dC ) is C (?; D). Both spaces are 
compact and totally disconnected, containing the set of finite traces M 
(?; I) as an open and discrete subspace.

The concatenation of (M (?; I); dC ) is uniformly continuous; its 
continuous extension to C (?; D) coincides with the concatenation 
defined explicitly above. The concatenation of (M (?; I); dR) is 
uniformly continuous if and only if D is transitive (if and only if dR 
and dC are equivalent metrics).

70 Volker Diekert and Yves M?etivier

As it is well-known from the sequential calculus, the concatenation is 
not monotone with respect to the prefix ordering, i.e., a <= ab, but we 
do not have ac <= abc, in general. In the sequential calculus the 
solution is to introduce a special symbol for termination. Here, we 
provide some alphabetic information about the set of other actions which 
can be executed in parallel before waiting for termination of the 
process. Formally, we add to a (finite) trace a second component of the 
form D(A) with A ? ?. The semantics is that, before termination, the 
process may perform in the future only actions a 2 ? such that D(a) ? 
D(A). Therefore the semantics of D(A) = ? is that everything is 
possible; the semantics of D(A) = ; is explicit termination. Note that 
for the full dependency D = ? ? ? the whole information reduces to 
explicit termination, since there are no other sets D(A) than ? or ;. We 
define a partially ordered monoid M ffi(?; I) as follows (the sign ffi 
refers to dependence information):

M ffi(?; D) = f(u; D(A)) j u 2 M (?; I); A ? ?g:

It is the monoid with the concatenation

(u; D(A)) ? (v; D(B)) = (u?A(v); öA(v) [ D(A [ B)):

The approximation ordering v is defined by

(u; D(A)) v (v; D(B)) () u <= v and D(u?1v) [ D(B) ? D(A):

Example 8.3.

(u; ;)(v; D(B)) = (uv; D(B));

(u; ?)(v; D(B)) = (u; ?);

(1; ?) v (u; D(A [ alph(v))) v (uv; D(A n alph(v))) v (uv; ;);

(1; ;) is the neutral element, and (1; ?) is the bottom element being 
rightabsorbent.

It is clear that M (?; I) is a submonoid of M ffi(?; D). The canonical 
embedding is u 7?! (u; ;). If D = ? ?? is full, then using a new symbol 
p
for explicit termination we have a canonical identification M ffi(?; D) 
= ?? [??p
.
We identify u 2 ?? with (u; ;) and u
p
with (u; ?).
The set of ffi-traces Fffi (?; D) is defined by

Fffi (?; D) = f(u; D(A)) j u 2 R(?; D); alphinf(u) ? Ag:

The same formulae for the concatenation and the approximation ordering 
apply. The concatenation is well-defined since we demand alphinf(u) ? A 
for (u; D(A)) 2 Fffi (?; D).
The various spaces we have considered so far can be put into a commuting 
diagram of inclusions.


Partial Commutation and Traces 71

M (?; I) ? - M ffi(?; D)

R(?; D)
?

\

? - C (?; D) ? - Fffi (?; D)
?

\

The following theorem states that Fffi (?; D) with the approximation 
ordering is in fact a good semantic domain.

Theorem 8.7. The set of ffi-traces Fffi (?; D) with the ordering v is a 
complete partial order (CPO). The concatenation is continuous in both 
arguments, i.e.,

(
G
X) ? (
G
Y ) =
G
(X ? Y )

for all directed subsets X;Y ? Fffi (?; D). The CPO Fffi (?; D) is 
coherently complete and algebraic. In particular, it is a Scott domain. 
The subset of compact (or finite) elements is M ffi(?; D).

For Fffi (?; D) the Scott-topology and its refinement the 
Lawson-topology are defined. The Lawson-topology is induced by the 
extension of the metric dC from complex traces to ffi-traces. Formally, 
let dffi(x; y) = 2?`ffi(x;y) and

`ffi((u; D(A)); (v; D(B))) = supf n 2 N j 8p 2 M (?; I); jpj < n : 
D(p?1u) [ D(A) = D(p?1v) [ D(B) g:

By general facts about Lawson-topology [54] we obtain a compact and 
totally disconnected space. (In particular Fffi (?; D) is a complete 
ultra-metric space.) Every compact and totally disconnected space is a 
projective limit. We make this explicit. For each n >= 0 and a trace u 2 
M (?; I) let u[n] = F
fp <= u j jpj <= ng, i.e., u[n] is the least upper bound of the prefixes 
of length n in u. Using this notations we define finite and aperiodic 
monoids Mn and Fn as follows:

Mn = f(u[n]; D((u[n])?1u)) j u 2 M (?; I)g

Fn = f(u[n]; D(A)) j u 2 M (?; I); A ? ?g

The multiplication is given in both monoids by the same formula:

(u; D(A)) ? (v; D(B)) = ((u?A(v))[n]; D(((u?A(v))[n])?1uv) [ D(A [ B)):

It is an exercise to verify that he formula is well-defined. It also 
shows that Mn is a submonoid of Fn and that for all n >= 0 we have a 
canonical homomorphism

n : M (?; I) ?! Fn; u 7?! (u[n]; D((u[n])?1u))

The image of n is exactly Mn. For each m >= n there are surjective 
homomorphisms 0 m;n and m;n such that the following diagram commutes:


72 Volker Diekert and Yves M?etivier

M (?; I)
m- Mm ? - Fm

@
@
@
@
@

n

R
Mn
?

0
m;n

? - Fn
?

m;n

It is clear that this leads to projective systems. Recall the definition

lim
?
Mn = f(xn)n>=0 2
Y

n>=0
Mn j 0
m;n(xm) = xn for all m >= ng

lim
?
Fn = f(xn)n>=0 2
Y

n>=0
Fn j m;n(xm) = xn for all m >= ng

Being finite we endow the sets Mn;Fn with the discrete topology. The 
projective limits are then compact (by Tychonov's Theorem) and totally 
disconnected. They are topological monoids and the multiplication is 
uniformly continuous. We have just constructed the corresponding monoids 
of complex and ffi-traces with the Lawson-topology. The final theorem 
reflects most of what we have done so far for complex and for ffi-traces 
in two lines.

Theorem 8.8. We have the following equalities of topological monoids:

C (?; D) = lim
?
Mn

Fffi (?; D) = lim
?
Fn:

8.5 Bibliographical Remarks and Further Reading

The theory of infinite traces has its origins in the mid eighties. Fl?e 
and Roucairol [44, 45] considered the problem of serializability of 
iterated transactions in data bases. Their definition of an infinite 
trace is equivalent to our definition of an infinite real trace. Best 
and Devillers [9] defined the behavior of Petri nets by an equivalence 
relation on ?1. This equivalence relation yields real traces. A 
definition of a real trace as a prefix-closed and directed subset of 
real traces and its characterization by dependence graphs is given in a 
survey by Mazurkiewicz [70]. This characterization is the basis for an 
investigation of the poset properties, as e.g. studied by Gastin and 
Rozoy in [52]. Kwiatkowska [66] introduced real traces as a suitable 
model for distributed systems to reason about fairness, liveness, and 
safety properties. She also showed that the set R(?; D) with the 
prefix-metric dR yields a compact ultra-metric space. Bonizzoni, Mauri, 
and Pighizzini gave a Foata normal form for infinite traces [10].

The theory of recognizable real trace languages has been initiated by 
Gastin [47, 48]. The generalization of the 
Kleene-Büchi-Ochma?nski-Theorem to real traces (Thm. 8.1) is due to 
Gastin, Petit, and Zielonka [51]. (It has been

Partial Commutation and Traces 73

generalized to complex trace languages in [30].) A construction of a 
deterministic asynchronous Muller automaton accepting a given 
recognizable real trace language has been exhibited by Diekert and 
Muscholl in [31]. A complementation construction for asynchronous 
cellular Büchi automata based on Klarlund's progress measure technique 
has been presented by Muscholl [77]. As a preliminary result, a 
determinization procedure for asynchronous (cellular) automata for 
finitary trace languages is provided (see also Klarlund et al. [65]). 
Logical definability on infinite traces is investigated in [42]. 
Together, the results mentioned above provide a satisfactory picture and 
a rather complete generalization of regular infinitary word languages to 
real traces, see also [78].

A basic difference between ?1 and R(?; D) is however that a natural 
associative operation of concatenation cannot be defined for real 
traces, in general. This led Diekert to the notion of complex trace 
[27]. The results about rational and recognizable complex trace 
languages have been established in [30]. A theory of ffi-traces as a 
natural generalization of this concept has been proposed in [29].

There are other generalizations of the theory of finite traces we have 
not dealt with in this chapter. For example, it is very natural to 
consider asymmetric (in-)dependencies. This leads to the notions of 
semi-trace and of semi-commutation initiated successfully by Clerbout 
and Latteux [15, 16, 17, 18]. For an overview on semi-commutations given 
by Clerbout, Latteux, and Roos we refer to [34, Chap. 12]. A 
generalization of semi-traces based on the pomset model of Pratt [86] 
has been proposed in [28].

Another approach to express dynamic behavior is due to investigations of 
Panangaden and Stark [83] who introduced the notion of trace automata. 
Close to this is the notion of concurrent automata being transition 
systems where the dependence relation may vary with the state and their 
monoids of computations due to Droste [35]. Many important theorems of 
trace theory have been generalized to these monoids, see [38].

References

1. IJsbrand Jan Aalbersberg and Hendrik Jan Hoogeboom. Characterizations 
of the decidability of some problems for regular trace languages. 
Mathematical Systems Theory, 22:1{19, 1989.
2. IJsbrand Jan Aalbersberg and Emo Welzl. Trace languages defined by 
regular string languages. R.A.I.R.O. | Informatique Th?eorique et 
Applications, 20:103{119, 1986.
3. Anatolij V. Anisimov and Donald E. Knuth. Inhomogeneous sorting. 
International Journal of Computer and Information Sciences, 8:255{260, 
1979. 4. Jean Berstel. Transductions and context-free languages. Teubner 
Studienbücher, Stuttgart, 1979.
5. Jean Berstel and Dominique Perrin. Theory of Codes. Pure and Applied 
Mathematics; 117. Academic Press, Orlando, Florida, 1985.

74 Volker Diekert and Yves M?etivier

6. Alberto Bertoni, Giancarlo Mauri, and Nicoletta Sabadini. A hierarchy 
of regular trace languages and some combinatorial applications. In A. 
Ballester, D. Cardus, and E. Trillas, editors, Proceedings of the 2nd 
World Conf. on Mathematics at the Service of Man, Las Palmas (Canary 
Island) Spain, pages 146{153. Universidad Politecnica de Las Palmas, 
1982. 7. Alberto Bertoni, Giancarlo Mauri, and Nicoletta Sabadini. 
Concurrency and commutativity. Technical report, Instituto di 
Cibernetica, Universit?a di Milano, 1983. Presented at the Workshop on 
Petri nets, Varenna (Italy), 1982. 8. Alberto Bertoni, Giancarlo Mauri, 
and Nicoletta Sabadini. Unambiguous regular trace languages. In G. 
Demetrovics, J. Katona and Arto Salomaa, editors, Proceedings of the 
Coll. on Algebra, Combinatorics and Logic in Computer Science, volume 42 
of Colloquia Mathematica Soc. J. Bolyai, pages 113{123. North Holland, 
Amsterdam, 1985.
9. Eike Best and Raymond Devillers. Sequential and concurrent behaviour 
in Petri net theory. Theoretical Computer Science, 55:87{136, 1987.
10. Paola Bonizzoni, Giancarlo Mauri, and Giovanni Pighizzini. About 
infinite traces. In Volker Diekert, editor, Proceedings of the ASMICS 
workshop Free Partially Commutative Monoids, Kochel am See, Oktober 
1989, Report TUM- I9002, Technical University of Munich, pages 1{10, 
1990.
11. V?eronique Bruy?ere and Clelia De Felice. Trace codings. In E.W. 
Mayr and C. Puech, editors, Proceedings of the 12th Annual Symposium on 
Theoretical Aspects of Computer Science (STACS'95), 1995, number 900 in 
Lecture Notes in Computer Science, pages 373{384, Berlin-Heidelberg-New 
York, 1995. Springer. 12. V?eronique Bruy?ere, Clelia De Felice, and 
Giovanna Guaiana. Coding with traces. In P. Enjalbert, E.W. Mayr, and K. 
W. Wagner, editors, Proceedings of the 11th Annual Symposium on 
Theoretical Aspects of Computer Science (STACS'94), 1994, number 775 in 
Lecture Notes in Computer Science, pages 353{364, Berlin-Heidelberg-New 
York, 1994. Springer.
13. Pierre Cartier and Dominique Foata. Probl?emes combinatoires de 
commutation et r?earrangements. Number 85 in Lecture Notes in 
Mathematics. Springer, Berlin-Heidelberg-New York, 1969.
14. Marek Chrobak and Wojciech Rytter. Unique decipherability for 
partially commutative alphabets. Fundamenta Informaticae, X:323{336, 
1987. 15. Mireille Clerbout. Commutations Partielles et Familles de 
Langages. Th?ese, Universit?e des Sciences et Technologies de Lille 
(France), 1984. 16. Mireille Clerbout and Michel Latteux. Partial 
commutations and faithful rational transductions. Theoretical Computer 
Science, 34:241{254, 1984. 17. Mireille Clerbout and Michel Latteux. 
Semi-Commutations. Information and Computation, 73:59{74, 1987.
18. Mireille Clerbout, Michel Latteux, and Yves Roos. Decomposition of 
partial commutations. In M. S. Paterson, editor, Proceedings of the 17th 
International Colloquium on Automata, Languages and Programming 
(ICALP'90), Warwick (England) 1990, number 443 in Lecture Notes in 
Computer Science, pages 501{ 511, Berlin-Heidelberg-New York, 1990. 
Springer.
19. Robert Cori and Yves M?etivier. Recognizable subsets of some 
partially abelian monoids. Theoretical Computer Science, 35:179{189, 
1985.
20. Robert Cori, Yves M?etivier, and Wies law Zielonka. Asynchronous 
mappings and asynchronous cellular automata. Information and 
Computation, 106:159{ 202, 1993.
21. Robert Cori and Dominique Perrin. Automates et commutations 
partielles. R.A.I.R.O. | Informatique Th?eorique et Applications, 
19:21{32, 1985. 22. Bruno Courcelle. The monadic second-order logic of 
graphs X: linear orderings. Theoretical Computer Science, 1996. to 
appear.


Partial Commutation and Traces 75

23. Volker Diekert. Transitive orientations, Möbius functions and 
complete semi- Thue systems for free partially commutative monoids. In 
T. Lepistö et al., editors, Proceedings of the 15th International 
Colloquium on Automata, Languages and Programming (ICALP'88), Tampere 
(Finland) 1988, number 317 in Lecture Notes in Computer Science, pages 
176{187, Berlin-Heidelberg-New York, 1988. Springer.
24. Volker Diekert. Combinatorics on Traces. Number 454 in Lecture Notes 
in Computer Science. Springer, Berlin-Heidelberg-New York, 1990. 25. 
Volker Diekert. Research topics in the theory of free partially 
commutative monoids. Bulletin of the European Association for 
Theoretical Computer Science (EATCS), 40:479{491, Feb 1990.
26. Volker Diekert. Möbius functions and confluent semi-commutations. 
Theoretical Computer Science, 108:25{43, 1993.
27. Volker Diekert. On the concatenation of infinite traces. Theoretical 
Computer Science, 113:35{54, 1993. Special issue STACS'91.
28. Volker Diekert. A partial trace semantics for Petri nets. 
Theoretical Computer Science, 134:87{105, 1994. Special issue of ICWLC 
92, Kyoto (Japan). 29. Volker Diekert and Paul Gastin. A domain for 
concurrent termination: A generalization of Mazurkiewicz traces. In 
Zolt?an Fülöp and Ferenc G?ecseg, editors, Proceedings of the 22nd 
International Colloquium on Automata, Languages and Programming 
(ICALP'95), Szeged (Hungary) 1995, number 944 in Lecture Notes in 
Computer Science, pages 15{26. Springer, 1995.
30. Volker Diekert, Paul Gastin, and Antoine Petit. Rational and 
recognizable complex trace languages. Information and Computation, 
116:134{153, 1995. 31. Volker Diekert and Anca Muscholl. Deterministic 
asynchronous automata for infinite traces. Acta Informatica, 31:379{397, 
1994. A preliminary version was presented at STACS'93, Lecture Notes in 
Computer Science 665 (1993). 32. Volker Diekert and Anca Muscholl. A 
note on M?etivier's construction of asynchronous automata for 
triangulated graphs. Fundamenta Informaticae, to appear 1996. Special 
issue on Formal Language Theory. 33. Volker Diekert, Anca Muscholl, and 
Klaus Reinhardt. On codings of traces. In E.W. Mayr and C. Puech, 
editors, Proceedings of the 12th Annual Symposium on Theoretical Aspects 
of Computer Science (STACS'95), 1995, number 900 in Lecture Notes in 
Computer Science, pages 385{396, Berlin-Heidelberg-New York, 1995. 
Springer.
34. Volker Diekert and Grzegorz Rozenberg, editors. The Book of Traces. 
World Scientific, Singapore, 1995.
35. Manfred Droste. Concurrent automata and domains. International 
Journal of Foundations of Computer Science, 3:389{418, 1992.
36. Manfred Droste. A Kleene Theorem for recognizable languages over 
concurrency monoids. In Serge Abiteboul and Eli Shamir, editors, 
Proceedings of the 21st International Colloquium on Automata, Languages 
and Programming (ICALP'94), Jerusalem (Israel) 1994, number 820 in 
Lecture Notes in Computer Science, pages 388{398, 1994. 37. Manfred 
Droste. Aperiodic languages over concurrency monoids. 1995. submitted. 
38. Manfred Droste. Recognizable languages in concurrency monoids. To 
appear in Theoretical Computer Science, 1995.
39. Manfred Droste and Dietrich Kuske. Logical definability of 
recognizable and aperiodic languages in concurrency monoids. In 
Proceedings of the CSL'95 , Paderborn, Lecture Notes in Computer 
Science, Berlin-Heidelberg-New York, 1996. Springer. To appear.


76 Volker Diekert and Yves M?etivier

40. Christine Duboc. Commutations dans les monö?des libres: un cadre 
th?eorique pour l'?etude du parallelisme. Th?ese, Facult?e des Sciences 
de l'Universit?e de Rouen, 1986.
41. Werner Ebinger. Charakterisierung von Sprachklassen unendlicher 
Spuren durch Logiken. Dissertation, Institut für Informatik, Universität 
Stuttgart, 1994. 42. Werner Ebinger and Anca Muscholl. Logical 
definability on infinite traces. Theoretical Computer Science, 
154:67{84, 1996. A preliminary version appeared in Proceedings of the 
20th International Colloquium on Automata, Languages and Programming 
(ICALP'93), Lund (Sweden) 1993, Lecture Notes in Computer Science 700, 
1993.
43. Samuel Eilenberg and Marcel Paul Schützenberger. Rational sets in 
commutative monoids. Journal of Algebra, 13:173{191, 1969. 44. 
Marie-Paule Fl?e and G?erard Roucairol. On serializability of iterated 
transactions. In Proceedings of the 15th ACM SIGACT-SIGOPS Symp. on 
Princ. of Distrib. Comp., Ottawa (1982), pages 194 { 200, 1982.
45. Marie-Paule Fl?e and G?erard Roucairol. Fair serializability of 
iterated transactions using fifo-nets. In Grzegorz Rozenberg, editor, 
Advances in Petri Nets, number 188 in Lecture Notes in Computer Science, 
pages 154{168. Springer, Berlin-Heidelberg-New York, 1985.
46. Michel Fliess. Matrices de Hankel. J. Math. Pures et Appl., 
53:197{224, 1974. 47. Paul Gastin. Infinite traces. In I. Guessarian, 
editor, Proceedings of the Spring School of Theoretical Computer Science 
on Semantics of Systems of Concurrent Processes, number 469 in Lecture 
Notes in Computer Science, pages 277{308, Berlin-Heidelberg-New York, 
1990. Springer.
48. Paul Gastin. Recognizable and rational trace languages of finite and 
infinite traces. In Christian Choffrut et al., editors, Proceedings of 
the 8th Annual Symposium on Theoretical Aspects of Computer Science 
(STACS'91), Hamburg 1991, number 480 in Lecture Notes in Computer 
Science, pages 89{104, Berlin- Heidelberg-New York, 1991. Springer.
49. Paul Gastin, Edward Ochma?nski, Antoine Petit, and Brigitte Rozoy. 
Decidability of the Star problem in A? ? fbg?. Information Processing 
Letters, 44:65{71, 1992.
50. Paul Gastin and Antoine Petit. Asynchronous automata for infinite 
traces. In W. Kuich, editor, Proceedings of the 19th International 
Colloquium on Automata, Languages and Programming (ICALP'92), Vienna 
(Austria) 1992, number 623 in Lecture Notes in Computer Science, pages 
583{594, Berlin- Heidelberg-New York, 1992. Springer.
51. Paul Gastin, Antoine Petit, and Wies law Zielonka. An extension of 
Kleene's and Ochma?nski's theorems to infinite traces. Theoretical 
Computer Science, 125:167{204, 1994. A preliminary version was presented 
at ICALP'91, Lecture Notes in Computer Science 510 (1991).
52. Paul Gastin and Brigitte Rozoy. The poset of infinitary traces. 
Theoretical Computer Science, 120:101{121, 1993.
53. Alan Gibbons and Wojciech Rytter. On the decidability of some 
problems about rational subsets of free partially commutative monoids. 
Theoretical Computer Science, 48:329{337, 1986.
54. Gerhard Gierz, Karl Heinrich Hofmann, Klaus Keimel, Jimmie D. 
Lawson, Michael W. Mislove, and Dana S. Scott. A Compendium of 
Continuous Lattices. Springer, Berlin-Heidelberg-New York, 1980.
55. Seymour Ginsburg and Edwin H. Spanier. Semigroups, Presburger 
formulas and languages. Pacific Journal of Mathematics, 16(2):285{296, 
1966. 56. Martin C. Golumbic. Algorithmic Graph Theory and Perfect 
Graphs. Academic Press, New York, 1980.


Partial Commutation and Traces 77

57. Sheila A. Greibach. The undecidability of the ambiguity problem for 
minimal linear grammars. Information and Control, 6:119{125, 1963.
58. Giovanna Guaiana, Antonio Restivo, and Sergio Salemi. Star-free 
trace languages. Theoretical Computer Science, 97:301{311, 1992. A 
preliminary version was presented at STACS'91, Lecture Notes in Computer 
Science 480 (1991). 59. Kosaburo Hashiguchi. Limitedness theorem on 
finite automata with distance functions. Journal of Computer and System 
Sciences, 24:233{244, 1982. 60. Kosaburo Hashiguchi. Recognizable 
closures and submonoids of free partially commutative monoids. 
Theoretical Computer Science, 86:233{241, 1991. 61. Hendrik Jan 
Hoogeboom and Anca Muscholl. The code problem for traces { improving the 
boundaries. Submitted for publication., 1995.
62. Günter Hotz and Volker Claus. Automatentheorie und Formale Sprachen, 
Band III. Bibliographisches Institut, Mannheim, 1972.
63. Oscar H. Ibarra. Reversal-bounded multicounter machines and their 
decision problems. Journal of the Association of Computing Machinery, 
25(1):116{133, 1978.
64. Robert M. Keller. Parallel program schemata and maximal parallelism 
I. Fundamental results. Journal of the Association of Computing 
Machinery, 20(3):514{537, 1973.
65. Nils Klarlund, Madhavan Mukund, and Millind Sohoni. Determinizing 
asynchronous automata. In Serge Abiteboul and Eli Shamir, editors, 
Proceedings of the 21st International Colloquium on Automata, Languages 
and Programming (ICALP'94), Jerusalem (Israel) 1994, number 820 in 
Lecture Notes in Computer Science, pages 130{141, 1994.
66. Marta Z. Kwiatkowska. A metric for traces. Information Processing 
Letters, 35:129{135, 1990.
67. Leslie Lamport. Time, clocks, and the ordering of events in a 
distributed system. Communications of the Association of Computing 
Machinery, 21:558{ 564, 1978.
68. Gennadi?? Semjonovich Makanin. The problem of solvability of 
equations in free semigroups. Math. USSR Izvestiya, 21:483{546, 1983.
69. Antoni Mazurkiewicz. Concurrent program schemes and their 
interpretations. DAIMI Rep. PB 78, Aarhus University, Aarhus, 1977.
70. Antoni Mazurkiewicz. Trace theory. In W. Brauer et al., editors, 
Petri Nets, Applications and Relationship to other Models of 
Concurrency, number 255 in Lecture Notes in Computer Science, pages 
279{324, Berlin-Heidelberg-New York, 1987. Springer.
71. Yves M?etivier. On recognizable subsets of free partially 
commutative monoids. In L. Kott, editor, Proceedings of the 13th 
International Colloquium on Automata, Languages and Programming 
(ICALP'86), Rennes (France) 1986, number 226 in Lecture Notes in 
Computer Science, pages 254{264, Berlin- Heidelberg-New York, 1986. 
Springer.
72. Yves M?etivier. Une condition suffisante de reconnaissabilit?e dans 
un monö?de partiellement commutatif. R.A.I.R.O. | Informatique 
Th?eorique et Applications, 20:121{127, 1986. 73. Yves M?etivier. An 
algorithm for computing asynchronous automata in the case of acyclic 
non-commutation graph. In Th. Ottmann, editor, Proceedings of the 14th 
International Colloquium on Automata, Languages and Programming 
(ICALP'87), Karlsruhe (FRG) 1987, number 267 in Lecture Notes in 
Computer Science, pages 226{236, Berlin-Heidelberg-New York, 1987. 
Springer. 74. Yves M?etivier. Contribution ?a l'?etude des monö?des de 
commutations. Th?ese d'?etat, 1987. Universit?e Bordeaux I.


78 Volker Diekert and Yves M?etivier

75. Yves M?etivier and Edward Ochma?nski. On lexicographic 
semi-commutations. Information Processing Letters, 26:55{59, 1987/88.
76. Yves M?etivier, Gw?enäel Richomme, and Pierre-Andr?e Wacrenier. 
Computing the closure of sets of words under partial commutations. In 
Zolt?an Fülöp and Ferenc G?ecseg, editors, Proceedings of the 22nd 
International Colloquium on Automata, Languages and Programming 
(ICALP'95), Szeged (Hungary) 1995, number 944 in Lecture Notes in 
Computer Science, pages 75{86. Springer, 1995. 77. Anca Muscholl. On the 
complementation of Büchi asynchronous cellular automata. In Serge 
Abiteboul and Eli Shamir, editors, Proceedings of the 21st International 
Colloquium on Automata, Languages and Programming (ICALP'94), Jerusalem 
(Israel) 1994, number 820 in Lecture Notes in Computer Science, pages 
142{153. Springer, 1994. 78. Anca Muscholl. Über die Erkennbarkeit 
unendlicher Spuren. Teubner, 1996. 79. Anca Muscholl and Holger 
Petersen. A note on the commutative closure of star-free languages. 
Information Processing Letters, 57:71{74, 1996. 80. Edward Ochma?nski. 
Regular behaviour of concurrent systems. Bulletin of the European 
Association for Theoretical Computer Science (EATCS), 27:56{67, Oct 
1985.
81. Edward Ochma?nski. On morphisms of trace monoids. In Robert Cori and 
M. Wirsing, editors, Proceedings of the 5th Annual Symposium on 
Theoretical Aspects of Computer Science (STACS'88), number 294 in 
Lecture Notes in Computer Science, pages 346{355, Berlin-Heidelberg-New 
York, 1988. Springer. 82. Friedrich Otto. Finite canonical rewriting 
systems for congruences generated by concurrency relations. Mathematical 
Systems Theory, 20:253{260, 1987. 83. Prakas Panangaden and Eugene W. 
Stark. Computations, residuals and the power of indeterminacy. In Timo 
Lepistö et al., editors, Proceedings of the 15th International 
Colloquium on Automata, Languages and Programming (ICALP'88), Tampere 
(Finland) 1988, number 317 in Lecture Notes in Computer Science, pages 
439{454, Berlin-Heidelberg-New York, 1988. Springer. 84. Dominique 
Perrin. Words over a partially commutative alphabet. In Alberto 
Apostolico, editor, Combinatorial Algorithms on Words, volume F12 of 
NATO- ASI Series, pages 329{340. Springer, Berlin-Heidelberg-New York, 
1986. 85. Giovanni Pighizzini. Asynchronous automata versus asynchronous 
cellular automata. Theoretical Computer Science, 132:179{207, 1994. 86. 
Vaughan R. Pratt. Modelling concurrency with partial orders. 
International Journal of Parallel Programming, 15(1):33{71, 1986.
87. Gw?enäel Richomme. Some trace monoids where both the Star Problem 
and the Finite Power Property Problem are decidable. In I. Privara et 
al., editors, Proceedings of the 19th Symposium on Mathematical 
Foundations of Computer Science (MFCS'94), Ko<=sice (Slovakia) 1994, 
number 841 in Lecture Notes in Computer Science, pages 577{586, 
Berlin-Heidelberg-New York, 1994. Springer. 88. Jacques Sakarovitch. On 
regular trace languages. Theoretical Computer Science, 52:59{75, 1987. 
89. Jacques Sakarovitch. The \last" decision problem for rational trace 
languages. In Imre Simon, editor, Proceedings of the 1st Latin American 
Symposium on Theoretical Informatics (LATIN'92), number 583 in Lecture 
Notes in Computer Science, pages 460{473, Berlin-Heidelberg-New York, 
1992. Springer. 90. Wolfgang Thomas. Classifying regular events in 
symbolic logic. Journal of Computer and System Sciences, 25:360{376, 
1982.
91. Wolfgang Thomas. Automata on infinite objects. In Jan van Leeuwen, 
editor, Handbook of Theoretical Computer Science, chapter 4, pages 
133{191. Elsevier Science Publishers B. V., 1990.


Partial Commutation and Traces 79

92. Wolfgang Thomas. On logical definability of trace languages. In 
Volker Diekert, editor, Proceedings of a workshop of the ESPRIT Basic 
Research Action No 3166: Algebraic and Syntactic Methods in Computer 
Science (ASMICS), Kochel am See, Bavaria, FRG (1989), Report TUM-I9002, 
Technical University of Munich, pages 172{182, 1990.
93. Wies law Zielonka. Notes on finite asynchronous automata. R.A.I.R.O. 
| Informatique Th?eorique et Applications, 21:99{135, 1987.
94. Wies law Zielonka. Safe executions of recognizable trace languages 
by asynchronous automata. In A. R. Mayer et al., editors, Proceedings of 
the Symposium on Logical Foundations of Computer Science, Logic at Botik 
'89, Pereslavl- Zalessky (USSR) 1989, number 363 in Lecture Notes in 
Computer Science, pages 278{289, Berlin-Heidelberg-New York, 1989. 
Springer.