On Codings of Traces

Extended Abstract ⋆

Volker Diekert  Anca Muscholl  Klaus Reinhardt

Institut für Informatik, Universität Stuttgart Breitwiesenstr. 20-22, D-70565 Stuttgart e-mail: {diekert,muscholl,reinhard}@informatik.uni-stuttgart.de

Abstract. The paper solves the main open problem of [BFG94]. We show that given two dependence alphabets (Σ, D) and (Σ′, D′), it is decidable whether there exists a strong coding h : M(Σ, D) ⟶ M(Σ′, D′) between the associated trace monoids. In fact, we show that the problem is NP-complete. (A coding is an injective homomorphism, it is strong if independent letters are mapped to independent traces.) We exhibit an example of trace monoids where a coding between them exists, but no strong coding. The decidability of codings remains open, in general. We have a lower and an upper bound, which show both to be strict. We further discuss encodings of free products of trace monoids and give almost optimal constructions. In the final section, we state that the coding property is undecidable in a naturally arising class of homomorphisms.

Topics: Formal languages, concurrency.

1 Introduction

The theory of traces has been recognized as an important tool for investigations about concurrent systems, see [DR95]. The origins of the theory go back to the work of Mazurkiewicz (trace theory), Karp/Miller, Keller (parallel program schemata), and Cartier/Foata (combinatorics), see [Maz87, Kel73, CF69]. Traces are of particular interest for a description of concurrent processes, since for many algorithms one can obtain complexity bounds, which are close to the corresponding algorithms on words, e.g. test of equality [AG91], pattern matching [HY92], or word problems [Die89, Die90]. A convenient data structure for these algorithms is a representation of traces as a tuple of words. This is nothing but a coding of a trace monoid in a direct product of free monoids and leads to the general problem to find codings between trace monoids. This question has been raised by Ochmański in [Och88] and reconsidered recently by Bruyère et al. in [BFG94] (see also [BF95] in this volume). A natural class of codings of trace monoids is given by strong codings. These are injective homomorphisms

⋆ This research has been supported by the ESPRIT Basic Research Action No. 6317 ASMICS 2, Algebraic and Syntactic Methods In Computer Science.

such that independent letters are mapped to independent traces (similar to a refinement of actions in a concurrent system). The main result of [BFG94] is the decidability of the existence of a strong coding for two large families of trace monoids, but the authors left open the general problem: given two trace monoids M(Σ, D) and M(Σ′, D′), is it decidable whether there exists a strong coding of one into the other. The main result of the present paper solves this problem. We give a graph theoretical criterion for the existence of a strong coding thereby showing its NP-completeness, see Thm. 9. The paper contains several other results. As mentioned above, from the viewpoint of applications, the most important codings are those into a direct product of free monoids. Again, there is a characterization for strong codings, which is directly related to a covering by cliques and which shows the NP-completeness of this restricted problem, too. Much less is known if we consider codings (i.e., injective homomorphisms), instead of strong codings. For certain dependence alphabets we are able to compute the least k for the existence of an encoding of the trace monoid into a k-fold direct product (e.g., the path and the cycle of n vertices). We show that if the dependence alphabet is a cycle of four vertices, then the associated trace monoid has a coding into a direct product of free monoids with two components, whereas at least four are needed for a strong coding. The existence of a coding between trace monoids is NP-hard, but we even do not know its decidability in the restricted case where the second monoid is a direct product of free monoids. We have a lower bound for the minimal number of components we need by the size of a maximal independent set and an upper bound by the number of cliques which are needed to cover all vertices and edges. The exact value remains unknown. We give an example of a dependence alphabet (which is in fact a cograph), where both the lower and the upper bounds are strict. Finally, we give almost optimal constructions for encoding free products of trace monoids into direct products of free monoids. The results can be used for encoding efficiently trace monoids with a cograph dependence alphabet. In the final section we reconsider the well-known result on the undecidability of whether a given homomorphism of trace monoids is a coding. The proof [HC72, CR87] uses a reduction of the Post correspondence problem, and it does not apply to restricted classes of homomorphisms. In this paper we start with a so-called strict morphism between independence alphabets. These morphisms induce in a canonical way homomorphisms between the associated trace monoids. (The homomorphism of the Projection Lemma is of this kind.) Thm. 22 states that the coding property for this natural class of homomorphisms is undecidable.

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 (which however will be omitted in pictures). An undirected graph is simply a pair (V, E), where E ⊆ V × V is a symmetric relation. We use the following basic operations on graphs: complementation \overline{(V, E)} = (V, (V ×V)\E), disjoint union (V_{1}, E_{1}) ˙⋃(V_{2}, E_{2}) = (V_{1} ˙⋃ V_{2}, E_{1} ˙⋃ E_{2}), and complex product (V_{1}, E_{1}) ∗ (V_{2}, E_{2}) = (V_{1} ˙⋃ V_{2}, E_{1} ˙⋃ E_{2} ˙⋃(V_{1} × V_{2}) ˙⋃(V_{2} × V_{1})). (The smallest family of graphs containing the one-point graphs which is closed under these operations is the family of cographs, see e.g. [CLB81, CPS85].) Given a dependence alphabet (Σ, D) (or an independence alphabet (Σ, I) resp.) we associate the trace monoid M(Σ, D). This is the quotient monoid Σ^{∗}/{ab = ba | (a, b) ∈ I}; an element t ∈ M(Σ, D) 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′ : t = xt′}. By 1 we denote both the empty word and the empty trace. Traces s, t ∈ M(Σ, D) 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. A trace t is called connected, if alph(t) induces a connected subgraph of the dependence alphabet (Σ, D). The constructions disjoint union and complex product resp., on dependence alphabets correspond to the direct product and the free product (= direct sum in the category of monoids) resp., for the associated trace monoids. Thus, we have M((Σ_{1}, D_{1}) ˙⋃(Σ_{2}, D_{2})) = M(Σ_{1}, D_{1}) × M(Σ_{2}, D_{2}) and M((Σ_{1}, D_{1}) ∗ (Σ_{2}, D_{2})) = M(Σ_{1}, D_{1}) ∗ M(Σ_{2}, D_{2}). The situation for independence alphabets is dual. Let Σ′ ⊆ Σ be a subalphabet and D′ = (Σ′ × Σ′) ∩ D the induced dependence relation. The canonical projection π_{Σ′} : M(Σ, D) → M(Σ′, D′) is induced by π_{Σ′}(a) = a, if a ∈ Σ′ and π_{Σ′}(a) = 1 otherwise. Consider (Σ, D) written as a union of cliques, i.e., (Σ, D) = (⋃_{i=1}^{k} Σ_{i}, ⋃_{i=1}^{k} Σ_{i} × Σ_{i}). Then we have the following well-known Projection Lemma:

Proposition 1 [CL85 , CP85 ]. Let (Σ, D) = (⋃_{i=1}^{k} Σ_{i}, ⋃_{i=1}^{k} Σ_{i} × Σ_{i}). Then the canonical homomorphism

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

is injective.

In the following a homomorphism h : M(Σ, D) → M(Σ′, D′) is called a coding, if it is injective. It is called a strong homomorphism, if independent letters are mapped to independent traces, i.e., if (a, b) ∈ I implies (h(a), h(b)) ∈ I′ for all a, b ∈ Σ. Of particular interest are strong codings, a notion which has been introduced in [BFG94]. The next proposition belongs probably to folklore:

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

1. The dependence alphabet (Σ, D) contains an independent set of size k.

2. There exists a strong coding h : IN^{k} → M(Σ, D).

3. There exists a coding h : IN^{k} → M(Σ, D).

Proof. Since the implications 1) ⇒ 2) ⇒ 3) are obvious, we show 3) ⇒ 1). Let {a_{1}, …, a_{k}} be a set of generators of IN^{k} and let t_{i} = h(a_{i}), 1 ≤ i ≤ k. By a result of Duboc [Dub86] the equations t_{i}t_{j} = t_{j}t_{i} (1 ≤ i ≠ j ≤ k) yield the existence of pairwise independent, connected roots x_{1}, …, x_{l}, together with nonnegative integers n_{ij} (1 ≤ i ≤ k, 1 ≤ j ≤ l) such that t_{i} = x_{1}^{n_{i1}} ⋯ x_{l}^{n_{il}} for 1 ≤ i ≤ k. The set of roots {x_{1}, …, x_{l}} generates a commutative submonoid of M(Σ, D), and the coding factorizes as h : IN^{k} → IN^{l} → M(Σ, D). With h being injective we have k ≤ l by linear algebra. Finally, it suffices to choose some letter b_{i} ∈ alph(x_{i}), 1 ≤ i ≤ l, in order to establish the result.

Corollary 3. It is NP-complete to decide whether there exists a (strong) coding of IN^{k} into M(Σ, D). Therefore, the problem whether there exists a (strong) coding between two given trace monoids is (at least) NP-hard.

3 Characterization of the existence of strong codings

Strong codings between trace monoids are closely related to morphisms of (in-) dependence alphabets.

Definition 4. Let (V, E) and (V′, E′) be undirected graphs. A morphism H : (V, E) → (V′, E′) is a relation between vertices H ⊆ V × V′ such that (a, b) ∈ E implies H(a) × H(b) ⊆ E′ for all a, b ∈ V. (By H(a) we mean the set {α ∈ V′ | (a, α) ∈ H} for a ∈ V.)

Obviously, undirected graphs with these morphisms form a category. For H ⊆ V × V′ we denote by H^{−1} the inverse relation H^{−1} = {(α, a) ∈ V′ × V | (a, α) ∈ H}. A relation H ⊆ V × V′ is a morphism H : (V, E) → (V′, E′) if and only if H^{−1} : \overline{(V′, E′)} → \overline{(V, E)} is a morphism on the complement graphs in the opposite direction. Hence, complementation yields a duality of the category. The basic relation between strong homomorphisms of trace monoids and morphisms of undirected graphs is given by the next lemma, which follows directly from the above definitions.

Lemma 5. Let h : M(Σ, D) → M(Σ′, D′) be a homomorphism of trace monoids. Define H ⊆ Σ × Σ′ as

H = {(a, α) ∈ Σ × Σ′ | α ∈ alph(h(a))}.

The following assertions are equivalent:

1. h : M(Σ, D) → M(Σ′, D′) is a strong homomorphism.

2. H : (Σ, I) → (Σ′, I′) is a morphism of independence alphabets.

3. H^{−1} : (Σ′, D′) → (Σ, D) is a morphism of dependence alphabets.

Definition 6. A morphism G : (Σ′, D′) → (Σ, D) of dependence alphabets is called covering, if for all a ∈ Σ there exists α ∈ Σ′ with a ∈ G(α) and if for all (a, b) ∈ D, a ≠ b there exists (α, β) ∈ D′, α ≠ β with (a, b) ∈ G(α) × G(β).

The following lemma is stated with a different notation in [BFG94].

Lemma 7. Let h : M(Σ, D) → M(Σ′, D′) be a strong coding. Define H = {(a, α) ∈ Σ × Σ′ | α ∈ alph(h(a))}. Then H^{−1} : (Σ′, D′) → (Σ, D) is a covering of dependence alphabets.

Proof. By Lem. 5 the relation H^{−1} is a morphism. Let a ∈ Σ, then h(a) ≠ 1, since h is a coding. Hence a ∈ H^{−1}(α) for some α ∈ Σ′. Now, let (a, b) ∈ D, a ≠ b. Since h(ab) ≠ h(ba) we find by Prop. 1 a pair (α, β) ∈ D′, α ≠ β such that π_{α,β}h(ab) ≠ π_{α,β}h(ba). Thus, either (a, b) ∈ H^{−1}(α) × H^{−1}(β) or (a, b) ∈ H^{−1}(β) × H^{−1}(α) holds. In any case H^{−1} is a covering.

Lemma 8. Let H ⊆ Σ × Σ′ be a relation such that H^{−1} : (Σ′, D′) → (Σ, D) is a covering of dependence alphabets. Then there exists a strong coding h : M(Σ, D) → M(Σ′, D′) such that H = {(a, α) ∈ Σ × Σ′ | α ∈ alph(h(a))}.

Proof. Let Σ = \{a_{1}, a_{2}, ...\} and Σ′ = \{α_{1}, α_{2}, ...\}. For each i define \overrightarrow{H(a_{i})} =

α_{i_{1}} ⋯ α_{i_{k}} and \overleftarrow{H(a_{i})} = α_{i_{k}} ⋯ α_{i_{1}}, where H(a_{i}) = \{α_{i_{1}}, …, α_{i_{k}}\} and i_{1} < ⋯ < i_{k}. For i = 1, 2, … let

h(a_{i}) = ( \overrightarrow{H(a_{i})} )^{i} \overleftarrow{H(a_{i})}.

Lem. 5 states that h is a strong homomorphism. We have to show that h is injective, only. First note that h(a) ≠ 1 for all a ∈ Σ. Assume by contradiction that h(x) = h(y) for some x ≠ y. Let x be of minimal length with this property. Then x = ax′ for some a ∈ Σ, x′ ∈ M(Σ, D). Since h is strong and h(x) = h(y), there is some b ∈ alph(y) with (a, b) ∈ D. Hence we can write y = zby′ for some b ∈ Σ, y′, z ∈ M(Σ, D) such that (a, z) ∈ I and (a, b) ∈ D. We have a ≠ b since x is of minimal length. Since H^{−1} is a covering, we find (α, β) ∈ D′, α ≠ β such that α ∈ alph(h(a)) and β ∈ alph(h(b)). For the contradiction it is enough to show π_{α,β}h(x) ≠ π_{α,β}h(y). Since h is strong, we have π_{α,β}h(z) = 1. We may assume that α comes before β in Σ′. Let a = a_{i} and b = a_{j} (i ≠ j). We have π_{α,β}h(a) = (αβ^{ϵ})^{i} (β^{ϵ}α) and π_{α,β}h(b) = (α^{δ}β)^{j} (βα^{δ}) for some δ, ϵ ∈ {0, 1}. It follows that neither π_{α,β}h(a) is a prefix of π_{α,β}h(y) nor π_{α,β}h(zb) is a prefix of π_{α,β}h(x). Hence h(x) = h(y) is impossible.

The following result solves the main open problem of [BFG94]. It follows by the conjunction of Lem. 7 and Lem. 8.

Theorem 9. Let (Σ, D) and (Σ′, D′) be dependence alphabets. The following assertions are equivalent:

1. There exists a strong coding h : M(Σ, D) → M(Σ′, D′).

2. There exists a covering G : (Σ′, D′) → (Σ, D) of dependence alphabets.

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

Corollary 10. The following problem is NP-complete: Input: Dependence alphabets (Σ, D), (Σ′, D′). Question: Does there exist a strong coding from M(Σ, D) into M(Σ′, D′)?

4 Codings into direct products of free monoids

In this section we investigate codings of a trace monoid into a k-fold direct product of free monoids. We are interested in the smallest possible value of k. For strong codings the situation is clear, as stated in Prop. 12 below. (This result follows also from [BFG94].)

Lemma 11. Let h : M(Σ, D) → ∏_{i=1}^{k} Σ_{i}^{∗} be a strong coding into a k-fold direct product of free monoids. Let π_{i} = π_{Σ_{i}} denote the canonical projection onto the i-th component and C_{i} = {a ∈ Σ | π_{i}h(a) ≠ 1}, i = 1, …, k. Then C_{i} is a (dependence) clique for all i = 1, …, k and (Σ, D) = (⋃_{i=1}^{k} C_{i}, ⋃_{i=1}^{k} C_{i} × C_{i}).

Proof. Since h is injective, each (a, b) ∈ D is contained in some C_{i} × C_{i}. The set C_{i} is a clique, i = 1, …, k, since h is strong.

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

Proof. One direction is Lem. 11, the other follows from the Projection Lemma, Prop. 1. The question, whether the vertices and edges of a given graph can be covered by k cliques, is NP-complete, see [GJ78] for details.

4.1 A lower bound

We now turn to the problem of codings into direct products without the property of being a strong homomorphism. The following example shows a dependence alphabet where the existence of a coding into a k-fold direct product of free monoids also requires a covering by k cliques. Hence, in the example, the bound of Prop. 12 is optimal for codings, too.

Example 1. Let (Σ, D) = P_{n} be the path of length n ≥ 1, i.e., Σ = {a_{1}, …, a_{n}} with D = {(a_{p}, a_{q}) | 1 ≤ p, q ≤ n, |p−q| ≤ 1}. Suppose h : M(Σ, D) → ∏_{i=1}^{k} Σ_{i}^{∗} is a coding. Then we have k ≥ n − 1.

Proof. Assume by contradiction that there is an embedding h into a k-fold direct product, k ≤ n − 2. For 1 ≤ m < n let A_{m} = {i | 1 ≤ i ≤ k, h_{i}(a_{m}a_{m+1}) ≠ h_{i}(a_{m+1}a_{m})}, with h_{i} = π_{i}h. Clearly, A_{m} ≠ ∅ and | ⋃_{m=1}^{n−1} A_{m}| ≤ n−2. Moreover, for every 1 ≤ l < m < n with m ≥ l + 2 we have A_{m} ∩ A_{l} = ∅ (since {a_{m+1}} × {a_{l}, a_{l+1}} ⊆ I and thus h_{i}(a_{m+1}) = 1 for i ∈ A_{l}). Now, let 1 ≤ p < q ≤ n with q − p minimal such that | ⋃_{m=p}^{q−1} A_{m}| ≤ q − p − 1. Then A_{m} ∩ A_{m+1} ≠ ∅ for every p ≤ m < q − 1 follows by the minimality of q − p, together with the above observation. Furthermore, we have |A_{m} ∪ A_{m+1}| ≥ 2 (otherwise, it is easy to see that nonnegative integers r, s ≥ 1 exist, such that h(a_{m}^{r}a_{m+1}a_{m+2}^{s}) = h(a_{m+2}^{s}a_{m+1}a_{m}^{r})). We can now deduce that after renumbering we have A_{p} = {p}, A_{m} = {m − 1, m} (p < m < q − 1) and A_{q−1} = {q − 2}. The final step is to show the existence of integers k_{i} ≥ 1 (p ≤ i ≤ q) with h(a_{p}^{k_{p}} ⋯ a_{q}^{k_{q}}) = h(a_{q}^{k_{q}} ⋯ a_{p}^{k_{p}}) (note q > p), which yields the contradiction. For this, write h_{m}(a_{m}) = r_{m}^{s_{m}} and h_{m}(a_{m+2}) = r_{m}^{t_{m}}, for some words r_{m} and integers s_{m}, t_{m} ≥ 1, p ≤ m ≤ q − 2. The claimed k_{i}, p ≤ i ≤ q, are now chosen as a (positive) solution of the system of (q − p − 2) equations s_{m} · k_{m} = t_{m} · k_{m+2}.

Remark. It is interesting to note that if (Σ, D) corresponds to C_{n} (the cycle of length n) and n ≥ 5, then the optimal k for encoding M(Σ, D) into a k-fold direct product of free monoids is again k = n − 1. The lower bound can be seen using the above result on | ⋃_{m=1}^{n−1} A_{m}|. For C_{4} we can do better, see Ex. 2 below.

In the following we denote by α(Σ, D) the size of a maximal independent set of (Σ, D). Lem. 11 yields the following obvious lower bound.

Proposition 13. Let h : M(Σ, D) → ∏_{i=1}^{k} Σ_{i}^{∗} be a coding. Then we have α(Σ, D) ≤ k.

Proof. IN^{α(Σ,D)} is a submonoid of M(Σ, D).

4.2 Inductive methods

The following example (also used in [BF95]) provides two observations: For some codings we can achieve the lower bound α(Σ, D) of Prop. 13, and we may find a coding into a k-fold direct product, where no strong coding exists.

Example 2. Let (Σ, D) be a C_{4}, i.e., a cycle with four letters.

(Σ, D) = \begin{matrix}a & − & d \\ | & & | \\ b & − & c \end{matrix}

Then there is a coding h : M(Σ, D) → {a, b}^{∗} × {c, d}^{∗}. Thus for a coding a 2-fold (2 = α(Σ, D)) direct product of free monoids is enough, whereas for a strong coding we need four components by Prop. 12.

Proof. Choose any nonnegative integers m_{1}, m_{2}, n_{1}, n_{2} > 0 such that the matrix

( \begin{matrix}m_{1} & n_{1} \\ m_{2} & n_{2} \end{matrix} ) is non-singular. Define h : M(Σ, D) → \{a, b\}^{∗} × \{c, d\}^{∗} by

h(a) = (a^{m_{1}}, c^{n_{1}}), h(b) = (b^{m_{1}}, d^{n_{1}}), h(c) = (a^{m_{2}}, c^{n_{2}}), h(d) = (b^{m_{2}}, d^{n_{2}}).

It is easily seen that h is injective. The basic observation is that M(Σ, D) has the algebraic structure of a free product of IN^{2} by IN^{2}.

In fact, Ex. 2 reveals a more general principle.

Proposition 14. Let h_{j} : M(Σ_{j}, D_{j}) → ∏_{i=1}^{k} Γ_{i}^{∗} be codings such that |Γ_{i}| ≥ 2 and π_{i}h_{j}(a) ≠ 1 for all a ∈ Σ_{j}, i = 1, …, k, j = 1, …, m. Then there exists a

coding h : ∗_{j=1}^{m} M(Σ_{j}, D_{j}) → ∏_{i=1}^{k} Γ_{i}^{∗}, where ∗_{j=1}^{m} M(Σ_{j}, D_{j}) denotes the m-fold

free product. Furthermore, we find h such that π_{i}h(a) ≠ 1 for all a ∈ ˙⋃_{j=1}^{m} Σ_{j} and i = 1, …, k.

Proof. (Sketch) For each j replace Γ_{i} by some Γ_{ij} such that the alphabets become disjoint for different j. The codings h_{j} define a canonical homomorphism \overline{h} : ∗_{j=1}^{m} M(Σ_{j}, D_{j}) → ∏_{i=1}^{k}( ˙⋃_{j=1}^{m} Γ_{ij})^{∗}. Since π_{i}h_{j}(a) ≠ 1 it is easy to see that \overline{h} is

a coding. Furthermore, we have π_{i}\overline{h}(a) ≠ 1 for all a ∈ ˙⋃_{j=1}^{m} Σ_{j}.

Finally, since |Γ_{i}| ≥ 2 for all i = 1, …, k, we can code ( ˙⋃_{j=1}^{m} Γ_{ij})^{∗} into Γ_{i}^{∗}.

Corollary 15. Let k, m ≥ 1 and a, b different letters, a ≠ b. Then there exists

a coding h : ∗_{i=1}^{m} IN^{k} → ∏_{i=1}^{k}{a, b}^{∗}.

Unfortunately, the hypothesis π_{i}h_{j}(a) ≠ 1 of Prop. 14 is very strong. As soon as (Σ, D) contains three letters a, b, c such that (a, b) ∈ D, (a, c) ∈ I, and (b, c) ∈ I it cannot be satisfied anymore. Even for cographs (Σ, D) the number k = α(Σ, D) is, in general, not large enough in order to allow a coding of M(Σ, D) into a k-fold direct product of free monoids. We have the following example showing the strictness of our lower and upper bounds:

Example 3. Let the dependence alphabet be the following cograph:

(Σ, D) = [figure: a; b; c; d; p; q; r; s] , i.e., (Σ, I) = ^{a  d  p  s c  b  r  q}

Then we have α(Σ, D) = 2 and M(Σ, D) = ({a, b}^{∗}×{c, d}^{∗})∗({p, q}^{∗}×{r, s}^{∗}). The least k such that a coding h : M(Σ, D) → ∏_{1≤i≤k} Σ_{i}^{∗} exists is k = 3.

Proof. (Sketch) First assume h : M(Σ, D) → Σ_{1}^{∗} × Σ_{2}^{∗} would be a coding. A combinatorial argument yields the existence of letters x ∈ {a, b, c, d} and y ∈ {p, q, r, s} such that h(x) = (u, 1), h(y) = (1, v) for some u ∈ Σ_{1}^{∗}, v ∈ Σ_{2}^{∗}. Then h(xy) = h(yx) = (u, v) contradicting xy ≠ yx. Finally, consider the homomorphism h : M(Σ, D) → {a, b, p, q}^{∗} × {r, s, e}^{∗} × {c, d, f}^{∗} given by the following table (where the columns give h(x), x ∈ Σ):

\begin{matrix}h & a & b & c & d & p & q & r & s \\ \{a, b, p, q\} & a & b & 1 & 1 & p & q & 1 & 1 \\ \{r, s, e\} & e & e & e & e & 1 & 1 & r & s \\ \{c, d, f\} & 1 & 1 & c & d & f & f & f & f \end{matrix}

To check injectivity, note that for t ∈ M(Σ, D), h(t) allows to decode the initial alphabet of t: if the 2nd (resp. 3rd) component starts in {r, s} (resp. in {c, d}) then the corresponding letter belongs to in(t). Otherwise we have e and f in the last two components, which restricts in(t) to the set {a, b, p, q}, which in turn is identified by the first component of the encoding.

The next results concern the special case of embedding trace monoids with cograph dependence alphabets into direct products of free monoids. Consider two codings h_{1} : M_{1} = M(Σ_{1}, D_{1}) → ∏_{i=1}^{k} Σ_{i}^{∗} and h_{2} : M_{2} = M(Σ_{2}, D_{2}) → ∏_{j=1}^{l} Γ_{j}^{∗}. Whereas the direct product M_{1} × M_{2} can be embedded into a (k + l)- fold direct product (a tight bound), we are able to obtain a better upper bound for the free product M_{1} ∗ M_{2}. The next lemma presents an inductive method for embedding free products.

Lemma 16. Let M_{1} = M(Σ_{1}, D_{1}), M_{2} = M(Σ_{2}, D_{2}) be given trace monoids. Let Σ_{1}, Σ_{2} be pairwise disjoint, let Γ be an alphabet and x ∉ Γ a new letter. Then there exists a coding h : M_{1} ∗ (M_{2} × Γ^{∗}) → (M_{1} ∗ M_{2}) × (Γ ∪ {x})^{∗}.

Proof. Consider the homomorphism h : M_{1}∗(M_{2}×Γ^{∗}) → (M_{1}∗M_{2})×(Γ ∪{x})^{∗} given by

h(a) = \{ \begin{matrix}(a , x) & for a ∈ Σ_{1} \\ (a , 1) & for a ∈ Σ_{2} \\ (1 , a) & for a ∈ Γ \end{matrix}

Note that h allows the decoding of initial alphabets as follows. The 2nd component of an encoded trace h(z), π_{Γ ∪{x}}h(z), starts by a ∈ Γ if and only if a belongs to the initial alphabet of z, in(z). Otherwise, a letter b ∈ (Σ_{1}∪Σ_{2})∩in(z) can be determined using π_{Σ_{1}∪Σ_{2}}h(z) = π_{Σ_{1}∪Σ_{2}}z.

Theorem 17. Let h_{1} : M(Σ_{1}, D_{1}) → ∏_{i=1}^{k} Σ_{i}^{∗} and h_{2} : M(Σ_{2}, D_{2}) → ∏_{j=1}^{l} Γ_{j}^{∗} be codings, k, l ≥ 1. Then there exists a coding of M(Σ_{1}, D_{1}) ∗ M(Σ_{2}, D_{2}) into a (k + l − 1)-fold direct product of free monoids. Moreover, this bound is optimal, in general.

Proof. Clearly, for trace monoids M_{i}, N_{i} such that M_{i} can be embedded into N_{i} (i = 1, 2), we can embed M_{1} ∗ M_{2} canonically into N_{1} ∗ N_{2}. Thus, assume that M_{1} = M(Σ_{1}, D_{1}) = ∏_{i=1}^{k} Σ_{i}^{∗} and M_{2} = M(Σ_{2}, D_{2}) = ∏_{j=1}^{l} Γ_{j}^{∗} holds and let w.l.o.g. l ≥ 2. By Lem. 16 we can embed (∏_{i=1}^{k} Σ_{i}^{∗}) ∗ ((∏_{j=1}^{l−1} Γ_{j}^{∗}) × Γ_{l}^{∗}) into the monoid ((∏_{i=1}^{k} Σ_{i}^{∗}) ∗ (∏_{j=1}^{l−1} Γ_{j}^{∗})) × (Γ_{l} ˙∪{x})^{∗}. By induction, the left operand of the outer direct product can be embedded into a (k + l − 2)-fold direct product, which yields the result. The lower bound of this construction is obtained by generalizing Ex. 3 to the monoid (∏_{i=1}^{k}{a, b}^{∗}) ∗ (∏_{j=1}^{l}{p, q}^{∗}).

We consider in Thm. 19 below a nearly optimal method (with regard to the number of components) of encoding m-fold free products, m ≥ 3, into direct products of free monoids. Let us start with a technical

Lemma 18. Let k, m ≥ 2 and let Σ_{ij} be pairwise disjoint alphabets, i = 1, …, k,

j = 1, …, m. Then there exists a coding h : ∗_{j=1}^{m}(∏_{i=1}^{k} Σ_{ij}^{∗}) → (⋃_{j=1}^{m} Σ_{1,j})^{∗} ×

( ∗_{j=1}^{m}(IN × ∏_{i=2}^{k} Σ_{ij}^{∗})).

Proof. Let x_{j}, j = 1, …, m, be new letters. We identify {x_{j}}^{∗} × ∏_{i=2}^{k} Σ_{ij}^{∗} with IN × ∏_{i=2}^{k} Σ_{ij}^{∗}. The following homomorphism h is easily seen to be injective:

h(a) = \{ \begin{matrix}(a , (x_{j}, 1)) & if a ∈ Σ_{1j} for some 1 ≤ j ≤ m \\ (1 , (1, a)) & if a ∉ ⋃_{j=1}^{m} Σ_{1j} \end{matrix}

The theorem below can be applied in conjunction with Lem. 16 in order to encode m-fold free products efficiently for m ≥ 3. (Lem. 16 is used for reducing the number of components.)

Theorem 19. Let h_{j} : M(Σ_{j}, D_{j}) → ∏_{i=1}^{k} Γ_{ij}^{∗} be codings, j = 1, …, m, and

a ≠ b. Then there exists a coding h : ∗_{j=1}^{m} M(Σ_{j}, D_{j}) → ∏_{i=1}^{2k}{a, b}^{∗}.

Proof. Assume Γ_{ij} to be pairwise disjoint. By repeated application of Lem. 18 we

obtain a coding h′ : ∗_{j=1}^{m}(∏_{i=1}^{k} Γ_{ij}^{∗}) → ∏_{i=1}^{k} Θ_{i}^{∗} × ( ∗_{j=1}^{m} IN^{k}), with Θ_{i} = ⋃_{j=1}^{m} Γ_{ij}

for i = 1, …, k. By standard methods we encode Θ_{i}^{∗} into {a, b}^{∗} and, by Cor. 15, ∗_{j=1}^{m} IN^{k} into ∏_{i=k+1}^{2k}{a, b}^{∗}. The result follows by composition with the coding

of ∗_{j=1}^{m} M(Σ_{j}, D_{j}) into ∗_{j=1}^{m}(∏_{i=1}^{k} Γ_{ij}^{∗}).

Remark. Note that already for m = 2 the lower bound forThm. 19 is by Thm. 17 the value 2k − 1. Hence, Thm. 19 gives an almost optimal construction.

5 Clique-preserving morphisms

Throughout this section the notion of clique is meant w.r.t. independence alphabets.

Definition 20. A clique-preserving morphism of independence alphabets 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 : M(Σ, D) → M(Σ′, D′) 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. (In fact, our construction is a faithful covariant functor from independence alphabets to trace monoids.) The most prominent homomorphism of trace monoids arising this way is the coding used in the Projection Lemma, Prop. 1. Write (Σ, D) = (⋃_{i=1}^{k} Σ_{i}, ⋃_{i=1}^{k} Σ_{i} ×

Σ_{i}) and let Σ′ = ˙⋃_{i=1}^{k} Σ_{i} be the disjoint union. The identity relations id_{Σ_{i}} ⊆ Σ_{i}×Σ_{i} induce in a natural way a relation H ⊆ Σ×Σ′ which by abuse of language can be written as H = ⋃_{i=1}^{k} id_{Σ_{i}} ⊆ Σ × Σ′. The associated homomorphism h is exactly the strong coding of Prop. 1, h : M(Σ, D) → ∏_{i=1}^{k} Σ_{i}^{∗}.

Remark. Note that a clique-preserving morphism is not a morphism of undirected graphs as defined in Sect. 3, in general. 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.

The following proposition is in major contrast to the final result of Thm. 22 below.

Proposition 21. Let H ⊆ Σ × Σ′ be a relation such that H(a) is a clique of (Σ′, I′) for all a ∈ Σ. Then the induced homomorphism h : Σ^{∗} → M(Σ′, D′) 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).

It is well-known that it is undecidable whether a homomorphism of trace monoids is injective, see [HC72, CR87]. The following theorem sharpens this result in the sense that we show the undecidability for a more natural class of homomorphism.

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

The proof of Thm. 22 is a technical and involved reduction of the halting problem of a two-counter machine. For lack of space we omit the details and refer to the full version of this paper.

6 Conclusion and open problems

In this paper we have solved the problem of the existence of strong codings for trace monoids by giving a NP-complete graph criterion. Whether or not the existence of codings is decidable remains an interesting open question. For strong codings into a k-fold direct product of free monoids we know the smallest possible value of k. For codings, we know a lower and an upper bound for k, only. It is still possible that the smallest k is uncomputable. We have extended a well-known undecidability result to a very natural class of homomorphism. The proof (not included in the present extended abstract) is very complicated. It would be interesting to find a simple direct proof.

References

[AG91] C. Àlvarez and J. Gabarró. The parallel complexity of two problems on concurrency. Information Processing Letters, 38:61–70, 1991.

[BF95] V. Bruyère and C. De Felice. Trace codings. This volume.

[BFG94] V. Bruyère, C. De Felice, and G. Guaiana. Coding with traces. In Proc. of STACS’94, LNCS 775, pp. 353–364. Springer, 1994.

[CF69] P. Cartier and D. Foata. Problèmes combinatoires de commutation et réarrangements. Lecture Notes in Mathematics 85. Springer, 1969.

[CL85] M. Clerbout and M. Latteux. Partial commutations and faithful rational transductions. Theoretical Computer Science, 35:241–254, 1985.

[CLB81] D. G. Corneil, H. Lerchs, and L. Stewart Burlingham. Complement reducible graphs. Discrete Appl. Math., 3:163–174, 1981.

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

[CPS85] D. G. Corneil, Y. Pearl, and L. K. Stewart. A linear recognition algorithm for cographs. SIAM Journal of Computing, 14:926–934, 1985.

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

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

[Die90] V. Diekert. Combinatorics on Traces. LNCS 454. Springer, 1990.

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

[Dub86] C. Duboc. On some equations in free partially commutative monoids. Theoretical Computer Science, 46:159–174, 1986.

[GJ78] M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, 1978.

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

[HY92] K. Hashiguchi and K. Yamada. String matching problems over free partially commutative monoids. Information and Computation, 101:131–149, 1992.

[Kel73] R. Keller. Parallel program schemata and maximal parallelism I. Fundamental results. Journal of the ACM, 20:514–537, 1973.

[Maz87] A. Mazurkiewicz. Trace theory. In Petri Nets, Applications and Relationship to other Models of Concurrency, LNCS 255. Springer, 1987.

[Och88] E. Ochmański. On morphisms of trace monoids. In Proc. of STACS’88, LNCS 294, pp. 346–355. Springer, 1988.

This article was processed using the LaTEX macro package with LLNCS style