A note on Métivier’s construction of asynchronous automata for triangulated graphs ^{∗}

Volker Diekert Anca Muscholl

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

1 Introduction

Free partially commutative monoids have been introduced in computer science by Mazurkiewicz as trace monoids [Maz77]. They have been widely adopted as a suitable model for concurrency. A particularly interesting language family is given by considering recognizable subsets. In the context of trace monoids we have a natural finite automaton model with a distributed control structure, the asynchronous (cellular) automaton. By Zielonka’s important theorem deterministic asynchronous (cellular) automata precisely characterize recognizability of trace languages. It is well-known that Zielonka’s construction is rather involved, making use of a bounded timestamping technique which gives information about trace prefixes. With this information, distributed control is possible. The question, whether a substantially simpler construction for deterministic asynchronous automata exists, is still open. Recently, two determinization constructions for asynchronous automata have been given [KMS94, Mus94], but both rely on the complicated time-stamping technique. In the special case of acyclic dependence graphs Y. Métivier exhibited a surprisingly elegant solution [Mét87], providing in a natural way deterministic asynchronous automata for recognizable languages. The drawback is the fact that acyclicity is a strong restriction on concurrency alphabets. In fact, even the special case of complete dependence, i.e. the free monoid, is not included. We show here that for a larger class of graphs –the triangulated graphs– the main idea of Métivier’s construction still applies. We are thus able to generalize this simple construction to triangulated graphs. From a practical point of view, this means that by adding sufficient dependency, i.e. triangulating in a dependence alphabet, we can obtain simple deterministic asynchronous automata for every recognizable trace languages, by loosing some concurrency, only.

∗Research supported by the ESPRIT Basic Research Action No. 6317 (ASMICS 2). This paper appeared in The Book of Traces, World Scientific, 1995.

We conclude this section by introducing some notations. By (Σ, D) we denote a finite dependence alphabet, with Σ being a finite alphabet and D ⊆ Σ × Σ a reflexive and symmetric relation called dependence relation. The complementary relation I = (Σ×Σ)\D is called independence relation. The monoid of finite traces, IM(Σ, D), is defined as a quotient monoid with respect to the congruence relation induced by I, i.e., IM(Σ, D) = Σ^{∗}/{ ab = ba | (a, b) ∈ I }. Recognizability for trace languages can be defined by recognizing morphisms: a trace language L ⊆ IM(Σ, D) is recognizable if there exists a finite monoid S and a morphism η : IM(Σ, D) → S recognizing L, i.e. satisfying L = η^{−1}η(L). Alternatively, by Zielonka’s characterization theorem, recognizability is equivalent to recognition by finite asynchronous automata. (Note that we work here with deterministic automata, only.) An asynchronous automaton A is a tuple (∏_{i=1}^{m} Q_{i}, (δ_{a})_{a∈Σ}, q_{0}, F) satisfying the following conditions:

• The global state set Q = ∏_{i=1}^{m} Q_{i} is a direct product of local states sets Q_{i}, 1 ≤ i ≤ m.

• Each letter a ∈ Σ has an associated domain dom(a) ⊆ {1, …, m} such that for all (a, b) ∈ I we have dom(a) ∩ dom(b) = ∅.

• To each letter a ∈ Σ there is a (partially defined) local transition function δ_{a} : ∏_{i∈dom(a)} Q_{i} → ∏_{i∈dom(a)} Q_{i}. A global transition step q′ = δ(q, a), q = (q_{i})_{1≤i≤m}, q′ = (q′_{i})_{1≤i≤m} ∈ Q, is defined if and only if δ_{a}((q_{i})_{i∈dom(a)}) is defined. In this case only the components of the domain of a change, i.e. we have

1. q′_{j} = q_{j} if j ∉ dom(a)

2. (q′_{i})_{i∈dom(a)} = δ_{a}((q_{i})_{i∈dom(a)}).

The language accepted by A is L(A) = {t ∈ IM(Σ, D) | δ(q_{0}, t) ∈ F }. Note that asynchronous automata enable concurrent transitions, since write-and-read–domains of independent letters do not overlap.

2 Triangulated graphs

An undirected graph G = (V, E) with vertex set V and edge set E is triangulated if all its chordless cycles are of length three. Trivial examples are complete graphs

(i.e., graphs where E = ( \begin{matrix}V \\ 2 \end{matrix} )), or acyclic graphs (i.e., trees or forests).

For u ∈ V let E(u) denote the set of vertices adjacent to u, i.e. E(u) = {v ∈ V | uv ∈ E}. A perfect vertex elimination scheme is a linear ordering ≤ of the vertices such that for all u ∈ V the set {v ∈ E(u) | u ≤ v} forms a clique (i.e. a complete subgraph). We may represent a perfect vertex elimination scheme by a list [v_{1}, …, v_{n}] such that v_{i} ≤ v_{j} if and only if i ≤ j. It is easy to see that a graph having a perfect vertex elimination scheme is triangulated. The converse is also true. This characterization of triangulated graphs is due to Dirac [Dir61]. The result and the proof hereof can be found e.g. in the textbook of Golumbic [Gol80, Thm. 4.1]. Note that if G = (V, E) is acyclic, then any ordering which represents a topological sorting yields a perfect vertex elimination scheme. For a complete graph, every order is a perfect vertex elimination scheme.

3 Extending Métivier’s construction

In [Mét87] Y. Métivier gave an elegant and amazingly simple construction for asynchronous automata in the case of acyclic dependence alphabets (Σ, D) (see also the survey of D. Perrin [Per89]). The basic idea is to choose a tree (forest) structure and to move the distributed information to the top of the tree(s) as soon as available. We will explain this simple construction below. In fact, our result shows that it applies to triangulated graphs. All we need is a perfect vertex elimination scheme. Let (Σ, D) be any triangulated dependence alphabet and let ≤ be a linear ordering of Σ such that for all a, b, c ∈ Σ, a ≤ b ≤ c, (a, c) ∈ D and (b, c) ∈ D, we have (a, b) ∈ D, too. Thus, if Σ = {a_{1}, …, a_{n}} (n = |Σ|) is written in increasing order a_{1} < ⋯ < a_{n}, then [a_{n}, …, a_{1}] is a perfect vertex elimination scheme of (Σ, D). Let η : IM(Σ, D) → S be a homomorphism to a finite monoid S. First we define for Γ ⊆ Σ and s_{c} ∈ S (c ∈ Γ) the ordered product ∏_{c∈Γ} s_{c} by multiplying the elements according to the ordering in Σ. Thus, ∏_{c∈Γ} s_{c} = s_{c_{1}} ⋯ s_{c_{m}}, if Γ = {c_{1}, …, c_{m}}, m ≥ 0, with c_{1} < ⋯ < c_{m}. All products of elements of S used in the following will be ordered ones. Consider L = η^{−1}(R) for some subset R ⊆ S. We are going to construct an asynchronous automaton A recognizing L. Of course, by standard techniques of a simple time-stamping modulo the degree of (Σ, D), the resulting automaton can be transformed into an equivalent asynchronous cellular one. The state set of A will be an n-fold direct product of S, n = |Σ|. The automaton A = (∏_{a∈Σ} Q_{a}, δ, q_{0}, F) is then defined by

δ : ∏_{a∈Σ} Q_{a} × Σ → ∏_{a∈Σ} Q_{a},

where for every a ∈ Σ:

Q_{a} = S

δ(q, a) = q · a = q′ with q_{b}′ = \{ \begin{matrix}( ∏_{{a≤c, \atop (a,c)∈D}} q_{c}) · η(a) & if b = a \\ 1 & if a < b, (a, b) ∈ D \\ q_{b} & otherwise \end{matrix}

Furthermore, let q_{0} = (1)_{a∈Σ} and F = {(q_{a})_{a∈Σ} ∈ ∏_{a∈Σ} Q_{a} | ∏_{a∈Σ} q_{a} ∈ η(L)}.

Proposition 3.1 Let L ∈ Rec(IM(Σ, D)) be recognized by the morphism η : IM(Σ, D) → S to the finite monoid S. Let A be the automaton defined above. Then A is asynchronous and we have L(A) = L.

Proof: First we show that A is asynchronous. The write-and-read–domain of a letter a ∈ Σ is given by the index set {c ∈ Σ | a ≤ c and (a, c) ∈ D}. Assume that for some a, b, c ∈ Σ, a ≤ b ≤ c we have (a, c) ∈ D and (b, c) ∈ D. Then (a, b) ∈ D follows, due to the ordering. Hence, if (a, b) ∈ I, then a and b have disjoint write-and-read–domain. Thus, A is asynchronous. In particular, for any trace w ∈ IM(Σ, D), the global state q_{0} · w = δ((1)_{a∈Σ}, w) is well-defined. For (q_{a})_{a∈Σ} = q_{0} · w we show the following two invariants:

1. a ≤ b and (a, b) ∈ I imply q_{b} η(a) = η(a) q_{b}.

2. a ≤ b ≤ c, (a, b) ∈ I, and (a, c) ∈ D imply q_{b} q_{c} = q_{c} q_{b}.

In order to verify these invariants we need some alphabetic information. We observe that for each local state q_{a}, a ∈ Σ, there exists some subset Γ_{a} ⊆ Σ with the following properties: q_{a} is an element of the submonoid generated by η(c), with c ∈ Γ_{a}, and for each c ∈ Γ_{a} there exists a chain a = a_{0} < ⋯ < a_{k} = c, k ≥ 0, such that (a_{i−1}, a_{i}) ∈ D for 1 ≤ i ≤ k. This crucial observation can be easily derived from the inductive definition of the transition function δ. Consider now a ≤ b ≤ c with (a, b) ∈ I and Γ_{b}, Γ_{c} ⊆ Σ as introduced above. Invariant (1) follows by showing that {a} × Γ_{b} ⊆ I. Invariant (2) follows by showing that Γ_{b} × Γ_{c} ⊆ I, whenever (a, c) ∈ D. For invariant (1) let b_{k} ∈ Γ_{b} and b = b_{0} < ⋯ < b_{k}, k ≥ 0 such that (b_{i−1}, b_{i}) ∈ D for 1 ≤ i ≤ k. Assume that we would have (a, b_{k}) ∈ D. Then k ≥ 1 and (b_{k−1}, b_{k}) ∈ D implies (a, b_{k−1}) ∈ D. We can continue this way and we arrive to (a, b_{0}) ∈ D, see also Figure 1. This is a contradiction to (a, b) ∈ I. Thus, (a, b_{i}) ∈ I for all 1 ≤ i ≤ k; a fact which will be used below, too. For invariant (2) let (a, c) ∈ D, b_{k} ∈ Γ_{b}, c_{m} ∈ Γ_{c} with b = b_{0} < ⋯ < b_{k} and c = c_{0} < ⋯ < c_{m}, k, m ≥ 0, such that (b_{i−1}, b_{i}) ∈ D, (c_{j−1}, c_{j}) ∈ D for 1 ≤ i ≤ k, 1 ≤ j ≤ m. We show by induction that (b_{i}, c_{j}) ∈ I for all i, j. Assume first that c_{m} ≤ b_{k}. Then we have k ≥ 1 (since b < c) and (c_{m}, b_{k}) ∈ D, (b_{k−1}, b_{k}) ∈ D

a  b_{0}  ⋯  b_{k−1}  b_{k}

Figure 1: Consequence of (a, b_{k}) ∈ D.

imply (c_{m}, b_{k−1}) ∈ D. Hence we may assume b_{k} < c_{m}. Suppose next that m ≥ 1. Then (b_{k}, c_{m}) ∈ D, (c_{m−1}, c_{m}) ∈ D imply (b_{k}, c_{m−1}) ∈ D. Hence, we may assume m = 0 and we obtain the following situation:

a < b = b_{0} < ⋯ < b_{k} < c, k ≥ 0.

Finally, suppose that we would have (b_{i}, c) ∈ D for some 1 ≤ i ≤ k. Since (a, c) ∈ D this implies (a, b_{i}) ∈ D, contradicting the fact mentioned in the proof of (1) above. Thus, both invariants (1) and (2) are valid. The proposition follows from the following claim:

For (q_{a})_{a∈Σ} = q_{0} · w we have ∏_{a∈Σ} q_{a} = η(w).

The claim is satisfied for |w| = 0 since q_{0} = (1)_{a∈Σ}. By induction assume that the claim holds for q = q_{0} · w and let q′ = q · a for some letter a ∈ Σ. It is enough to show:

(∏_{a≤c} q_{c}) η(a) = ( ∏_{{a≤c, \atop (a,c)∈D}} q_{c}) η(a) ( ∏_{{a<b, \atop (a,b)∈I}} q_{b}).

However, this last formula is immediate from the two invariants shown above. This completes the proof of the proposition. □

The example below illustrates the construction for a dependence alphabet on four letters Σ = {a, b, c, d} with the following dependence relation D:

a b  c  d

The alphabet Σ can be ordered as a < b < c < d (note that [d, c, b, a] is a perfect vertex elimination scheme). Let η : IM(Σ, D) → ZZ/nZZ be a morphism computing the length of a trace modulo n, n ≥ 1. Then the construction for asynchronous automata given above yields e.g. the following transition mappings, together with some concrete computations in ZZ/nZZ:

x_{a} x_{b} x_{c}  x′_{a}0 = x_{a} + x_{b} + x_{c} + 1 mod n 0 a

x_{b} x_{c}  x′_{b} = x_{b} + x_{c} + 1 mod n 0 b

x_{c} x_{d}  x′_{c} = x_{c} + x_{d} + 1 mod n 0 c

x_{d}  x′_{d} = x_{d} + 1 mod n d

δ(q_{0}, c a b d ) = ( \begin{matrix}2 \\ 1 \\ 0 \\ 1 \end{matrix} )

δ(q_{0}, a −b −c −d) = ( \begin{matrix}1 \\ 1 \\ 1 \\ 1 \end{matrix} ) δ(q_{0}, d −c −b −a) = ( \begin{matrix}4 \\ 0 \\ 0 \\ 0 \end{matrix} )

Remark 3.2 Note that as soon as the dependence graph contains a chordless cycle of length greater than three, the automaton constructed above is not asynchronous anymore. More precisely, for any ordering ≤ of the alphabet Σ there exist letters a < b < c (on the cycle) satisfying (a, c) ∈ D, (b, c) ∈ D, but (a, b) ∈ I. In this case however, c belongs to both write-and-read–domain of a and b.

References

[Dir61] G. A. Dirac. On rigid circuit graphs. Abh. Math. Sem. 25, Univ. Hamburg, 1961.

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

[Gol80] M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs. Academic Press, New York, 1980.

[KMS94] N. Klarlund, M. Mukund, and M. Sohoni. Determinizing asynchronous automata. In Serge Abiteboul and Eli Shamir, editors, Proceedings of the 21st International Colloquium on Automata, Languages and Programming (ICALP’94), Jerusalem (Israel) 1994, number 820 in Lecture Notes in Computer Science, pages 130–141, 1994.

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

[Mét87] Y. Métivier. An algorithm for computing asynchronous automata in the case of acyclic non-commutation graph. In Th. Ottmann, editor, Proceedings of the 14th International Colloquium on Automata, Languages and Programming (ICALP’87), Karlsruhe (FRG) 1987, number 267 in Lecture Notes in Computer Science, pages 226–236, Berlin-Heidelberg-New York, 1987. Springer.

[Mus94] A. Muscholl. On the complementation of Büchi asynchronous cellular automata. In Serge Abiteboul and Eli Shamir, editors, Proceedings of the 21st International Colloquium on Automata, Languages and Programming (ICALP’94), Jerusalem (Israel) 1994, number 820 in Lecture Notes in Computer Science, pages 142–153. Springer, 1994.

[Per89] D. Perrin. Partial commutations. In Proceedings of the 16th International Colloquium on Automata, Languages and Programming (ICALP’89), Stresa (Italy) 1989, number 372 in Lecture Notes in Computer Science, pages 637–651, Berlin-Heidelberg-New York, 1989. Springer.