Code Problems on Traces

Volker Diekert Anca Muscholl^{⋆}

Universität Stuttgart, Institut für Informatik Breitwiesenstr. 20-22, D-70565 Stuttgart

Abstract. The topic of codes in the framework of trace monoids leads to interesting and challenging decision problems of combinatorial flavour. We give an overview of the current state of some basic questions in this field. Among these, we consider the existence problem for strong codings, clique-preserving morphisms and the unique decipherability problem (code problem).

1 Introduction

Free partially commutative monoids [7] offer a mathematically sound framework for modelling and analyzing concurrent systems. This was made popular by the work of Mazurkiewicz. He investigated originally the behaviour of safe 1-labelled Petri nets [17] and the computer science community quickly recognized the importance of this work. The basic concept is to consider a system as a finite set of actions Σ, together with a fixed symmetric independence relation I ⊆ Σ ×Σ, denoting pairs of actions which can be scheduled in parallel. In the setting defined by a pair (Σ, I) we identify sequential observations (i.e., strings over Σ) modulo identities ab = ba for (a, b) ∈ I. This yields the partial commutation and the resulting monoid has been called trace monoid by Mazurkiewicz. Trace monoids have been successfully considered in classical theories like formal languages, automata and logic. Some challenging decision problems for trace monoids are still open. One of the fundamental open problems is whether or not there is an algorithm to decide the solvability of equations involving constants. For the word case of free monoids the positive answer is known to due a famous result of Makanin [15]. The solution of an equation is a homomorphism. We think that a better understanding of homomorphisms will help to attack a possible extension of Makanin’s result, and our contribution is restricted to some questions about homomorphisms. The surprising fact is that even basic questions on codings (injective homomorphisms) between trace monoids are still open. We focus on two problems. First, given two trace monoids 𝕄_{1}, 𝕄_{2}, does an injective homomorphism h: 𝕄_{1} → 𝕄_{2} exist? Second, given a homomorphism h: 𝕄_{1} → 𝕄_{2}, is h injective, i.e., a coding? For both questions only partial answers are known. The first question has a positive answer for strong codings, see Sect. 3 below.

⋆ This research has been supported in part by the French-German research programme PROCOPE.

The second question is known to be undecidable, even if the first monoid is free, as soon as (Σ_{2}, I_{2}) contains a cycle on four vertices as induced subgraph [14, 8]. It is known to be decidable when the independence relation (Σ_{2}, I_{2}) does not contain any induced subgraph isomorphic to the path P_{4} or the cycle C_{4} on four vertices, [1]. Recently it has been shown that for (Σ_{2}, I_{2}) being equal to the P_{4}, the code problem is decidable. However, the question of the precise borderline for decidability is still open. We present in Sect. 4 the solution to the code problem for P_{4}, which has been exhibited independently in [13, 16]. Another natural instance of the question whether a given homomorphism h: 𝕄_{1} → 𝕄_{2} is a coding or not is given when h is described by morphisms between independence alphabets. This special case arises when actions in a system are refined in such a way that the refined action is a product of independent elements which therefore can be performed in parallel. However even for such a restricted class of homomorphisms the injectivity problem turns out again to be undecidable, see Sect. 5.

2 Notations and Preliminaries

A dependence alphabet is a pair (Σ, D), where Σ is a finite alphabet and D ⊆ Σ × Σ is a reflexive and symmetric relation, called dependence relation. The complement I = (Σ × Σ) \ D is called independence relation; it is irreflexive and symmetric. The pair (Σ, I) is denoted independence alphabet. We view both (Σ, D) and (Σ, I) as undirected graphs. The difference is that (Σ, D) has self-loops. Given an independence alphabet (Σ, I) (or a dependence alphabet (Σ, D) resp.) we associate the trace monoid 𝕄(Σ, I). This is the quotient monoid Σ^{∗}/ ≡_{I}, where ≡_{I} denotes the congruence generated by the set {uabv = ubav | (a, b) ∈ I, u, v ∈ Σ^{∗}}; an element t ∈ 𝕄(Σ, I) is called a trace, the length |t| of a trace t is given by the length of any representing word. By alph(t) we denote the alphabet of a trace t, which is the set of letters occurring in t. The initial alphabet of t is the set in(t) = {x ∈ Σ | ∃t′ ∈ 𝕄(Σ, I) : t = xt′}. By 1 we denote both the empty word and the empty trace. Traces s, t ∈ 𝕄(Σ, I) are called independent, if alph(s) × alph(t) ⊆ I. We simply write (s, t) ∈ I in this case. A trace t ≠ 1 is called a root, if t = u^{n} implies n = 1, for every u ∈ 𝕄(Σ, I). A trace t is called connected, if alph(t) induces a connected subgraph of the dependence alphabet (Σ, D).

3 Existence problem for codings

A homomorphism h: 𝕄(Σ, I) → 𝕄(Σ′, I′) is given by a mapping h: Σ → 𝕄(Σ′, I′) such that h(a)h(b) = h(b)h(a) for all (a, b) ∈ I. The homomorphism is called a coding, if it is injective. Representing each trace h(a) by a word ĥ(a) ∈ Σ′^{∗} we obtain a homomorphism between free monoids ĥ: Σ^{∗} → Σ′^{∗}. It may happen that the lifting ĥ is injective, but h is not. (A trivial example is ĥ = id_{Σ′} with I′ ≠ ∅.) But if we know that ĥ is not injective, then h cannot be injective. This surprising fact has been recently announced in [5]: If h: 𝕄(Σ, I) → 𝕄(Σ′, I′) is a coding, then every lifting ĥ: Σ^{∗} → Σ′^{∗} is a word coding. The result is far from being trivial and gives some flavour about the unexpected behaviour of homomorphisms between trace monoids. It is completely open whether the existence problem for codings between trace monoids is decidable. Only some few results and conjectures have been established [4, 12]. The situation changes if we restrict our attention to a naturally arising subclass of homomorphisms. The existence problem of strong codings has a nice graph characterization being discussed in this section.

Definition 1. [6] A homomorphism h: 𝕄(Σ, I) → 𝕄(Σ′, I′) is called a strong homomorphism, if (h(a), h(b)) ∈ I′ holds for all (a, b) ∈ I. A strong coding is a strong homomorphism being injective.

Hence, strong homomorphisms map independent letters to independent traces. The perhaps most prominent example of a strong coding is given by the Projection Lemma [9, 10]. It can be rephrased as follows.

Example 1. Let Σ′ ⊆ Σ be a subalphabet such that Σ′ × Σ′ ⊆ D. The canonical projection π_{Σ′}: 𝕄(Σ, I) → Σ′^{∗} is the homomorphism induced by setting π_{Σ′}(a) = a for a ∈ Σ′ and π_{Σ′}(a) = 1 for a ∈ Σ \ Σ′. Consider (Σ, D) written as a union of cliques, i.e., (Σ, D) = (⋃_{i=1}^{k} Σ_{i}, ⋃_{i=1}^{k} Σ_{i} × Σ_{i}). Then the canonical homomorphism

π: 𝕄(Σ, I) → ∏_{i=1}^{k} Σ_{i}^{∗}, t ↦ (π_{Σ_{i}}(t))_{1≤i≤k}

is a strong coding.

The Projection Lemma leads to the upper bound in the next proposition. To derive the lower bound is left as an exercise to the reader.

Proposition 2. Let (Σ, D) be a dependence alphabet and |Σ_{i}| ≥ 2 for i = 1, …, k. Then there exists a strong coding h: 𝕄(Σ, I) → ∏_{i=1}^{k} Σ_{i}^{∗} if and only if (Σ, D) allows a covering by k cliques. In particular, deciding the existence of strong codings into a k-fold direct product of free monoids is NP-complete.

The following example suggests some of the differences between the existence problem for codings resp. strong codings.

Example 2. Let (Σ, D) = C_{n} denote the cycle on n > 3 vertices, i.e., Σ = {a_{1}, …, a_{n}} and D is defined by the edges {a_{m}a_{m+1} | 1 ≤ m ≤ n} (with addition modulo n). By the proposition above there exists a strong coding from 𝕄(Σ, I) into ∏_{i=1}^{k} Σ_{i}^{∗} (where |Σ_{i}| ≥ 2 for all i) if and only if k ≥ n. If we consider codings instead of strong codings we obtain k = n − 1 as an upper bound. Let h: 𝕄(Σ, I) → ∏_{i=1}^{n−1} Σ_{i}^{∗} be given by h(a_{m}) = x_{m−1}y_{m}x_{m+1} for m < n and h(a_{n}) = x_{n−1}x_{1} (where by convention x_{0} = x_{n−1} and x_{n} = x_{1}). It is straightforward to check that h is a homomorphism. Suppose now h(u) = h(v) for some u, v and let |u|+|v| be minimal. The minimality implies in(u)∩in(v) = ∅. Since u ≠ 1 ≠ v we may assume by symmetry that for some 1 ≤ m < n we have a_{m} ∈ in(u) \ in(v). Then y_{m} ∈ in(h(u)). This implies a_{m} ∈ alph(v) and even a_{m} ∈ in(v) (otherwise x_{m} ∈ in(h(v))). Hence a contradiction. It can be shown that k ≥ n − 1 is also necessary for the existence of a coding for n > 4. On the other hand, 𝕄(Σ, I) with (Σ, D) = C_{4} can be already embedded in the direct product of two free monoids, [4, 12].

No difference between the existence of codings and strong codings occurs however if the left-hand side monoid is free commutative (see also [18]). It also yields a lower bound for the complexity in Cor. 4 and Cor. 7 below.

Proposition 3. Let (Σ, D) be a dependence alphabet and k ≥ 1. The following assertions are equivalent:

i) The dependence alphabet (Σ, D) contains an independent set of size k. ii) There exists a strong coding h: ℕ^{k} → 𝕄(Σ, I). iii) There exists a coding h: ℕ^{k} → 𝕄(Σ, I).

Corollary 4. Given (Σ, D) and k, it is NP-complete to decide whether there exists a (strong) coding of ℕ^{k} into 𝕄(Σ, I). Therefore, the problem whether there exists a (strong) coding between two given trace monoids is (at least) NP-hard.

Strong homomorphisms are tightly connected to morphisms of dependence and independence alphabets, which we now define.

Definition 5. Let (V′, E′), (V, E) be undirected graphs (possibly with selfloops), H ⊆ V′ × V be a relation between vertices, and for a′ ∈ V′ let H(a′) denote the set {a ∈ V | (a′, a) ∈ H}. The relation H is called a relational morphism, if (a′, b′) ∈ E′ implies H(a′) × H(b′) ⊆ E for all a′, b′ ∈ V′.

Theorem 6 [12]. Let (Σ, D) and (Σ′, D′) be dependence alphabets. The following assertions are equivalent:

i) There exists a strong coding h: 𝕄(Σ, I) → 𝕄(Σ′, I′). ii) There exists a relational morphism H: (Σ′, D′) → (Σ, D) of dependence

alphabets such that for all a ∈ Σ there exists a′ ∈ Σ′ with a ∈ H(a′), and for all (a, b) ∈ D, a ≠ b there exists (a′, b′) ∈ D′, a′ ≠ b′, with (a, b) ∈ H(a′) × H(b′).

Furthermore there are effective constructions between h and H such that H = {(a′, a) ∈ Σ′ × Σ | a′ ∈ alph(h(a))}.

Corollary 7. The following problem is NP-complete: Instance: Independence alphabets (Σ, I), (Σ′, I′). Question: Does there exist a strong coding from 𝕄(Σ, I) into 𝕄(Σ′, I′)?

4 Code problem

Rational languages in trace monoids (built over finite sets using concatenation, union and Kleene star) strictly contain the family of recognizable languages and do not form a Boolean algebra, in general. More precisely, the family of rational trace languages over 𝕄(Σ, I) is a Boolean algebra if and only if the independence relation I is transitive [20]. This fact leads to nontrivial decision problems for rational trace languages, see [3, 1, 20]. It is known e.g. that the question whether the intersection of two rational trace languages is empty or not is undecidable, in general. More precisely, the intersection problem is undecidable if and only if the graph associated to the independence relation contains as induced subgraph either a cycle or a path on four vertices [1]. It is therefore decidable exactly for transitive forests [22]. We ask in this section a closely related question, namely whether a finite set X is a code, i.e., whether X freely generates X^{+}. More generally, we will consider the notion of trace code.

Definition 8. For a set X ⊆ 𝕄(Σ, I) let Σ_{X} be an alphabet being in bijection ψ with the set X. Define I_{X} ⊆ Σ_{X} ×Σ_{X} by (x, y) ∈ I_{X} if x ≠ y and ψ(x)ψ(y) = ψ(y)ψ(x). Then X is called a trace code, if the induced homomorphism ψ: 𝕄(Σ_{X}, I_{X}) → 𝕄(Σ, I) is a coding.

Definition 9. The (trace) code problem for (Σ, I) is to decide on the instance of a finite set X ⊆ 𝕄(Σ, I) whether or not it is a (trace) code.

The trace code problem can be reduced to the intersection problem of rational trace languages. To see this, assume that X is not a trace code, then we find two traces u, v ∈ 𝕄(Σ_{X}, I_{X}), u ≠ v such that ψ(u) = ψ(v). For u, v with |u| + |v| minimal we obtain some x ∈ Σ_{X} with x ∈ in(u) and either alph(v) ⊆ I_{X}(x) or v = v_{1}yv_{2}, for some y ≠ x, (x, y) ∉ I_{X} and alph(v_{1}) ⊆ I_{X}(x) (I_{X}(x) denoting the set of letters from Σ_{X} independent of x). Hence, X is not a trace code if and only if for some x ∈ Σ_{X} the following holds:

ψ(x)X^{∗} ∩ (ψ(I_{X}(x)^{∗}) ∪ ψ(I_{X}(x)^{∗})ψ(D_{X}(x) \ x)X^{∗}) ≠ ∅ .

Since rational sets are closed under homomorphisms, the claim immediately follows. Hence, we obtain the following

Proposition 10. i) If the trace code problem is decidable for (Σ, I), then the

code problem is decidable for (Σ, I). ii) Both problems are decidable if the independence relation is a transitive forest

[1]. iii) Both problems are undecidable as soon as the independence relation I con-

tains C_{4} as induced subgraph [14, 8] (equivalently, 𝕄(Σ, I) contains a submonoid isomorphic to {a, b}^{∗} × {c, d}^{∗}).

The precise borderline for the decidability of the (trace) code problem is currently open. A temptive idea would consist in conjecturing undecidability for independence alphabets containing P_{4} as induced subgraph, since this would settle the problem. However, the decidability of the (trace) code problem for P_{4} has been recently established, [13, 16]. Furthermore, not every independence alphabet which does not contain C_{4} as induced subgraph has a decidable code problem, see [13, 16] for examples. The code problem between free monoids is equivalent to the emptiness problem for finite automata. Given X ⊆ A^{∗}, the states of the associated automaton A_{X} are suffixes of words in X. A transition u →^{1} v exists if v ∈ X^{−1}u ∪ u^{−1}X. With X^{−1}X \ {1} as initial states and 1 as unique final state one can verify that 1 ∈ L(A_{X}) is equivalent to L(A_{X}) ≠ ∅, which holds if and only if X is not a code. For the special case of free monoids, well-known techniques (see [2]) solve the code problem in polynomial time. More precisely, the code problem is complete for NL, the class of languages which can be recognized by nondeterministic Turing machines in logarithmic space (for the hardness see [19]). For the trace monoid 𝕄 = 𝕄(Σ, I), where the independence (or equivalently, the dependence) alphabet is P_{4}, the same complexity result holds, c.f. Thm. 13 below. However, we need a more complex device than finite automata. We assume for the rest of this section that 𝕄 = 𝕄(Σ, I), where (Σ, I) is equal to P_{4}:

Σ = {a, b, c, d} and I = {(a, b), (b, a), (b, c), (c, b), (c, d), (d, c)}.

We will use a one-counter automaton. Thus, the automaton can increment, decrement, and test the counter for zero. The value of the counter is an integer. By storing the sign in the finite control, we may also use a pushdown automaton where the pushdown alphabet contains besides the bottom symbol only one single symbol. We consider below mainly the code problem, i.e., the question whether a finite set X ⊆ 𝕄 freely generates X^{+}. The basic idea will be to guess two different factorizations of an element of X^{+} by storing in the counter a certain number of b’s resp. c’s, while keeping a (finite) synchronization information in the finite control. The technical lemma below explains how information can be stored in this way. We need some more notations. For traces w_{1}, w_{2}, … in 𝕄 let w[i] denote w_{1} ⋯ w_{i}. If u is a factor of v we also write u ⊆ v. (This means that v ∈ 𝕄u𝕄.) For u_{1}, …, u_{i}, v_{1}, …, v_{j} ∈ X we call the pair (u[i], v[j]) a partial solution, if u[i]s = v[j]s′ holds for some s, s′ ∈ 𝕄. Using Levi’s Lemma [10] we can represent u[i], v[j] as follows.

Fact 11 Let (u[i], v[j]) be a partial solution. Then unique traces r, α_{0}, α, β_{0}, β ∈ 𝕄 exist such that

• u[i] = rα_{0}α, v[j] = rβ_{0}β

• (α_{0}α, β_{0}β) ∈ I • α_{0} ⊆ u[i − 1], α ⊆ u_{i}, β_{0} ⊆ v[j − 1], β ⊆ v_{j}.

Lemma 12. Let X ⊆ 𝕄 be given and let w = u_{1} ⋯ u_{n} = v_{1} ⋯ v_{m} be such that u_{i}, v_{j} ∈ X with (u_{1}, …, u_{n}) ≠ (v_{1}, …, v_{m}). Let (u[i], v[j]) be a partial solution with r, α_{0}, α, β_{0}, β defined as above, (i, j) ≠ (n, m). Moreover, suppose |alph(α_{0}β_{0})| ≤ 1. Then there exist s, t ≥ 0 with s + t > 0 satisfying the following properties:

i) Either s = 0 or t = 0. Moreover, if s = 0 then alph(v_{j+1} ⋯ v_{j+t−1}) is a clique in (Σ, I). Symmetrically, if t = 0 then alph(u_{i+1} ⋯ u_{i+s−1}) is a clique in (Σ, I).

ii) u[i + s] = r′α′_{0}α′ and v[j + t] = r′β′_{0}β′ hold for uniquely determined traces r′, α′_{0}, α′, β′_{0}, β′ satisfying α′_{0} ⊆ u[i + s − 1], α′ ⊆ u_{i+s}, β′_{0} ⊆ v[j + t − 1] and β′ ⊆ v_{j+t}. Moreover, we have |alph(α′_{0}β′_{0})| ≤ 1.

Proof. First observe that |alph(α_{0}β_{0})| ≤ 1 together with (α_{0}, β_{0}) ∈ I implies that either α_{0} = 1 or β_{0} = 1. Suppose therefore without loss of generality β_{0} = 1. We distinguish the following cases:

i) Let α_{0} = 1: Choose (s, t) = (1, 0) and let p, α′_{0}, α′, β′ be such that αu_{i+1} = pα′_{0}α′, β = pβ′, (α′, β′) ∈ I and α′_{0} ⊆ α, α′ ⊆ u_{i+1}. Symmetrically we can choose (s, t) = (0, 1) and define p, α′, β′_{0}, β′ accordingly.

ii) Let β = 1: Choose (s, t) = (0, 1). Then we have α_{0}α = pα′_{0}α′, v_{j+1} = pβ′ for uniquely determined p, α′_{0}, α,′ β′ with (α′_{0}α′, β′) ∈ I, where α′_{0} ⊆ α_{0}, α′ ⊆ α. Note that p, α′, β′ depend on α, v_{j+1} and on the comparison between |α_{0}| and a value bounded by α, v_{j+1} (thus bounded by X).

iii) Let α_{0}, β ≠ 1 and |alph(α_{0}α)| = 1: Choose (s, t) = (1, 0). Then we have α_{0}αu_{i+1} = pα′_{0}α′ and β = pβ′ for uniquely determined p, α′_{0}, α′, β′ with (α′_{0}α′, β′) ∈ I, where α′_{0} ⊆ α_{0}α and α′ ⊆ u_{i+1}. Due to (α_{0}α, β) ∈ I we have p ⊆ u_{i+1}, hence α′_{0} = α_{0}α. Moreover, α′ and β′ can be directly computed from u_{i+1}, β.

iv) Finally let |alph(α_{0}α)| > 1 and α_{0}, β ≠ 1:

We know in this case that alph(α_{0}α) is a clique of the dependence relation D. In fact, either alph(α_{0}α) ⊆ {a, c} or alph(α_{0}α) ⊆ {b, d}. Let e.g. α_{0}α ∈ b^{+}d{b, d}^{∗} and consider the least t > 0 such that alph(v_{j+t})∩(D(b)\{b}) ≠ ∅, i.e., d ∈ alph(v_{j+t}). Clearly, every e ∈ alph(βv_{j+1} ⋯ v_{j+t−1}) satisfies (e, b) ∈ I or e = b. Moreover, if e ≠ b then (e, d) ∈ I. Otherwise, there would exist an edge from an e-labelled vertex x in v_{j+1} ⋯ v_{j+t−1} to a d-labelled vertex y in v_{j+t} ⋯ v_{m}, whereas y precedes x in α_{0}αu_{i+1} ⋯ u_{n}. Therefore, e = c and alph(βv_{j+1} ⋯ v_{j+t−1}) ⊆ {b, c}. Let p, α′_{0}, α′, β′_{0}, β′ be the unique traces satisfying (α′_{0}α′, β′_{0}β′) ∈ I and α_{0}α = pα′_{0}α′ and βv_{j+1} ⋯ v_{j+t} = pβ′_{0}β′. Moreover, α′_{0} ⊆ α_{0}, α′ ⊆ α, β′_{0} ⊆ βv_{j+1} ⋯ v_{j+t−1} and β′ ⊆ v_{j+t}. Since both alph(α) ∩ D(b) ≠ ∅ and alph(v_{j+t}) ∩ D(b) ≠ ∅ hold, we obtain α_{0} ⊆ p and π_{b}(v_{j+1} ⋯ v_{j+t−1}) ⊆ p. Hence, α′_{0} = 1 and β′_{0} ⊆ βπ_{c}(v_{j+1} ⋯ v_{j+t−1}). Clearly we have β ∈ c^{+} due to (α_{0}α, β) ∈ I, and the claim is satisfied.

Remark. 1. Note that Lem. 12 still holds if (Σ, I) contains no triangle and no induced C_{4}. Moreover, for (Σ, I) = P_{4} we note that the additional assumption α_{0}β_{0} ∈ b^{∗} ∪ c^{∗} yields in Lem. 12 α′_{0}β′_{0} ∈ b^{∗} ∪ c^{∗}, too. It suffices to choose in the case α_{0} = 1: (s, t) = (1, 0), if α ∈ b^{∗} ∪c^{∗}, resp. (s, t) = (0, 1), if β ∈ b^{∗} ∪c^{∗}.

2. In order to be a code, X may contain at most one element of the form b^{k}c^{l}, since any two such traces commute.

3. Let us take a closer look at the last case in the previous proof. Assume α_{0} = b^{q} and β = c^{r} for some q ≥ 0, r > 0. Supposing that X ∩ b^{∗}c^{∗} = {b^{k}c^{l}} the following equations hold:

b^{q}α = pα′ ,  (1)
c^{r}\binom{b^{k}}{c^{l}}^{t−1}v_{j+t} = pβ′_{0}β′.  (2)

Note that q and k(t − 1) differ by a value depending on α and v_{j+t}, only. Hence, k(t − 1) is determined by q and a value depending on α and v_{j+t}, only (thus bounded by X). Moreover, due to |α|_{c} = 0 we have β′_{0} = c^{r+l(t−1)}. Finally, with p = b^{q}p′ for some p′ we have α = p′α′, b^{k(t−1)}v_{j+t} = b^{q}p′β′ and we see that p′, α′, β′ can be computed using α and v_{j+t}, only.

Let (u[i], v[j]) be a partial solution with u[i] = rα_{0}α, v[j] = rβ_{0}β as in Lem. 12. A counter automaton can store the integer value |α_{0}| − |β_{0}| in the counter, whereas α, β are part of the finite control. The initial configurations (α, β), α_{0}, β_{0} will be given by partial solutions (u[i], v[j]) of minimal length satisfying x ∈ alph(u_{1}) ∩ alph(v[j]) for some x ∈ {a, d} (thus, α_{0}β_{0} ∈ b^{∗} ∪ c^{∗}). The automaton will accept if α = β = 1 and the counter is empty. It remains to describe the transition relation corresponding to the one-step transition described in Lem. 12, i.e., from (u[i], v[j]) to (u[i + s], v[j + t]). Updating α′, β′ according to the situations considered in Lem. 12 is not difficult. The only problem arises in the last case considered in Lem. 12, when b^{k}c^{l} ∈ X with kl ≠ 0 and the counter has to switch from b’s to c’s (or conversely). Roughly, the value of the counter has to be divided by k and multiplied by l (we may also have to increment/decrement the counter by a bounded value, i.e., a value depending on the finite state). Obviously, we cannot perform this combined operation using a single counter. The solution is to store instead of |α_{0}| − |β_{0}| the value (|α_{0}| − |β_{0}|) div k, if α_{0}β_{0} ∈ b^{∗}. Of course, we keep (|α_{0}| − |β_{0}|) mod k in the finite control. (Analogously, we store (|α_{0}| − |β_{0}|) div l in the counter, if α_{0}β_{0} ∈ c^{∗}.)

Remark. In order to be a trace code, X may contain at most two elements x_{1}, x_{2} with alph(x_{1}), alph(x_{2}) ⊆ {b, c}. More precisely, if x_{i} = b^{k_{i}}c^{l_{i}} then k_{1}l_{2} ≠ k_{2}l_{1} should hold. The second equation in the previous remark has to be replaced then by

c^{r}\binom{b^{k_{1}}}{c^{l_{1}}}^{t_{1}} \binom{b^{k_{2}}}{c^{l_{2}}}^{t_{2}}v_{j+t} = pβ′_{0}β′,  (2)

for t_{1}, t_{2} with t_{1} + t_{2} = t − 1. It can be shown in this case that if X is not a trace code, then we may suppose in the equation above that the difference |t_{1} − t_{2}| is bounded by X (i.e., there exists a suitable solution u_{1} ⋯ u_{n} = v_{1} ⋯ v_{m} with this property). In this case, we use the same method as for the code problem, with k_{1} + k_{2} (resp. l_{1} + l_{2}) replacing k (resp. l) and keeping |t_{1} − t_{2}| in the finite control.

Theorem 13 [13, 16]. Let Σ = {a, b, c, d} and 𝕄(Σ, I) be defined by three equations ab = ba, bc = cb, and cd = dc. Then the (trace) code problem for the independence alphabet (Σ, I) is decidable in polynomial time, actually it is NL-complete.

Proof sketch. For the complexity result in the theorem above recall that the hardness is already provided by the case of free monoids (over two letters alphabets) [19]. The code problem is shown to belong to NL by noting e.g. that one can test the existence of two different factorizations over a given X ⊆ 𝕄 by using a 2-way multi-head nondeterministic counter automaton. With the notations of Lem. 12 this automaton keeps track of α and β using two heads, which point at the corresponding elements of X in the input; the counter is used as in the proof of Thm. 13, whereas the modulo k, l values are handled by further heads on the input. Since the class of languages accepted by 2-way multi-head nondeterministic counter automata is known to coincide with NL [21], the result follows.

5 Clique-preserving morphisms

From the viewpoint of semantics codings may arise by refinement of actions. Assume we want to refine an action in such a way that it can be distributed to different parallel components. Then we may think of this as a homomorphism where a letter is mapped to a product of independent letters. This idea leads to the following definition, where (throughout this section) the notion of clique is meant w.r.t. independence alphabets.

Definition 14. A clique-preserving morphism of independence alphabets H, H: (Σ, I) → (Σ′, I′) is a relation H ⊆ Σ × Σ′ such that H(A) = {α ∈ Σ′ | (a, α) ∈ H, a ∈ A} is a clique of (Σ′, I′) whenever A ⊆ Σ is a clique of (Σ, I).

A clique-preserving morphism H ⊆ Σ × Σ′ yields in a natural way a homomorphism h: 𝕄(Σ, I) → 𝕄(Σ′, I′) by letting h(a) = ∏_{α∈H(a)} α for a ∈ Σ. Note that the product is well-defined since H(a) is (by definition) a clique, i.e., a set of commuting elements. Moreover, for (a, b) ∈ I we have

h(ab) = h(ba) = ∏_{α∈H(a)∪H(b)} α · ∏_{α∈H(a)∩H(b)} α

Remark. A clique-preserving morphism is not necessarily a morphism of undirected graphs as defined in Sect. 3. The reason is that for (a, b) ∈ I we may have H(a) ∩ H(b) ≠ ∅. Therefore the induced homomorphisms of trace monoids are not strong, in general. On the other hand, the strong coding defined in the Projection Lemma (Ex. 1) is clique-preserving, too.

Due to the next proposition we have a decidability result in the case where the left-hand side is free. This positive situation is in major contrast to Thm. 16 below.

Proposition 15. Let H ⊆ Σ × Σ′ be a relation such that H(a) is a clique of (Σ′, I′) for all a ∈ Σ. Then the induced homomorphism h: Σ^{∗} → 𝕄(Σ′, I′) with h(a) = ∏_{α∈H(a)} α is injective if and only if for all a, b ∈ Σ, a ≠ b there exists some (α, β) ∈ D′, α ≠ β with α ∈ H(a), β ∈ H(b).

The following result has been stated in [12] without proof:

Theorem 16. Given a clique-preserving morphism of independence alphabets H: (Σ, I) → (Σ′, I′), it is undecidable whether the associated homomorphism h: 𝕄(Σ, I) → 𝕄(Σ′, I′), h(a) = ∏_{α∈H(a)} α for a ∈ Σ, is a coding.

The following proof uses the undecidability of Post’s correspondence problem (PCP), stated as follows: given two homomorphisms f, g: Γ^{∗} → Γ′^{∗}, does some u ∈ Γ^{+} exist with f(u) = g(u)? For simplifying our reduction we impose following restrictions on the given PCP instances:

• 1 ≤ |f(a)|, |g(a)| ≤ 2 for every a ∈ Γ

• There exist x, y ∈ Γ, x ≠ y, such that f(u) = g(u) with u ∈ Γ^{+} implies u ∈ xΓ^{+}y; moreover, if the instance (f, g) has a solution, then also one in x(Γ_{0}Γ_{0})^{∗}Γ_{0}y, where Γ_{0} = Γ \{x, y}. Finally, for some α, β ∈ Γ′: f(x), g(x) ∈ αΓ′^{∗}, f(y), g(y) ∈ Γ′^{∗}β and α, β occur in no f(a), g(a), for a ∉ {x, y}.

One can show that PCP with these additional restrictions remains undecidable. This can be performed e.g. by slightly modifying the PCP pairs obtained in the reduction from the word problem for semi-Thue systems [11] (resp. imposing suitable restrictions on the semi-Thue systems). For the alphabet Σ_{0} defined below we will denote by Σ′_{0} the alphabet {a′ | a ∈ Σ_{0}}. Let

Σ_{0} = \{a_{b}, \overline{a}_{b} | a, b ∈ Γ_{0}\} ∪ \{a, \overline{a} | a ∈ Γ_{0}\} ∪ \{x_{1}, x_{2}, y_{1}, y_{2}\} ∪ \{\overline{a}_{x}, y_{b} | a, b ∈ Γ_{0}\} ,

and Σ_{1} = Σ_{0} ∪ Σ0^{′}. On Σ_{1} we have the independence relation I_{1} ⊆ Σ_{1} × Σ_{1}:

I_{1} = {(x_{1}, x′_{1}), (y_{2}, y′_{2}), (x′_{1}, x_{1}), (y′_{2}, y_{2})}.

For the second independence alphabet (Σ_{2}, I_{2}) let

Σ_{2} = \{A_{i}, \overline{A}_{i} | a ∈ Γ_{0}, 1 ≤ i ≤ 6\} ∪ \{X_{i}, Y_{i} | 1 ≤ i ≤ 6\} ∪ \{F, G, ^{|}c, $\} ∪ Γ′ , where we associate to every letter a ∈ Γ_{0} the capital letters A_{i}, \overline{A}_{i} (resp. X_{i} for x, resp. Y_{i} for y) for all 1 ≤ i ≤ 6. On Σ_{2} we define the dependence (independence, resp.) relation D_{2} ⊆ Σ_{2} × Σ_{2} (I_{2} ⊆ Σ_{2} × Σ_{2}, resp.) as symmetric relations satisfying:

(1) For all a ∈ Γ let D_{2} ∩ {A_{i} | 1 ≤ i ≤ 6}^{2} be (with self-loops omitted)

[figure: D_{2}:; A_{5}; A_{2}; A_{3}; A_{1}; A_{6}; A_{4}]

respectively, for a ∈ Γ_{0} and 1 ≤ i, j ≤ 6:

(\overline{A}_{i}, \overline{A}_{j}) ∈ D_{2} iff (A_{i}, A_{j}) ∈ D_{2} .

(2) For a ≠ b and i, j let (A_{i}, B_{j}) ∈ D_{2} and (\overline{A}_{i}, \overline{B}_{j}) ∈ D_{2}.

(3) For all a, b, i, j we define (A_{i}, \overline{B}_{j}) ∈ I_{2} if and only if

{(i, j), (j, i)} ∩ ({5, 6} × {1, 2} ∪ {4, 6} × {1, 3}) ≠ ∅ .

(4) Let D_{2}(γ) = Γ′ for all γ ∈ Γ′. Define further D_{2}(F) = D_{2}(G) = {F, G}, I_{2}(^{|}c) = {X_{1}, X_{2}, X_{3}, F, G} ∪ Γ′ and I_{2}($) = {Y_{4}, Y_{5}, Y_{6}, F, G} ∪ Γ′.

We define now a clique-preserving morphism H: (Σ_{1}, I_{1}) → (Σ_{2}, I_{2}) based on the given PCP instance f, g: Γ^{∗} → Γ′^{∗}. The associated homomorphism h will simulate the given (word) homomorphisms f, g using the control alphabet A_{i}, \overline{A}_{i}, F, G, . . .. More precisely, the control alphabet enforces by synchronization the presence of f- resp. g-images (since f(a) or g(a) may have length 2, we cannot generate them directly by a homomorphism associated to a cliquepreserving morphism.) We denote in the following by h(a)_{i}, i = 1, 2, a ∈ Γ, the ith letter of h(a) (resp. 1, if |h(a)| < i), with h ∈ {f, g}. In the definition below we have by convention k(a)_{i} ∈ H(c) only if k(a)_{i} ≠ 1, where c ∈ Σ_{1}, a ∈ Γ, and k ∈ {f, g}. However, for simplifying notations we write f(a)_{i}, g(a)_{i} throughout.

(1) For all a, b ∈ Γ_{0} let

\begin{aligned}H(a_{b}) & = & \{\overline{B}_{5}, \overline{B}_{6}, A_{1}, A_{2}, f(a)_{1}, F \} & H(a) & = & \{A_{3}, A_{4}, f(a)_{2}, G\} , \\ H(a′_{b}) & = & \{\overline{B}_{4}, \overline{B}_{6}, A_{1}, A_{3}, g(a)_{1}, F \} & H(a′) & = & \{A_{2}, A_{5}, g(a)_{2}, G\} , \end{aligned}

and analogously

\begin{aligned}H(\overline{a}_{b}) & = & \{B_{5}, B_{6}, \overline{A}_{1}, \overline{A}_{2}, f(a)_{1}, F \} & H(\overline{a}) & = & \{\overline{A}_{3}, \overline{A}_{4}, f(a)_{2}, G\} , \\ H(\overline{a}′_{b}) & = & \{B_{4}, B_{6}, \overline{A}_{1}, \overline{A}_{3}, g(a)_{1}, F \} & H(\overline{a}′) & = & \{\overline{A}_{2}, \overline{A}_{5}, g(a)_{2}, G\} . \end{aligned}

(2) Let for x_{i}, x′_{i} and a ∈ Γ_{0}:

\begin{aligned}H(x_{1}) & = & \{^{|}c, X_{1}, X_{2}, f(x)_{1}, F \} & H(x_{2}) & = & \{X_{3}, X_{4}, f(x)_{2}, G\} , \\ H(x′_{1}) & = & \{^{|}c, X_{1}, X_{3}, g(x)_{1}\} & H(x′_{2}) & = & \{X_{2}, X_{5}, g(x)_{2}\} , \end{aligned}

H(\overline{a}_{x}) = \{X_{5}, X_{6}, \overline{A}_{1}, \overline{A}_{2}, f(a)_{1}, F \}
H(\overline{a}′_{x}) = \{X_{4}, X_{6}, \overline{A}_{1}, \overline{A}_{3}, g(a)_{1}, F \}.

(3) For b ∈ Γ_{0} let:

\begin{aligned}H(y_{b}) & = & \{\overline{B}_{5}, \overline{B}_{6}, Y_{1}, Y_{2}, f(y)_{1}, F \} and \\ H(y′_{b}) & = & \{\overline{B}_{4}, \overline{B}_{6}, Y_{1}, Y_{3}, g(y)_{1}, F \} , \end{aligned}

together with

\begin{aligned}H(y_{1}) & = & \{Y_{3}, Y_{4}, f(y)_{2}\} & H(y_{2}) & = & \{Y_{5}, Y_{6}, $\} , \\ H(y′_{1}) & = & \{Y_{2}, Y_{5}, g(y)_{2}, G\} & H(y′_{2}) & = & \{Y_{4}, Y_{6}, F, $\} . \end{aligned}

With I_{1} = {(x_{1}, x′_{1}), (y_{2}, y′_{2}), (x′_{1}, x_{1}), (y′_{2}, y_{2})} it is easily seen that H is a cliquepreserving morphism of independence alphabets. Let h: 𝕄(Σ_{1}, I_{1}) → 𝕄(Σ_{2}, I_{2}) denote the associated homomorphism of trace monoids, h(a) = ∏_{A∈H(a)} A, a ∈ Σ_{1}. We defined H in such a way that every pair (u, v) ∈ 𝕄(Σ_{1}, I_{1})^{2} of minimal length |u| + |v| with h(u) = h(v) and u ≠ v satisfies alph(u) × alph(v) ⊆ Σ_{0} × Σ′_{0} ∪ Σ′_{0} × Σ_{0}.

Proposition 17. The homomorphism h: 𝕄(Σ_{1}, I_{1}) → 𝕄(Σ_{2}, I_{2}) associated to the clique-preserving morphism H is not injective if and only if the PCP instance (f, g) has a solution.

Proof. First, let us consider a solution u ∈ xΓ_{0}^{n}y for (f, g) with n odd. We have f(u) = g(u) with u = x a(1) ⋯ a(n) y, a(i) ∈ Γ_{0}. For a trace t = [a_{1} ⋯ a_{n}], a_{i} ∈ Σ_{0}, we will denote by t′ the trace [a′_{1} ⋯ a′_{n}]. It is easy to see that with

z = [x_{1}x_{2} \overline{a(1)}_{x}\overline{a(1)} a(2)_{a(1)}a(2) ⋯ \overline{a(n)}_{a(n−1)}\overline{a(n)} y_{a(n)} y_{1}y_{2}]

we obtain

F (GF)^{n+1} f(u) [^{|}c X_{1} ⋯ X_{6} \overline{A(1)}_{1} ⋯ \overline{A(1)}_{6} . . . . . . \overline{A(n)}_{1} ⋯ \overline{A(n)}_{6} Y_{1} ⋯ Y_{6} $] h(z) = h(z′) =

(For the vector-like representation above we use the fact that f(u), F (GF)^{n+1} commute pairwise, resp. with the first component.) For the converse, let us notice two properties of the clique-preserving morphism H used throughout the proof.

Fact 18 1. Zh(c) = h(c)Z for c ∈ Σ_{1} and Z ∈ \{A_{i}, \overline{A}_{i} | 1 ≤ i ≤ 6, a ∈ Γ } \ {X_{2}, X_{3}, Y_{4}, Y_{5}} is equivalent with (c, Z) ∈ H, i.e., Z ∈ alph(h(c)). For Z ∈ {X_{2}, X_{3}, Y_{4}, Y_{5}} we have Zh(c) = h(c)Z if and only if (c, Z) ∈ H or (c, Z) ∈ {(x′_{1}, X_{2}), (x_{1}, X_{3}), (y_{2}, Y_{4}), (y′_{2}, Y_{5})}.

2. For all Z ∈ \{A_{i}, \overline{A}_{i} | 2 ≤ i ≤ 5, a ∈ Γ_{0}\} ∪ \{X_{4}, Y_{2}\} we have two distinct letters c_{1}, c_{2} ∈ Σ_{1} satisfying (c_{i}, Z) ∈ H. Additionally, either F ∈ H(c_{1}) and G ∈ H(c_{2}), or F ∈ H(c_{2}) and G ∈ H(c_{1}) holds. This property will allow to determine c_{1} resp. c_{2} in a unique way, using (F, G) ∈ D_{2}.

We denote in the following for u ∈ 𝕄(Σ_{1}, I_{1}) by h^{∗}(u) the projection of h(u) on Σ_{2} \ Γ′, i.e., we consider the control letters, only. Assume now that h: 𝕄(Σ_{1}, I_{1}) → 𝕄(Σ_{2}, I_{2}) is not injective, and let u, v ∈ 𝕄(Σ_{1}, I_{1}), u ≠ v, be of minimal length |u| + |v| with h(u) = h(v). Note that for every (a, b) ∈ D_{1} \id_{Σ_{1}} one has (H(a)×H(b))∩(D_{2} \id_{Σ_{2}}) ≠ ∅. Moreover, by the minimality of |u|+|v| the initial alphabets of u resp. v are pairwise independent, i.e., in(u) × in(v) ⊆ I_{1}. Hence, two cases are possible: either in(u) = {x_{1}} and in(v) = {x′_{1}}, or in(u) = {y_{2}} and in(v) = {y′_{2}}. We first consider the case where in(u) = {x_{1}}, in(v) = {x′_{1}} and suppose u = x_{1}^{n}u_{1}, v = x′_{1}^{m}v_{1} for some u_{1}, v_{1} ∈ 𝕄(Σ_{1}, I_{1}) \ 1 with in(u_{1}) ≠ {x_{1}}, in(v_{1}) ≠ {x′_{1}}, and n, m ≥ 1. Hence, we have

h^{∗}(u) = ^{|}c^{n} {X_{1}^{n} \atop X_{2}^{n}} F^{n}h^{∗}(u_{1}) = ^{|}c^{m} {X_{1}^{m} \atop X_{3}^{m}} h^{∗}(v_{1}) = h^{∗}(v) .

Due to the condition imposed on the initial alphabets of u_{1}, v_{1} we immediately follow n = m. Moreover, recalling Fact 18(1) and the minimality of |u| + |v|, we obtain in(u_{1}) = {x_{2}} and in(v_{1}) = {x′_{2}}. Actually, since {X_{4}, X_{5}} ⊆ D_{2}(^{|}c) we may observe that u_{1} = x_{2}^{n}u_{2} and v_{1} = x′_{2}^{n}v_{2} holds for some u_{2}, v_{2} (neither u_{1} ∈ x_{2}^{i}x′_{1}𝕄(Σ_{1}, I_{1}) nor v_{1} ∈ x′_{2}^{i}x_{1}𝕄(Σ_{1}, I_{1}) can lead to a solution, if i < n). Therefore, we obtain the following situation (we omit in the representations below dependence edges from ^{|}c):

h^{∗}(u) = ^{|}c^{n} {X_{1}^{n}X_{2}^{n}X_{3}^{n}X_{4}^{n} \atop F^{n}G^{n}} h^{∗}(u_{2}) = ^{|}c^{n}X_{1}^{n}X_{3}^{n}X_{2}^{n}X_{5}^{n}h^{∗}(v_{2}) = h^{∗}(v) .

Fact 18(2) applied to X_{4} yields now directly v_{2} = \overline{a}′_{x}^{n}v_{3}, for some v_{3} and a ∈ Γ_{0}. Since X_{5} ∈ in(h(u_{2})) we have \{ā_{x}, x′_{2}\} ∩ in(u_{2}) ≠ ∅. Due to (\overline{a}′_{x}, \overline{A}_{1}) ∈ H and (\overline{A}_{1}, X_{2}) ∈ D_{2}, we obtain u_{2} = \overline{a}_{x}^{n}u_{3}, for some u_{3}. This yields the partial solution:

\begin{aligned}& ^{|}c^{n} & X_{1}^{n} ⋯ X_{6}^{n} & \overline{A}_{1}^{n}\overline{A}_{2}^{n} \\ h(u) = & & F^{n} G^{n} & F^{n} & h(u_{3}) = \\ & & (f(x)_{1})^{n} (f(x)_{2})^{n} & (f(a)_{1})^{n} \end{aligned} ; \begin{aligned}& ^{|}c^{n} & X_{1}^{n} ⋯ X_{6}^{n} & \overline{A}_{1}^{n}\overline{A}_{3}^{n} \\ h(v) = & & F^{n} & & h(v_{3}) . \\ & & (g(x)_{1})^{n} (g(x)_{2})^{n} & (g(a)_{1})^{n} \end{aligned}

More generally, let us assume

h^{∗}(u) = W \begin{matrix}\overline{A} & {n \atop 1} \\ G^{n} \end{matrix} \begin{matrix}\overline{A} & {n \atop 2} \\ F^{n} \end{matrix} h^{∗}(u_{1}) = W ^{\overline{A}_{1}^{n}} ^{\overline{A}_{3}^{n}} h^{∗}(v_{1}) = h^{∗}(v) ,

for a ∉ {x, y}, W ∈ 𝕄(Σ_{2}, I_{2}), u_{1}, v_{1} ∈ 𝕄(Σ_{1}, I_{1}). Due to \overline{A}_{2} ∈ in(h(v_{1})), together with Fact 18(2), we immediately obtain v_{1} =

\overline{a}′^{n}v_{2} for some v_{2}, hence h^{∗}(v) = W \begin{aligned}\overline{A} & {n \atop 1} & \overline{A} & {n \atop 3} & \overline{A} & {n \atop 2} & \overline{A} & {n \atop 5} \\ & G^{n} \end{aligned} h^{∗}(v_{2}). With \overline{A}_{3} ∈ in(h(u_{1})) we

need a letter c ∈ Σ satisfying (c, \overline{A}_{3}) ∈ H and alph(h(c))∩D(\overline{A}_{5}) ⊆ \{\overline{A}_{3}\}; hence,

c = \overline{a} and u_{1} = \overline{a}^{n}u_{2}, for some u_{2}. This yields h^{∗}(u) = W \begin{matrix}\overline{A} & {n \atop 1} & \overline{A} & {n \atop 2} & \overline{A} & {n \atop 3} & \overline{A} & {n \atop 4} \\ G^{n}F^{n}G^{n} \end{matrix} h^{∗}(u_{2}).

Finally, \overline{A}_{4} ∈ in(h(v_{2})), together with Fact 18(2) yields v_{2} = b′_{a}^{n}v_{3} and

h^{∗}(v) = W \begin{matrix}\overline{A} & {n \atop 1} & ⋯ & \overline{A} & {n \atop 6} \\ G^{n}F^{n} \end{matrix} B_{1}^{n}B_{3}^{n} h^{∗}(v_{3}) ,

for some b ≠ x and v_{3} ∈ 𝕄(Σ_{1}, I_{1}); on the other hand, the condition \overline{A}_{5} ∈ in(h(u_{2})) requires a letter c ∈ Σ_{1} with (c, \overline{A}_{5}) ∈ H and B_{1}h(c) = h(c)B_{1},

hence c = b_{a} and u_{2} = b_{a}^{n}u_{3}, with h^{∗}(u) = W \begin{matrix}\overline{A} & {n \atop 1} & ··· & \overline{A} & {n \atop 6} \\ G^{n}F^{n}G^{n}F^{n} \end{matrix} ^{B_{1}^{n}B_{2}^{n}} h^{∗}(u_{3}), for some

u_{3} ∈ 𝕄(Σ_{1}, I_{1}). The case h^{∗}(u) = W {A_{1}^{n} \atop G^{n}} {A_{2}^{n} \atop F^{n}} h^{∗}(u_{1}) = h^{∗}(v) = W A_{1}^{n}A_{3}^{n}h^{∗}(v_{1}), a ≠ y, is symmetric. Therefore, we suppose now a = y. We observe that the same arguments used above for \overline{A}_{2}, \overline{A}_{3} hold (dually) for Y_{2}, Y_{3} (in particular, by Fact 18(2)). Hence,

h^{∗}(u) = W {Y_{1}^{n}Y_{2}^{n}Y_{3}^{n}Y_{4}^{n} \atop G^{n}F^{n}} h^{∗}(u_{2}) = W {Y_{1}^{n}Y_{3}^{n}Y_{2}^{n}Y_{5}^{n} \atop G^{n}} h^{∗}(v_{2}) = h^{∗}(v) .

Thus we obtained w = [x_{1}^{n}x_{2}^{n} \overline{a_{1}}_{x}^{n}\overline{a_{1}}^{n} a_{2}_{a_{1}}^{n}a_{2}^{n} ⋯ \overline{a_{m}}_{a_{m−1}}^{n} \overline{a_{m}}^{n} y_{a_{m}}^{n} y_{1}^{n}], a_{i} ∈ Γ_{0}, n, m ≥ 1, such that u = wu_{2} and v = w′v_{2} for some u_{2}, v_{2} (recall that w′ denotes the Σ′_{0}-copy of w ∈ Σ_{0}^{∗}). Recall that f(y), g(y) ∈ Γ′^{∗}β and β occurs in no f(a), g(a), for a ∉ {x, y}. Hence, we obtained

\begin{matrix}(f(x)_{1})^{n}(f(x)_{2})^{n}(f(a_{1})_{1})^{n}(f(a_{1})_{2})^{n} ⋯ (f(a_{m})_{1})^{n}(f(a_{m})_{2})^{n}(f(y)_{1})^{n}(f(y)_{2})^{n} & = \\ (g(x)_{1})^{n}(g(x)_{2})^{n}(g(a_{1})_{1})^{n}(g(a_{1})_{2})^{n} ⋯ (g(a_{m})_{1})^{n}(g(a_{m})_{2})^{n}(g(y)_{1})^{n}(g(y)_{2})^{n} . \end{matrix}

It is now easy to check that z = x a_{1} ⋯ a_{m} y satisfies f(z) = g(z), hence z is a solution for the PCP instance (f, g).

It remains to consider a pair (u, v) ∈ 𝕄(Σ, I)^{2}, u ≠ v, of minimal length |u|+|v|, with h(u) = h(v), which satisfies in(u) = {y′_{2}}, in(v) = {y_{2}}. Assume u = y′_{2}^{n}u_{1} and v = y_{2}^{m}v_{1} with u_{1}, v_{1} such that in(u_{1}) ≠ {y′_{2}}, in(v_{1}) ≠ {y_{2}}. Again, m = n follows immediately. Hence, we obtain

h^{∗}(u) = $^{n} {Y_{6}^{n}Y_{4}^{n} \atop F^{n}} h^{∗}(u_{1}) = $^{n} Y_{6}^{n}Y_{5}^{n} h^{∗}(v_{1}) = h^{∗}(v) .

This case can now be handled as the first one, replacing A_{1}, A_{2}, A_{3}, A_{4}, A_{5}, A_{6} by A_{6}, A_{4}, A_{5}, A_{2}, A_{3}, A_{1} (\overline{A}_{i} analogously) and interchanging x, y. This concludes the proof.

References

1. IJ. J. Aalbersberg and H. J. Hoogeboom. Characterizations of the decidability of some problems for regular trace languages. Mathematical Systems Theory, 22:1–19, 1989.

2. J. Berstel and D. Perrin. Theory of Codes. Pure and Applied Mathematics; 117. Academic Press, Orlando, Florida, 1985.

3. A. Bertoni, G. Mauri, and N. Sabadini. Equivalence and membership problems for regular trace languages. In Proceedings of the 9th International Colloquium on Automata, Languages and Programming (ICALP’82), number 140 in Lecture Notes in Computer Science, pages 61–71, Berlin-Heidelberg-New York, 1982. Springer.

4. V. Bruyère and C. De Felice. Trace codings. In E. 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.

5. V. Bruyère and C. De Felice. Any lifting of a trace coding is a word coding. Submitted for publication, 1996.

6. V. Bruyère, C. De Felice, and G. Guaiana. Coding with traces. In P. Enjalbert, E. 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.

7. P. Cartier and D. Foata. Problèmes combinatoires de commutation et réarrangements. Number 85 in Lecture Notes in Mathematics. Springer, Berlin-Heidelberg-New York, 1969.

8. M. Chrobak and W. Rytter. Unique decipherability for partially commutative alphabets. Fundamenta Informaticae, X:323–336, 1987.

9. M. Clerbout and M. Latteux. Partial commutations and faithful rational transductions. Theoretical Computer Science, 34:241–254, 1984.

10. R. Cori and D. Perrin. Automates et commutations partielles. R.A.I.R.O. — Informatique Théorique et Applications, 19:21–32, 1985.

11. M. D. Davis and E. J. Weyuker. Computability, complexity and languages. Academic Press, New York, 1983.

12. V. Diekert, A. Muscholl, and K. Reinhardt. On codings of traces. In E. 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.

13. H. J. Hoogeboom and A. Muscholl. The code problem for traces – improving the boundaries. Submitted for publication.

14. G. Hotz and V. Claus. Automatentheorie und Formale Sprachen, Band III. Bibliographisches Institut, Mannheim, 1972.

15. G. S. Makanin. The problem of solvability of equations in free semigroups. Math. USSR Izvestiya, 21:483–546, 1983.

16. Yu. Matyiasevich. Cas décidables et indécidables du problème du codage pour les monoïdes partialement commutatifs. To appear in Quadrature.

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

18. E. Ochmański. On morphisms of trace monoids. In R. 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.

19. W. Rytter. The space complexity of the unique decipherability problem. Information Processing Letters, 23:1–3, 1986.

20. J. Sakarovitch. The “last” decision problem for rational trace languages. In I. 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.

21. K. Wagner and G. Wechsung. Computational complexity. VEB Deutscher Verlag der Wissenschaften, Berlin, 1986.

22. E. S. Wolk. A note on the comparability graph of a tree. Proc. of the Amer. Math. Soc., (16):17–20, 1965.

This article was processed using the L^{A}TEX macro package with LLNCS style