Algebraic and informational aspects of Zielonka’s Theorem

A. Bertoni – G. Mauri – G. Pighizzini – N. Sabadini

Dipartimento di Scienze dell’Informazione Università degli Studi di Milano via Comelico, 39 20135 Milano – ITALY

Abstract

Zielonka’s Theorem characterizes recognizable subsets of free partially commutative monoids in terms of asynchronous automata.

Here, we prove two results closely related to Zielonka’s Theorem: first, we give a new representation theorem for finite monoids; next, we characterize the class of recognizable subsets of free partially commutative monoids in terms of a new model of distributed system with bounds on space and communication complexity.

1 Introduction

Asynchronous automata, as introduced by W. Zielonka [Zie87] in order to give a mathematical model of concurrent systems, are essentially nets of finite state automata (processors), with a distributed control structure. Each processor has its own local alphabet and state space. An action symbol belonging to more than one local alphabet is executed synchronizing the corresponding processors, while actions that require different processors could be executed concurrently. The resulting structure can be easily interpreted as an automaton over a free partially commutative monoid (fpcm): as a consequence, given a fpcm, the subsets accepted by asynchronous automata are recognizable subsets of the fpcm [BBMS81].

Surprisingly, despite their distributed structure, asynchronous automata exactly characterize the class of recognizable subsets, as witnessed by a deep result obtained by Zielonka [Zie87]: given an automaton on a fpcm, it is always possible to construct an asynchronous automaton, which accepts the same subset.

In this paper, in Section 3 we give a new representation theorem for finite monoids, obtained as a simple consequence of some methods introduced in the proof of Zielonka’s theorem. In particular, we prove that every finite monoid (M, ·, 1) is isomorphic to a quotient of a monoid F of transformations on a suitable finite set S = S_{1} × … × S_{n}, such that:

(i) for every m ∈ M there is an element f_{m} ∈ F, a subset Dom(m) of {1, …, n} and a transformation f̃_{m} : ∏_{i∈Dom(m)} S_{i} → ∏_{i∈Dom(m)} S_{i} such that f_{m} = f̃_{m}×1\overline{Dom(m)}, where 1\overline{Dom(m)} is the identity on ∏_{i∉Dom(m)} S_{i};

(ii) given two transformations f_{m} and f_{m′}, associated with two distinct elements m, m′ ∈ M, the product of m and m′ is commutative, i.e., mm′ = m′m, if and only if Dom(m) ∩ Dom(m′) = ∅, that is the transformations f̃ and f̃′ act on disjoint components of S.

In Section 4 we give a different interpretation of Zielonka’s theorem in the area of distributed systems with bounds on space and communications.

We introduce a model of distributed system consisting of a net of off–line Turing Machines that exchange information using a simple communication protocol. The notion of communication complexity we introduce can be view as a natural extension to arbitrary fpcm of the analogous concept introduced in [BFS86] for products of free monoids. The main result states that the class of recognizable subsets of a finitely generated fpcm coincides with the behaviors of nets working in constant space and with a constant number of communications.

2 Preliminary notions and definitions

In this section we briefly recall basic notions and facts concerning trace languages and the algebraic structures supporting them, i.e., free partially commutative monoids.

Definition 2.1 A independence alphabet is a pair (Σ, I), where:

• Σ = {a_{1}, …, a_{m}} is a finite alphabet;

• I ⊆ Σ × Σ is a symmetric and irreflexive relation, the independence or concurrence relation.

The complement of the independence relation I is called dependence relation and, in the following, will be denoted by \overline{I}.

As usual, the relations I and \overline{I} can be represented using undirected graphs. More precisely, the independence graph associated with the independence alphabet (Σ, I) is the undirected graph with vertex set Σ and with edge set I, while the dependence graph of (Σ, I) is the undirected graph with vertex set Σ and with edge set \overline{I} − \{(a, a) | a ∈ Σ\}. Every clique of the dependence graph, i.e., every subset α ⊆ Σ such that α ≠ ∅ and ∀a, b ∈ α (a, b) ∈ \overline{I}, will be called dependence clique.

Definition 2.2 The free partially commutative monoid F (Σ, I) generated by an independence alphabet (Σ, I) is the initial object of the category of monoids generated by the elements of Σ and satisfying, besides the monoid equations, the set of “commutativity laws”:

{ab = ba | a, b ∈ Σ and (a, b) ∈ I}.

Definition 2.3 A trace on an independence alphabet (Σ, I) is any element t ∈ F (Σ, I); a trace language is any subset T ⊆ F (Σ, I).

In the usual representation, F (Σ, I) is the quotient structure F (Σ, I) = Σ^{∗}/ ≡_{I} where ≡_{I} is the least congruence over Σ^{∗} which extends the set of commutativity laws, and a trace is a congruence class of words. The congruence class containing the string w ∈ Σ^{∗} will be denoted by [w]_{I}, or simply by [w] when I is understood; the composition on F (Σ, I) is defined by [w] · [v] = [w · v]; the identity 1 is the class [ϵ], where ϵ denotes the empty string.

The linearization lin(t) of a trace t is the set of all strings belonging to the equivalence class t, i.e., lin(t) = {x ∈ Σ^{∗} | t = [x]}. The linearization of a trace language T is the union of linearizations of its traces, i.e., lin(T) = ⋃_{t∈T} lin(t).

We recall that every trace t can be represented as a partial order ord(t). This order is formally defined in the following way:

Definition 2.4 Given a trace t ∈ F (Σ, I), let x = x_{1} … x_{n} (x_{i} ∈ Σ, i = 1, …, n) be a representative string of t, i.e., [x]_{≡_{I}} = t; the partial order ord(t) associated to t is the pair ord(t) = (O_{t}, ≤_{t}), such that:

1. O_{t} = {(x_{1}, k_{1}), …, (x_{n}, k_{n})}, where k_{s} denotes the number of symbols equal to x_{s} in the string x_{1} … x_{s};

2. ≤_{t} is the transitive closure of the relation L defined by:

((x_{i}, k_{i}), (x_{j}, k_{j})) ∈ L iff (i ≤ j and (x_{i}, x_{j}) ∉ I).

We recall that an order ideal of a partial order ord = (O, ≤) is a subset O′ of O such that o ≤ o′ and o′ ∈ O′ implies o ∈ O′. It is easy to see that the set of order ideals of ord with the inclusion relation is a lattice. Moreover, it is not difficult to prove that the set of prefixes of a trace t equipped with the prefix relation is isomorphic to the lattice of the order ideals of ord(t) [BMS89]. Of course, given a prefix t′ of t, the order ideal corresponding to t′ is the set O_{t′}, with ordering relation ≤_{t′}=≤_{t} ∩(O_{t′} × O_{t′}).

Now we are able to define α–prefixes of traces.

Definition 2.5 Let (Σ, I) be an independence alphabet, t a trace belonging to F (Σ, I) and α a subset of the alphabet Σ. We denote by P ref_{α}(t) the order ideal generated by the set of occurrences in t of symbols belonging to α, i.e.,

P ref_{α}(t) = {(x, k) ∈ O_{t} | ∃(x′, k′) ∈ O_{t} : (x, k) ≤_{t} (x′, k′) and x′ ∈ α}.

The α–prefix ∂_{α}(t) is defined as the prefix of t corresponding to P ref_{α}(t).

Properties of α–prefixes are extensively studied in [Zie87, CM88]. In this paper we are interested in the following property, useful to compute the α–prefix of a trace:

Lemma 2.1 For t ∈ F (Σ, I), α ⊆ Σ, a ∈ Σ, we have:

∂_{α}(ta) = \{ \begin{matrix}∂_{α∪\overline{I}(a)}t · a & if a ∈ α \\ ∂_{α}t & otherwise, \end{matrix}

where \overline{I}(a) = \{b ∈ Σ | (a, b) ∉ I\}.

In this paper we will consider the class of recognizable trace languages. In order to define this class it is useful to recall the standard notion of automata over a monoid.

Definition 2.6 Let (M, ·, 1) be a monoid. An automaton over M, or M–automaton, is a triple A = (Q, q_{0}, δ) where:

• Q is a finite set of states;

• q_{0} ∈ Q is the initial state;

• δ : Q×M → Q is a transition function such that δ(q, 1) = q and δ(q, m·m′) = δ(δ(q, m), m′) for q ∈ Q, m, m′ ∈ M.

Definition 2.7 Given a monoid (M, ·, 1) and two M–automata A = (Q, q_{0}, δ), A′ = (Q′, q′_{0}, δ′), a morphism ϕ from A to A′ is a function ϕ : Q → Q′ such that ϕ(q_{0}) = q′_{0} (i.e., ϕ preserves the initial state) and ϕ(δ(q, m)) = δ′(ϕ(q), m) for every q ∈ Q, m ∈ M (i.e., ϕ preserves transitions).

From Definition 2.6, it turns out that if M is the free partially commutative monoid F (Σ, I) then δ(q, ab) = δ(q, ba) for (a, b) ∈ I, q ∈ Q, i.e., the action of two independent letters a, b on a state q produces the same result independently on the order of execution. Moreover, the transition function δ is completely defined giving the values δ(q, a), for q ∈ Q and a ∈ Σ. In fact, the only extension of δ to traces is obtained setting δ(q, 1) = q and δ(δ(q, t), a) = δ(q, ta), for q ∈ Q, t ∈ F (Σ, I), a ∈ Σ.

Specifying also a set of final states, every M–automaton can be seen as an acceptor of subsets of M. A trace language T ⊆ F (Σ, I) is said to be recognizable if and only if there is a F (Σ, I)–automaton accepting it. It is well known that T is recognizable if and only if its linearization lin(T) is a regular subset of the free monoid Σ^{∗}.

A different model of automata over free partially commutative monoids was introduced in [Zie87], defining asynchronous automata. In this model, the state set is the product of a family of sets of local states and independent symbols “locally” act on disjoint subfamilies of local states. Formally, we give the following definition:

Definition 2.8 An asynchronous automaton over an independence alphabet (Σ, I), with n processes, is a tuple A = (S_{1}, …, S_{n}, s_{10}, …, s_{n0}, Dom, {f̃_{σ}}_{σ∈Σ}), where:

• for i = 1, …, n, S_{i} is the ith finite set of local states and s_{i0} ∈ S_{i} is the ith initial state;

• Dom : Σ → 2^{{1,...,n}} is a function associating to every symbol σ ∈ Σ its “domain”, such that (a, b) ∈ I if and only if Dom(a) ∩ Dom(b) = ∅;

• for every σ ∈ Σ, f̃_{σ} : ∏_{i∈Dom(σ)} S_{i} → ∏_{i∈Dom(σ)} S_{i} is the local transition function associated with the symbol σ.

We observe that defining, for i = 1, …, n, Σ_{i} as the set {σ | i ∈ Dom(σ)}, the family (Σ_{1}, …, Σ_{n}) is a clique cover of the dependence graph of (Σ, I).

It can be useful to see asynchronous automata as particular monoid automata. In fact, with every asynchronous automaton A = (S_{1}, …, S_{n}, s_{10}, …, s_{n0}, Dom, {f̃_{σ}}_{σ∈Σ}) we associate the F (Σ, I)–automaton (S, q_{0}, δ) where S = ∏_{i=1}^{n} S_{i} is the set of global states, q_{0} = (s_{10}, …, s_{n0}) is the initial global state and δ : S × M → S is the global transition function defined by δ(q, σ) = p, for q, p ∈ S, σ ∈ Σ if and only if q = (s_{1}, …, s_{n}), p = (r_{1}, …, r_{n}), s_{i} = r_{i} for i ∉ Dom(σ) and (r_{i_{1}}, …, r_{i_{k}}) = f̃_{σ}(s_{i_{1}}, …, s_{i_{k}}), where {i_{1}, …, i_{k}} = Dom(σ). Intuitively, the transition function δ is obtained extending local transition functions to global states, in such a way that an action σ ∈ Σ modifies, according to the local transition function f̃_{σ}, only the components of a local state corresponding to its domain. Observe that the ith component of the global state δ(q, t) depends only on q and ∂_{Σ_{i}}(t), i.e., it coincides with the ith components of δ(q, ∂_{Σ_{i}}(t)).

A morphism from an asynchronous automaton A to a F (Σ, I)–automaton A′ is a morphism from the F (Σ, I)–automaton associated with A

The most important result in the theory of asynchronous automata was obtained by W. Zielonka in [Zie87] and it can be formulated in the following way:

Theorem 2.1 Given a F (Σ, I)–automaton A, there exists an asynchronous automaton A_{s} with independence alphabet (Σ, I) and a morphism ϕ from A_{s} to A.

Actually, asynchronous automata were defined as acceptors of trace languages, specifying also a set of final global states; in the original formulation, Zielonka’s Theorem states the equality between the classes of languages accepted by asynchronous automata over (Σ, I) and by F (Σ, I)–automata. So, asynchronous automata characterize recognizable subsets of free partially commutative monoids. Our formulation given in Theorem 2.1 is an immediate consequence of that result.

3 A representation theorem for finite monoids

It is well known that every finite monoid M of N elements is isomorphic to a transformation monoid M̂ ⊆ N^{N}. The following theorem improves that result considering pairs of elements of M whose product is commutative.

Theorem 3.1 Every finite monoid (M, ·, 1) is isomorphic to a quotient of a monoid F of transformations on a set S, such that:

(i) S is the product of n finite sets S_{1}, …, S_{n}, n ≥ 1;

(ii) for every m ∈ M there is an element f_{m} ∈ F, a subset Dom(m) of {1, …, n} and a “local” transformation f̃_{m} : ∏_{i∈Dom(m)} S_{i} → ∏_{i∈Dom(m)} S_{i} such that f_{m} = f̃_{m} × 1\overline{Dom(m)}, where 1\overline{Dom(m)} is the identity on ∏_{i∉Dom(m)} S_{i};

(iii) given two transformations f_{m} and f_{m′}, associated with two distinct elements m, m′ ∈ M, the product of m and m′ is commutative, i.e., mm′ = m′m, if and only if the “local” transformations f̃ and f̃′ act on disjoint components of S, i.e., Dom(m) ∩ Dom(m′) = ∅.

Proof. Given the monoid (M, ·, 1), we consider the independence alphabet (Σ, I) where Σ = M, I = {(m, m′) ∈ M × M | m, m′ ∈ M}, and the F (Σ, I)–automaton A = (Q, δ, q_{0}) with Q = M, q_{0} = 1 and δ(m, σ) = m · σ, for m ∈ Q, σ ∈ Σ.

It is not difficult to verify that δ(m, t) = m · δ(1, t), for m ∈ M and t ∈ F (Σ, I). From Theorem 2.1, it turns out that there exists an asynchronous automaton

A_{s} = (S_{1}, …, S_{n}, s_{10}, …, s_{n0}, Dom, {f̃_{σ}}_{σ∈Σ}) and a morphism ϕ from A_{s} to A.

For σ ∈ Σ, let f_{σ} be the transformation f̃_{σ} × 1\overline{Dom(m)}, obtained extending f̃_{σ} to global states.

We consider the monoid (F, ∘, I), where F = {f_{σ} | σ ∈ M}^{∗}, ∘ denotes the composition of transformations, and I is the identity on S. We observe that (σ, γ) ∈ I implies f_{σ} ∘ f_{γ} = f_{γ} ∘ f_{σ}. Thus, we can associate with every trace t ∈ F (Σ, I) an element f_{t} ∈ F, setting: f_{ϵ} = I and f_{tσ} = f_{t} ∘ f_{σ}, for t ∈ F (Σ, I), σ ∈ Σ. It is not difficult to see that f_{t}(s_{10}, …, s_{n0}) is the global state reached by the automaton A_{s} executing the trace t from the initial global state, i.e., f_{t}(s_{10}, …, s_{n0}) = δ_{s}((s_{10}, …, s_{n0}), t), where δ_{s} is the global transition function of A_{s}.

Given t′, t′′ ∈ F (Σ, I), f_{t′} = f_{t′′} implies δ(1, t′) = δ(1, t′′). In fact, f_{t′}(s_{10}, …, s_{n0}) = δ_{s}((s_{10}, …, s_{n0}), t′) and f_{t′′}(s_{10}, …, s_{n0}) = δ_{s}((s_{10}, …, s_{n0}), t′′); since there is a morphism from A_{s} to A, δ_{s}((s_{10}, …, s_{n0}), t′) = δ_{s}((s_{10}, …, s_{n0}), t′′) implies δ(1, t′) = δ(1, t′′).

Now, we consider the function ψ : F → M defined by:

ψ(f) = m if and only if ∃t ∈ F (Σ, I)(f = f_{t} ∧ δ(1, t) = m).

From the last observation, it turns out that this definition of ψ is sound. Now, we show that ψ is an homomorphism.

First, we observe that ψ(I) = 1, in fact I = f_{ϵ} and δ(1, ϵ) = 1. Given f′, f′′ ∈ F, let t′, t′′ ∈ F (Σ, I), m′, m′′ ∈ M such that f′ = f_{t′} and f′′ = f_{t′′}, m′ = ψ(f′) and m′′ = ψ(f′′). We have:

ψ(f′ ∘ f′′) = ψ(f_{t′} ∘ f_{t′′}) = ψ(f_{t′·f′′}) = δ(1, t′t′′) = δ(δ(1, t′), t′′)
= δ(m′, t′′) = m′ · δ(1, t′′) = m′ · m′′ = ψ(f′) · ψ(f′′).

Hence, ψ is an homomorphism. At this point, it is not difficult to conclude that M is isomorphic to the quotient of F with respect to the congruence induced by the morphism ψ.

4 Recognizable Trace Languages and Communication Complexity

In this section we relate the main Theorem of Zielonka to communication complexity. In fact we present a model of distributed system constituted by off–line Turing Machines exchanging information using a simple communication protocol, and we show that with constant bounds on the space of computation and on communication, this model characterizes the class of recognizable trace languages.

Let (Σ, I) be an independence alphabet and Σ_{1}, …, Σ_{m} a clique cover of its dependence graph. We consider a net N = (M_{1}, …, M_{m}), where any M_{i} is a Turing Machine with a read only input tape and a work tape; the input alphabet of M_{i} is Σ_{i}. Machine M_{i} can send messages to machine M_{j} through an unidirectional communication channel, with a FIFO strategy. When the machine M_{i} enters in a particular state q_{!}^{(ij)}, it put a bit in the queue of messages from M_{i} to M_{j}; when M_{i} enters in a particular state q_{?}^{(ji)}, it get a bit from the queue of messages from M_{j} to M_{i} or it waits if the queue is empty.

Now we explain how a net of this kind can recognize trace languages. Given a trace t ∈ F (Σ, I), the machine M_{i} receives on its input tape a whatever representative string x_{i} of the prefix ∂_{Σ_{i}}(t), i.e., x_{i} ∈ lin(∂_{Σ_{i}}(t)). With this input the machine starts its computation. During the computation the machine can send or receive messages from other machines as explained above. The machine M_{1} has an accepting state q_{Y} and a rejecting state q_{N}. We say that the net is sound whether, for every trace t, every machine M_{i} ends its computation in a finite number of steps and the machine M_{1} halts in a state q ∈ {q_{Y} , q_{N}}, independently on the choice of representative strings x_{1}, …, x_{m}; in other words, this means that the acceptation or the rejection does not depend on the choice of representative strings.

We say that the space complexity of a net N on a trace t is the maximum number of cells on work tapes scanned during the computation, while the communication complexity is the maximum number of bits exchanged.

A sound net N recognizes a trace language T ⊆ F (Σ, I) if and only if for every t ∈ T the machine M_{1} halts in q_{Y} and for every t ∉ T the machine M_{1} halts in q_{N}. We denote by C_{(Σ,I)}(f(n), g(n)) the class containing trace languages T ⊆ F (Σ, I) which are recognizable by nets N within space and communication complexity bounded respectively, on traces of length n, by cf(n) and cg(n), where c is a suitable constant depending only on N.

Theorem 4.1 The class of recognizable subsets of a free partially commutative monoid F (Σ, I) with a finite number of generators coincides with the class C_{(Σ,I)}(1, 1).

Proof. ⊆) If T ⊆ F (Σ, I) is a recognizable trace language, then there exists an asynchronous automaton A with m processes recognizing it. We construct a net N of m machines M_{1}, …, M_{m} that work in this way. Given an input trace t ∈ F (Σ, I), the machine M_{i} simulates the computation of the asynchronous automaton A on the trace ∂_{Σ_{i}}(t). When the machine M_{i}, i > 1, ends its simulation, it sends the global state reached to the machine M_{1}. Collecting these states, M_{1} can reconstruct the global state reached by the asynchronous automaton A on input t and so, it can decide whether or not t belongs to T. Since the space and the amount of bits exchanged during the simulation do not depend on the input trace t, we can conclude that the language T belongs to the class C_{(Σ,I)}(1, 1).

⊇) To prove the inclusion of the class C_{(Σ,I)}(1, 1) in the class of recognizable trace languages, we sketch an algorithm for simulating a net N = (M_{1}, …, M_{m}) recognizing a trace language T, using a one tape Turing Machine M working in linear time. Since, as shown in [Hen65], every language accepted by a machine with these constraints is regular, we can conclude that T is a recognizable trace language.

Given a net N we consider strings on the alphabet {q_{?}^{ij}, q_{!}^{ij}0, q_{!}^{ij}1}. Such a string can represent a sequence of operations “send” or “receive” among machines of the net. However, some strings do not correspond to safe computations of the machine; for instance, the string q_{?}^{ij}q_{?}^{ji} represents a deadlock (M_{i} waits a bit from M_{j} and vice versa). With a precomputation, we recover the set D of strings representing “safe” sequences of communications in the net N. Note that this set is finite since N has communication complexity O(1) and it does not depend on the input trace.

Now we explain how the machine M can simulate the computation of the net N on a trace t ∈ F (Σ, I). The machine starts its computation with a representative string w ∈ lin(t) on its tape; for every “safe” sequence d of communications, i.e., d ∈ D, M simulates the computations of M_{1}, M_{2}, …, M_{m} using the string d for the communications. The machine accepts if and only if M_{1} can reach the accepting state q_{Y} in a simulation involving a string d ∈ D. More precisely, we can describe the computation of M with the following program:

f := 0

for all d ∈ D do

begin i:=0 while i ≤ m and compatible(M_{i}, d) do i := i + 1 if i = m + 1 and the last state reached by M_{1} is q_{Y} then f := 1

end

if f = 1 then accepts else reject

The test compatible(M_{i}, d) can be performed in the following way:

• M scans the string w on its tape from right to left marking the symbols belonging to the prefix of ∂_{Σ_{i}}(t) (see Lemma 2.1);

• M simulates M_{i} (skipping all not marked symbols), using the string d in order to obtain in the states q_{?}^{ij} the bits from other processes; • the answer to the test is TRUE if and only if the sequence of symbols q_{!}^{ij}x, x ∈

{0, 1}, and q_{?}^{ij} matches with the sequence of messages sent and of interrogation states of M_{i} during the simulated computation;

• after the simulation of M_{i}, the machine unmarks the input symbols of ∂_{Σ_{i}}(t); so, at the end of the simulation of M_{i}, the content of the tape is the string w.

At this point, it is not difficult to verify that the string w is accepted by M if and only if the trace t is accepted by the given net N.

Now we show that M works in linear time. The machine M_{i} uses space O(1) and its computation is finite; so, M can be seen as a two way finite automaton whose head inverts the direction a constant number of times [HU79]. Thus, the test compatible(M_{i}, d) can be done in time O(n), where n = |w|. This test is repeated for every machine M_{i} and for every d ∈ D. But the number of machines M_{i} and the set D do not depend on the input. This permits us of concluding that the running time of M is O(n).

Since the machine M has only one tape and it works in linear time, as shown in [Hen65], the language L recognized by it is a regular subset of Σ^{∗}. On the other hand, the given net N accepts the trace language T. From the above given simulation, we can easily conclude that L = lin(T). Thus T is a recognizable trace language.

5 Conclusions and open problems

The main results obtained in this paper are:

(1) The Theorem of Zielonka (Theorem 2.1) is related to a representation result for finite monoids (Theorem 3.1).

(2) It is given an interpretation of Zielonka’s Theorem in terms of communication complexity.

With respect to (1), we observe that Theorem 3.1 easily implies Zielonka’s Theorem. Since the direct proof of this theorem is very complicated, and it seems very difficult to obtain some meaningful simplification, despite all efforts (see, e.g., [CM88, CMZ89]), an interesting open problem is then to study a direct proof of our result, using more algebraic oriented techniques.

With respect to (2), we leave as an open problem to characterize other classes of languages recognized by nets of machines with given non constant bounds in space and communication complexity.

References

[BBMS81] A. Bertoni, M. Brambilla, G. Mauri, and N. Sabadini. An application of the theory of free partially commutative monoids: asymptotic densities of trace languages. In Proc. 10th MFCS, Lecture Notes in Computer Science 118, pages 205–215, 1981.

[BFS86] L. Babai, P. Frankl, and J. Simon. Complexity classes in communication complexity theory. In Proc. 27th Symposium on Foundations of Computer Science, pages 337–347, 1986.

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

[CM88] R. Cori and Y. Métivier. Approximation of a trace, asynchronous automata and the ordering of events in a distributed system. In Proc. 15th ICALP, Lecture Notes in Computer Science 317, pages 147–161, 1988.

[CMZ89] R. Cori, Y. Métivier, and W. Zielonka. Asynchronous mappings and asynchronous cellular automata. Technical Report 89–97, LaBRI, Université de Bordeaux I, 1989.

[Hen65] F. Hennie. One–tape, off–line turing machine computations. Information and Control, 8:553–578, 1965.

[HU79] J. Hopcroft and J. Ullman. Introduction to automata theory, languages and computations. Addison–Wesley, 1979.

[Zie87] W. Zielonka. Notes on finite asynchronous automata. RAIRO Inf. Theor., 21:99–135, 1987.