On the synchronization of semi-traces^{⋆}

Klaus Reinhardt

Wilhelm-Schickhard Institut für Informatik, Universität Tübingen

Sand 13, D-72076 Tübingen, Germany e-mail: reinhard@informatik.uni-tuebingen.de

Abstract. The synchronization of two or more semi-traces describes the possible evaluation of a concurrent system, which consists of two or more concurrent subsystems in a modular way, where communication between the subsystems restricts the order of the actions. In this paper we give criteria, which tell us for given semi-traces in given semicommutation systems, whether they are synchronizable and whether the synchronization is again a semi-trace; and criteria, which tell us for given semi-commutation systems, whether all semi-traces have this property. We prove that deciding these criteria is NLOGSPACE-complete for given semi-traces. The same holds for the synchronizability of all semitraces for given semi-commutation systems. On the other hand the question, whether for given semi-commutation systems the synchronization of synchronizable semi-traces is a semi-trace is co-NP-complete. Furthermore we give a co-NP-complete condition for being able to decide synchronizability locally in TC^{0}.

1 Introduction

Traces were introduced by Mazurkiewicz in [Maz87] to describe the behavior of concurrent systems. Traces are equivalence classes of words under partial commutations, which allow only to describe symmetric dependencies between actions. In order to enhance the possibilities of descriptions, M.Clerbout introduced the notion of semi-commutation in her thesis [Cle84] as a generalization of partial commutation, see also M. Clerbout and M. Latteux [CL87]. In a broader context it was observed in [HK89], [Och90] and [Och92], that semi-commutations are very useful for modeling behaviors of Petri-nets. For instance we are able to describe a producer/consumer system. For more information see [CGL^{+}92], [OW93], [DR95]. If we want to describe a distributed system and we have described the single components by semi-dependence alphabets, where the alphabets can partially overlap at those actions, where the components interact, we need the operation of synchronization to get the consistent evaluations of the entire system. The partial traces in [Die94] are closed under synchronization; but this notion gives up the efficient description by just one representing word. Semi-traces are

⋆ this research has been supported by the EBRA working group No. 3166 ASMICS.

not closed under synchronization and hence we have to distinguish between stable and unstable synchronizations of semi-traces. In this paper we classify the complexity of problems and operations on semicommutation systems, which are semantically relevant for such concurrent systems. Since it is important for practical applications to be able to design algorithms with low complexity and particularly efficient parallel algorithms, it is a good news, that some of the problems are in such low complexity classes as NLOGSPACE and TC^{0}.

2 Preliminaries

Let TC^{0} be the class of problems being recognized by a uniform circuit family of constant depth and polynomial size with threshold-gates or computable in constant time for the enlarged PRAM model in [Par90], respectively. NC^{k} (AC^{k}) is the class of problems being recognized by a circuit family of O(log^{k}n) depth and polynomial size with bounded (unbounded) fan-in gates [Ruz81]. The problems in NC = ⋃_{k} NC^{k} are regarded as the efficiently parallelizable problems. NLOGSPACE (NP) is the class of problems being recognized by a logarithmic space-bounded (polynomial time-bounded) nondeterministic Turing machine. For completeness we use LOGSPACE-reducibility. co-NP is the set of the complements of problems in NP. The following inclusions are know [Joh90]: AC^{0} ⊂ TC^{0} ⊆ NC^{1} ⊆ LOGSPACE ⊆ NLOGSPACE ⊆ AC^{1} ⊆ TC^{1} ⊆ NC^{2} ⊆ NC ⊆ P ⊆ NP ⊆ Σ_{2}^{P} ⊆ PSPACE. Although nearly no separations are known (e.g., TC^{0} ≠ NP? is not known), proper inclusions are conjectured, which motivates the difference for local checking in TC^{0} or NLOGSPACE regarded in this paper. To describe semi-commutation, we use semi-dependence alphabets, of the form (A, SD) where SD ⊆ A×A is reflexive but possibly asymmetric. This defines the associated semi-commutation system SC = { ab ⟹ ba | (a, b) ∉ SD }. A semi-

trace over (A, SD) is by definition the set of words [u⟩ = { w ∈ A^{∗} | u ⟹_{SC}^{∗} w }, which can be derived from a word u ∈ A^{∗} by applying semi-commutation rules from SC. This means that we can use one possible evaluation of the concurrent system expressed by the word u to describe all possible evaluations. For several semi-dependence alphabets (A_{i}, SD_{i}) the corresponding semi-traces [u⟩_{i} get the same index.

2.1 Graph representation

We represent a semi-trace [a_{1}...a_{n}⟩ over (A, SD) by a graph with nodes labeled by a_{1}...a_{n} and two kinds of edges: The hard arcs a_{i} → a_{j} with i < j and (a_{i}, a_{j}) ∈ SD and the soft arcs^{2} a_{i} [figure]a_{j} with i < j and (a_{i}, a_{j}) ∈ SD^{−1} \ SD, which emphasize the semi-dependence structure (see also [DOR94]). The graph examples are restricted to the Hasse diagram, that means we do not show arcs, which are in the transitive closure of shown arcs. Example: Consider the following semi-dependence alphabets

2 An asymmetric commutation can change the order described by a soft arc but then

the outcome is not representing the complete semi-trace. (SD^{−1} = {(a, b) | (b, a) ∈ SD})

[figure: (A_{1}, SD_{1}) =; a; b; c; and; (A_{2}, SD_{2}) =; a; b; d]

and the following semi-traces together with their graph representation:

[figure: [cacba⟩_{1} =; c; a; c; b; a; .; .; .; .; .; .; .; .; .; .; [dbada⟩_{2} =; d; b; a; d; a; .; .; .; .; .; .; .; .; .; .]

[figure: [bdada⟩_{2} =; d; b; a; d; a; .; .; .; .; .; [daadb⟩_{2} =; d; a; a; d; b; .; .; .; .; .; .; .; .; .; .]

2.2 Synchronization

In order to construct complex systems in a modular way, we need a notion of synchronization for semi-commutation as it was introduced by Mazurkiewicz in [Maz87] and [DV89] for the symmetric case of partial commutation. The synchronization (A_{1}, SD_{1}) ∥ ... ∥ (A_{m}, SD_{m}) of semi-dependence alphabets is simply their union (A, SD) = ( ⋃_{i≤m} A_{i}, ⋃_{i≤m} SD_{i}). The synchronization^{3} of

semi-traces is [u_{1}⟩_{1} ∥ [u_{2}⟩_{2} ∥ … [u_{m}⟩_{m} = {w ∈ A^{∗} | Π_{A_{i}}^{A}(w) ∈ [u_{i}⟩_{i} ∀0 < i ≤ m}, where Π_{A_{i}}^{A}(w) is the projection of the word w to the letters in A_{i} with Π_{A_{i}}^{A}(a) = a for all a ∈ A_{i} and Π_{A_{i}}^{A}(a) = λ otherwise. We call semi-traces synchronizable, if their synchronization is not the empty set and stably synchronizable if their synchronization is a semi-trace. On the graph representation level the synchronization is the union of the graphs of the semi-traces, where we have to identify nodes with the same labeling according to their order preserving all arcs describing dependencies. Of course ∀i, j ≤ m ∀a ∈ A_{i} ∩ A_{j} | u_{i} |_{a}=| u_{j} |_{a} is a necessary condition for synchronizability; together with the non-existence of a cycle of hard arcs, the condition becomes also sufficient. If there is a soft arc (in either direction) in a cycle with hard arcs having the same direction, the soft arc can be deleted. Continuing the above example we get the new semi-dependence alphabet (A, SD) = (A_{1} ∪ A_{2}, SD_{1} ∪ SD_{2}) = [figure: a; b; c; d] and for [cacba⟩_{1} ∥ [dbada⟩_{2} we get the stable synchronization

[figure: [cdacbda⟩ =; c; d; a; c; b; d; a; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; over (A, SD).]

3 It is easy to see that the synchronization on an identical alphabet is simply the

intersection: [u⟩_{i} ∥ [v⟩_{i} = [u⟩_{i} ∩ [v⟩_{i}

On the other hand we get [cacba⟩_{1} ∥ [bdada⟩_{2} = [figure: c; d; a; c; b; d; a; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .] which has a cycle of hard arcs and therefore [cacba⟩_{1} ∥ [bdada⟩_{2} = ∅.

Another example is [cacba⟩_{1} ∥ [daadb⟩_{2}. Here we get the graph [figure: c; d; a; c; b; d; a; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .] having a directed cycle containing two soft arcs,

which means, that either the soft arc a [figure]d or the soft arc d [figure]b must be turned around to get a word describing a possible evaluation. Therefore [cacba⟩_{1} ∥ [daadb⟩_{2} = [cdacbad⟩_{1} ∪ [cdacdba⟩_{2}

is not a stable synchronization.

2.3 Deciding the synchronizability of semi-traces

The above observations lead to the following theorem:

Theorem 1. The following problems are NLOGSPACE-complete:

i) Given m semi-dependence alphabets (A_{i}, SD_{i}) with 0 < i ≤ m and the semitraces [u_{1}⟩_{1}, [u_{2}⟩_{2}, … [u_{m}⟩_{m}. Are the traces synchronizable, that means [u_{1}⟩_{1} ∥ [u_{2}⟩_{2} ∥ … [u_{m}⟩_{m} ≠ ∅?

ii) Given a semi-dependence alphabet (A, SD) and the semi-traces [u⟩, [v⟩ with ∀a ∈ A |u_{i}|_{a} = |u_{j}|_{a}. Are the two traces synchronizable, that means [u⟩ ∩ [v⟩ ≠ ∅?

iii) Given m semi-dependence alphabets (A_{i}, SD_{i}) with 0 < i ≤ m and the semitraces [u_{1}⟩_{1}, [u_{2}⟩_{2}, … [u_{m}⟩_{m}. Are the traces stably synchronizable, that means is there a word w ∈ A^{∗} with [u_{1}⟩_{1} ∥ [u_{2}⟩_{2} ∥ … [u_{m}⟩_{m} = [w⟩?

iv) Given a semi-dependence alphabet (A, SD) and the semi-traces [u⟩, [v⟩ with [u⟩ ∩ [v⟩ ≠ ∅. Are the two traces stably synchronizable, that means is there a word w ∈ A^{∗} with [u⟩ ∩ [v⟩ = [w⟩?

Proof. i): A nondeterministic logarithmic space-bounded Turing machine first deterministically checks ∀i, j ≤ m ∀a ∈ A_{i} ∩ A_{j} | u_{i} |_{a}=| u_{j} |_{a}, then it guesses a cycle and tests each connection by testing precedence and dependence of the pair in each semi-trace. According to [Imm88] and [Sze88] the non-existence of the cycle can also be tested in NLOGSPACE. For hardness see ii). ii): The problem is in NLOGSPACE because of i). The monotone graph reachability problem for directed graphs is well known to be NLOGSPACEcomplete; for a given graph

G = ({s = a_{1}, a_{2}, … a_{n} = e}, R)

with the property (a_{i}, a_{j}) ∈ R ⇒ i < j the question is whether there exists a directed path from s to e. This can be reduced to the complementary of the synchronizability problem by adding the edge (e, s) to the graph, which is now the dependence graph ({s, a_{2}, a_{3} … a_{n−1}, e}, R) (SD := R ∪ {(e, s)}) and consider the synchronizability of [esa_{2}a_{3} … a_{n−1}⟩ and [a_{2}a_{3} … a_{n−1}es⟩. There exists a directed path from s to e, iff the semi-traces are not synchronizable, because of a cycle of hard arcs. iii): A nondeterministic logarithmic space-bounded Turing machine first checks the synchronizability like in i), then is uses the [Imm88] and [Sze88] technique to do the opposite of the following: It guesses and tests a cycle with two soft arcs. Then again using [Imm88] and [Sze88] it tests, whether both soft arcs can be turned around without producing a cycle. For hardness see iv). iv): The problem is in NLOGSPACE because of iii). The monotone graph reachability problem for directed graphs can be reduced to the problem by adding the additional letters b and c and the edges (b, s), (b, c), (e, c) and (e, s) to the graph, which is now the dependence graph ({b, c, s, a_{2}, a_{3}, … a_{n−1}, e}, SD) and consider, whether the synchronization of the semi-traces [cbs(a_{2}a_{3} … a_{n−1})^{n}e⟩ and [s(a_{2}a_{3} … a_{n−1})^{n}ecb⟩ is a semi-trace.

[figure: s; e; c; b; (a_{2}...a_{n−1})^{n}; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .]

The synchronization is the semi-trace [bs(a_{2}a_{3} … a_{n−1})^{n}ec⟩, iff there is a path of hard arcs from s to e. ⊓ ⊔

For the existence of a non-confluent situation we get the same complexity:

Theorem 2. [Rei94] The following problem is NLOGSPACE-complete: Given a semi-dependence alphabet (A, SD) and the semi-trace [u⟩. Are there words v, w ∈ [u⟩ with [v⟩ ∥ [w⟩ = ∅?

3 The synchronizability in semi-commutation systems

It is easy to see that only a cycle of hard arcs from at least two semi-traces can be responsible for non-synchronizability of semi-traces, where ∀i, j ≤ m ∀a ∈ A_{i} ∩ A_{j} | u_{i} |_{a}=| u_{j} |_{a}. (The cycle may even consist of a symmetric dependence.) Of course this cycle must be also in the dependence graph and must be composed of edges from at least two dependence alphabets.

Theorem 3. Given m semi-dependence alphabets (A_{i}, SD_{i}) with 0 < i ≤ m. The following assertions are equivalent:

i) ∀u_{1} ∈ A_{1}^{∗}, … u_{m} ∈ A_{m}^{∗}, (∀i, j ≤ m ∀a ∈ A_{i} ∩ A_{j} | u_{i} |_{a}=| u_{j} |_{a}) ⇒ [u_{1}⟩_{1} ∥ [u_{2}⟩_{2} ∥ … [u_{m}⟩_{m} ≠ ∅

ii) ¬∃1 < k, i ≠ j, C = {(x_{1}, x_{2}), … (x_{k−1}, x_{k}), (x_{k}, x_{1})} with C ⊆ SD ∧ C ∩ SD_{i} ≠ ∅ ∧ C ∩ SD_{j} ≠ ∅ Again this property is NLOGSPACE-complete. The following theorem says that semi-dependence alphabets have unstable synchronization (that means it can happen that the synchronization is neither empty nor a semi-trace), iff there exists a cycle in the union of the semi-dependence alphabets where

– all nodes are different,

– the two directed arcs (x_{1}, x_{k}) and (x_{j+1}, x_{j}) have reverse direction,

– there is no chord which separates them,

– there is no chord in backward direction and

– in each semi-dependence alphabet the cycle is either interrupted or has a directed arc in the opposite direction at some place, but then there is a another semi-dependence alphabet, having an arc at this place and is either interrupted or has a directed arc in the opposite direction at another place.

[figure: x_{k}; x_{j+1}; x_{1}; x_{j}; ⋯; ⋯]

Theorem 4. Given m semi-dependence alphabets (A_{i}, SD_{i}) with 0 < i ≤ m. The following assertions are equivalent:

i) ∃u_{1} ∈ A_{1}^{∗}, … u_{m} ∈ A_{m}^{∗} ∀w ∈ A^{∗} [w⟩ ≠ [u_{1}⟩_{1} ∥ [u_{2}⟩_{2} ∥ … [u_{m}⟩_{m} ≠ ∅

ii) ∃j ∈ {1, ...k − 1}, (x_{1}, x_{2}), …, (x_{k−1}, x_{k}) ∈ SD ∪ SD^{−1} with

∀n ≠ p x_{n} ≠ x_{p} ∧

(x_{1}, x_{k}), (x_{j+1}, x_{j}) ∈ SD \ SD^{−1} ∧

∀(n, p) ∈ {1, ...j} × {j+1, ...k} \ {(1, k), (j, j+1)} (x_{n}, x_{p}) ∉ SD ∪ SD^{−1}∧ ∀n ∈ {1, ...k} ∀p ∈ {n + 2, ...k} (x_{p}, x_{n}) ∉ SD ∧ ∀i ≤ m ∃n ≤ k, ((x_{n+1}, x_{n}) ∉ SD_{i} ∧

((x_{n}, x_{n+1}) ∉ SD_{i} ∨
∃l ∈ {1, ...m} \ {i}(x_{n}, x_{n+1}) ∈ SD_{l} ∪ SD_{l}^{−1} ∧

∃p ∈ {1, ...k} \ {n} (x_{p+1}, x_{p}) ∉ SD_{l}))

The simplest example for this is (A_{1}, SD_{1}) = ({a, b}, {(a, b)}) and (A_{2}, SD_{2}) = ({a, b}, {(b, a)}) then [ba⟩_{1} ∥ [ab⟩_{2} = {ab, ba} ≠ [u⟩ for any u. If we only regard semi-traces over one semi-dependence alphabet, then it follows, that it has unstable synchronization, iff there exists a cycle of different nodes with two directed arcs in both directions and only directed chords from the part of the cycle where two of these arcs start (in different direction) to the part of the cycle where the other two arcs end.

Corollary 5. Given a semi-dependence alphabet (A, SD). The following assertions are equivalent: i) ∃u, v ∈ A^{∗} ∀w ∈ A^{∗} [w⟩ ≠ [u⟩ ∥ [v⟩ ≠ ∅

ii) ∃j ≠ q ≠ r ≠ j ∈ {1, ...k − 1}, (x_{1}, x_{2}), … (x_{k−1}, x_{k}) ∈ SD ∪ SD^{−1} with

∀n ≠ p x_{n} ≠ x_{p} ∧

(x_{1}, x_{k}), (x_{j+1}, x_{j}) ∈ SD \ SD^{−1} ∧ (x_{q+1}, x_{q}), (x_{r+1}, x_{r}) ∈ SD^{−1} \ SD ∧ ∀(n, p) ∈ {1, ...j} × {j+1, ...k} \ {(1, k), (j, j+1)} (x_{n}, x_{p}) ∉ SD ∪ SD^{−1}∧ ∀n ∈ {1, ...k} ∀p ∈ {n + 2, ...k} (x_{p}, x_{n}) ∉ SD

So there are only two such basic examples for semi-dependence alphabets (all other cases can be reduced to one of them by contraction of nodes in the graph):

[figure: a; b; c; d; and; a; b; c; d]

In the first one any chord would destroy the situation [cabd⟩ ∥ [bdca⟩ = [abdc⟩ ∪ [dcab⟩ ≠ [u⟩ for any u. In the second one the situation [dcab⟩ ∥ [bdca⟩ = [abdc⟩ ∪ [cdba⟩ ≠ [u⟩ for any u works independently from the existence of the arc from a to d. Now we come to the proof of Theorem 4:

Proof. ii ⇒ i: Take the shortest cycle of this kind and choose u_{i} = x_{n+1} … x_{k}x_{1}x_{2} … x_{n} such that (x_{n+1}, x_{n}) ∉ SD_{i} and

(x_{n}, x_{n+1}) ∉ SD_{i} ∨ ∃l ≤ m, ≠ i, (x_{n}, x_{n+1}) ∈ (SD_{l} ∪ SD_{l}^{−1}) ∩ [u_{l}⟩_{l}.

So the synchronization has a cycle with the two soft arcs (x_{k}, x_{1}) and (x_{j}, x_{j+1}) and no cycle of hard arcs. i ⇒ ii: Choose v, v′, u_{i} (length-)minimal with ∀iΠ_{A_{i}}^{A}(v) = u_{i}, ∀iΠ_{A_{i}}^{A}(v′) = u_{i} and ¬∃w with ∀i Π_{A_{i}}^{A}(w) = u_{i}, v, v′ ∈ [w⟩. Construct G as the union of all (graphs of) [u_{i}⟩_{i}. Construct G′ from G by replacing every b [figure] a by a ⟶ b if a = x_{1} ⟶ x_{2} ⟶ … x_{j} = b in G. Because of v, v′ the graph G′ contains no cycle of hard arcs. So G′ must have a cycle with at least two soft arcs

[figure: x_{k}; x_{1}; x_{j+1}; x_{j}; ...; ...; .; .; .; .; .; .; .; .; .; .]

because otherwise G′ would be the graph for [w⟩ which must contain every hard arc of G anyway because of ∀i Π_{A_{i}}^{A}(w) = u_{i} and cycles with one soft arc are deleted in the construction of G′. The shortest cycle of this kind has no chord. Now we can find a cycle with at least two soft arcs consisting only of original arcs from G and having only hard new chords in the direction of the cycle, which do not separate the two soft arcs with the following construction: We replace a new arc in cycle by the path of original hard arcs, which caused its existence. This may lead to a forbidden chord, but then we can find a shorting of the cycle with at least two soft arcs and no forbidden chord, where either the number of soft arcs or the number of new hard arcs is reduced, so the construction must terminate. Because of the minimality of the u_{i} there are no other vertices in G′ except those in the cycle and no element of A appears twice. Furthermore the cycle can not contain soft chords and therefore there can be no arcs in the opposite direction. Now every arc in the cycle must come from one of the [u_{i}⟩_{i}’s. But for every [u_{i}⟩_{i} the cycle must be open at a certain arc from x_{n} to x_{n+1} and it could be that (x_{n}, x_{n+1}) ∈ SD_{i}, then an arc at this place must be delivered from some other [u_{l}⟩_{l}. But this [u_{l}⟩_{l} must be open at another arc from x_{p} to x_{p+1}. This is, what the last part of the formula in ii says. ⊓ ⊔

Theorem 6. The assertions of Theorem 4 as well as the assertions of Corollary 5 are co-NP-complete to decide for semi-commutation systems.

It is easy to see that the problem is in co-NP. The proof of hardness in [Rei94] uses a similar graph construction as in [DOR94] with the only difference, that we have to replace the two directed arcs by two pairs of directed arc to two additional nodes. The complexity class Σ_{2}^{P} contains those languages which are accepted by an NPmachine with access to an NP-oracle. (For more background see e. g. [BDG88].) In analogy to another result in [DOR94] the following holds:

Theorem 7. The following problem is Σ_{2}^{P} -complete: Given two dependence alphabets (A, D) and (A, D′) such that D′ ⊆ D. Does there exist a semi-commutation system SC such that

D = {(a, b) ∈ A × A | ab ⟹ ba ∉ SC ∩ SC^{−1}} and
D′ = {(a, b) ∈ A × A | ab ⟹ ba ∉ SC ∪ SC^{−1}} and
∀u, v ∈ A^{∗} ∃w ∈ A^{∗} with [u⟩ ∥ [v⟩ = [w⟩ or = ∅ ?

This means can unstable synchronization be avoided by choosing the direction of asymmetric dependencies?

The same result holds for 2m dependence alphabets. Because the direction of the most arcs in the cycle is of no influence, we can not use the same graph construction as in [DOR94] for the proof; instead a different construction in [Rei94], which makes use of the direction of chords, works in a similar way to reduce the truth of quantified boolean formulae (see [Sto77], [Wra77]) to the problem.

Remark. Given 2m dependence alphabets (A_{i}, D_{i}) and (A_{i}, D′_{i}) such that D′_{i} ⊆ D_{i} for all 0 < i ≤ m. The direction of asymmetric arcs can be chosen for m semi-dependence alphabets in such a way that semi-traces having the same letters in the intersection are always synchronizable, that means the direction of asymmetric arcs can be changed in a way such that there is no directed cycle consisting of arcs from at least two of the dependencies iff there is no such cycle having at most one asymmetric arc. The property is hereby in NLOGSPACE.

4 The inclusion of semi-traces

For a valid representing evaluation of a concurrent system it is a basic question, whether another evaluation is also valid. If the system is described by partial commutation, it is the following trace-equivalence problem: Given a symmetric semi-commutation system C and two words w, w′; is it true that w ⟹_{C}^{∗} w′?

The trace-equivalence problem is proved to be in TC^{0} in [AG91] by describing in first order logic enlarged by majority quantifiers, whether for each dependent pair (a, b) for every position in w there is a corresponding position in w′ with the same number of preceding a’s and b’s. By a result of [BIS90] this follows to be in TC^{0} (but not in AC^{0}). The same is applied to asymmetric semi-commutation systems in [Rei94]:

Theorem 8. The following semi-trace-inclusion problem is in TC^{0}: Given an asymmetric semi-commutation system SC by the semi-dependence alphabet (A, SD) and two words w, w′; is it true that w ⟹_{SC}^{∗} w′ respectively [w′⟩ ⊆ [w⟩?

5 Local checking of synchronizability of semi-traces

In [DV89] an easy testable (TC^{0}), necessary condition for the synchronizability of traces was described. The local checking property is a criterion for the sufficiency of this condition. It is co-NP-complete [DOR94]. The necessary condition for the synchronizability of two semi-traces [u_{1}⟩_{1}, [u_{2}⟩_{2} is the following:

Π_{A_{1}∩A_{2}}^{A_{1}}(u_{1}) ⟹_{SC′}^{∗} Π_{A_{1}∩A_{2}}^{A_{2}}(u_{2}) for SC′ defined by SD′ = SD_{1} ∩ SD_{2}^{−1}

According to Theorem 8 this condition can be tested in TC^{0}.

Lemma 9. The above condition is sufficient, iff the composition [RW91] of the semi-commutation systems SC_{1} and SC_{2}^{−1} is a semi-commutation system^{4}.

Proof. If the composition of the semi-commutation systems SC_{1} and SC_{2}^{−1} is a semi-commutation system, the composition SC′ is determined by SD′ = SD_{1} ∩

SD_{2}^{−1} over A_{1} ˙∪{a_{1}, … a_{n}} = A_{2} ˙∪{b_{1}, … b_{m}}. If Π_{A_{1}∩A_{2}}^{A_{1}}(u_{1}) ⟹_{SC′}^{∗} Π_{A_{1}∩A_{2}}^{A_{2}}(u_{2})

then u_{1}a_{1}^{|u_{2}|_{a_{1}}} … a_{n}^{|u_{2}|_{an}} ⟹_{SC′}^{∗} u_{2}b_{1}^{|u_{1}|_{b_{1}}} … b_{m}^{|u_{1}|_{bm}}, since

(A_{1} × {a_{1}, … a_{n}}) ∩ SD_{1} = ∅ and (A_{2} × {b_{1}, … b_{m}}) ∩ SD_{2} = ∅. Thus we have

u_{1}a_{1}^{|u_{2}|_{a_{1}}} , … a_{n}^{|u_{2}|_{an}} ⟹_{SC_{1}}^{∗} s ⟹_{SC_{2}^{−1}}^{∗} u_{2}b_{1}^{|u_{1}|_{b_{1}}} , … b_{m}^{|u_{1}|_{bm}}

and s is in the synchronization of [u_{1}⟩_{1} and [u_{2}⟩_{2}. If the condition is sufficient, then for every w_{1} ⟹_{SC′}^{∗} w_{2} there is a synchronization

s ∈ [Π_{A_{1}}(w_{1})⟩_{1} ∥ [Π_{A_{2}}(w_{2})⟩_{2} and the derivation w_{1} ⟹_{SC′}^{∗} w_{2} is composed of

w_{1} ⟹_{SC_{1}}^{∗} s ⟹_{SC_{2}^{−1}}^{∗} w_{2}. ⊓ ⊔

4 this means that f_{SC_{1}} ∘ f_{SC_{2}^{−1}} = f_{SC′} for a semi-commutation system SC′.

Theorem 10. The local checking property for synchronizability of two semitraces is co-NP-complete.

Proof. A criterion describing, whether the composition of two semi-commutation systems is a semi-commutation system, is given in [RW91]. It is easy to see that this criterion is in co-NP and since the criterion for confluence, which was shown to be co-NP-complete in [DOR94], is a special case for this, the problem is co-NP-complete, too. ⊓ ⊔

Remark. If we use a pairwise application of the condition for the local checking for m semi-commutation systems, we get the same result with an immediate generalization of [RW91]. We conjecture that this is also the case for conditions regarding projections to sub-alphabets of constant size.

Remark. It is easy to see that for regular string languages R_{1}, R_{2} the synchronization is also regular but even in the special case for symmetric dependencies it is undecidable whether f_{SC}(R_{1}) ∥ f_{SC}(R_{2}) ≠ ∅ according to [AH89]; for more information see [Rei94].

Acknowledgment: I thank Volker Diekert, Klaus-Jörn Lange and an anonymous referee for helpful remarks.

References

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

[AH89] 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.

[BDG88] J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I. Number 11 in EATCS Monographs on Theoretical Computer Science. Springer, Berlin-Heidelberg-New York, 1988.

[BIS90] D.M. Barrington, N. Immerman, and H. Straubing. On uniformity within NC^{1}. J. of Comp. and Syst. Sciences, 41:274–306, 1990.

[CGL^{+}92] M. Clerbout, D. Gonzalez, M. Latteux, E. Ochmanski, Y. Roos, and P.A. Wacrenier. Recognizable morphisms on semi commutations. Tech. Rep. LIFL I.T.-238, Université des Sciences et Technologies de Lille (France), 1992.

[CL87] M. Clerbout and M. Latteux. Semi-Commutations. Information and Computation, 73:59–74, 1987.

[Cle84] M. Clerbout. Commutations Partielles et Familles de Langages. Thèse, Université des Sciences et Technologies de Lille (France), 1984.

[Die94] V. Diekert. A partial trace semantics for Petri nets. Theoretical Computer Science, 134:87–105, 1994. Special issue of ICWLC 92, Kyoto (Japan).

[DOR94] V. Diekert, E. Ochmański, and K. Reinhardt. On confluent semi-com-mutation systems – decidability and complexity results. Information and Computation, 110:164–182, 1994. A preliminary version was presented at ICALP’91, Lecture Notes in Computer Science 510 (1991).

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

[DV89] V. Diekert and W. Vogler. On the synchronization of traces. Mathematical Systems Theory, 22:161–175, 1989. A preliminary extended abstract appeared at MFCS 88, Lecture Notes in Computer Science 324 (1988) 271-279.

[HK89] D. V. Hung and E. Knuth. Semi-commutations and Petri nets. Theoretical Computer Science, 64:67–81, 1989.

[Imm88] N. Immerman. Nondeterministic space is closed under complement. SIAM Journal on Computing, 17(5):935–938, 1988.

[Joh90] D. S. Johnson. A catalog of complexity classes. In J. van Leeuwen, editor, Algorithms and Complexity, volume A of Handbook of Theoretical Computer Science, chapter 2, pages 67–161. Elsevier, 1990.

[Maz87] A. Mazurkiewicz. Trace theory. In W. Brauer et al., editors, Petri Nets, Applications and Relationship to other Models of Concurrency, number 255 in Lecture Notes in Computer Science, pages 279–324, Berlin-Heidelberg-New York, 1987. Springer.

[Och90] E. Ochmański. Semi-Commutation and Petri Nets. In V. Diekert, editor, Proceedings of the ASMICS workshop Free Partially Commutative Monoids, Kochel am See 1989, Report TUM-I9002, Technical University of Munich, pages 151–166, 1990.

[Och92] E. Ochmański. Modelling concurrency with semi-commutations. In I. M. Havel and V. Koubek, editors, Proceedings of the 17th Symposium on Mathematical Foundations of Computer Science (MFCS’92), Prague, (Czechoslovakia), 1992, number 629 in Lecture Notes in Computer Science, pages 412– 420, Berlin-Heidelberg-New York, 1992. Springer.

[OW93] E. Ochmański and P. A. Wacrenier. On regular compatibility of semicommutations. In Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, editors, Proceedings of the 20th International Colloquium on Automata, Languages and Programming (ICALP’93), Lund (Sweden) 1993, number 700 in Lecture Notes in Computer Science, pages 445–456, Berlin-Heidelberg-New York, 1993. Springer.

[Par90] Ian Parberry. A primer on the complexity theory of neural networks. In R.B. Banerji, editor, Formal Techniques in Artificial Intelligence, Amsterdam, 1990. North-Holland.

[Rei94] K. Reinhardt. Prioritätszählerautomaten und die Synchronisation von Halbspursprachen. Dissertation, Institut für Informatik, Universität Stuttgart, 1994.

[Ruz81] W. L. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22:365–383, 1981.

[RW91] Y. Roos and P. A. Wacrenier. Composition of two semi commutations. In A. Tarlecki, editor, Proceedings of the 16th Symposium on Mathematical Foundations of Computer Science (MFCS’91), Kazimierz Dolny (Poland) 1991, number 520 in Lecture Notes in Computer Science, pages 406–414, Berlin-Heidelberg-New York, 1991. Springer.

[Sto77] L. J. Stockmeyer. The polynomial time hierarchy. Theoret. Comput. Sci., 3:1–22, 1977.

[Sze88] R. Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279–284, 1988.

[Wra77] C. Wrathall. Complete sets and the polynomial hierarchie. Theoret. Comput. Sci., 3:23–33, 1977.

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