Marcella Anselmo
email: anselmo@dia.unisa.it.

Alessandra Cherubini
email: alessandra.cherubini@polimi.it.

Pierluigi San

REGULAR LANGUAGES AND ASSOCIATIVE LANGUAGE DESCRIPTIONS †

Keywords: Formal languages, Regular languages, Associative descriptions, Commutative languages, Group languages, Threshold locally testable languages

come

Introduction

The Associative Language Description model (ALD) [START_REF] Cherubini | Languages based on structural local testability[END_REF] was originally motivated by the want of a brain compatible theory of language. In essence, this definition combines the concepts of local testability and of phrase structure in as simple a way as possible, aligned with current views on † Work partially supported by MIUR grants PRIN 2005015419-002: "Linguaggi Formali e Automi: Metodi, Modelli e Applicazioni" and FIRB RBAU01MCAC: "Applicazioni della Teoria degli Automi all'Analisi, alla Compilazione e alla Verifica di Software Critico e in Tempo Reale". information processing in the brain [START_REF] Braitenberg | Entwurf einer neurologischen Theorie der Sprache[END_REF]. A similar model was already proposed in [START_REF] Joshi | Local constraints in the syntax and semantics of programming languages[END_REF]. The ALD definition introduces a solution to a few shortcomings of Context-Free (CF ) grammars, disallowing certain "unpractical" languages (such as counting context-free languages, where derivation trees are characterized by numerical congruences) and not requiring metasymbols (the nonterminals) which are "external" to the language. Many basic properties of the ALD model were established in [START_REF] Cherubini | Some structural properties of associative language descriptions[END_REF] and in [START_REF] Cherubini | Associative language descriptions[END_REF], such as: nonclosure under union, concatenation and homomorphism; strict inclusion in the CF family (only noncounting context-free languages are ALD); comparison with other families; hierarchy theorems; etc. The expressive adequacy of the ALD family in terms of common artificial languages such as Pascal and HTML has been shown in [START_REF] Crespi Reghizzi | Associative definitions of programming languages[END_REF].

The main open problem about the ALD family is the inclusion of regular languages in the ALD family. The lack of closure properties does not allow the use of standard ways to prove the (non)inclusion of regular languages in other families of languages, while many "ad hoc" methods enable to prove the inclusion of several classes of regular languages in ALD family, but they do not seem to generalize to all regular languages.

The objective of this paper is to prove some inclusion results of subfamilies of regular languages into ALD family. More in details, we show that regular threshold locally testable languages (3), regular positive commutative languages, regular commutative languages on an alphabet of at most two elements and regular group languages are all ALD languages. Moreover, there is an ALD language in each level of the (restricted) star hierarchy. All these results seem to show that ALD languages are "well-distributed" over the class of regular languages. These considerations, together with many efforts towards finding a negative answer to the question, seem to support the conjecture that every regular language is ALD. Unfortunately, the proof techniques applied to show that each of these families are ALD do not seem to be generalizable to every regular language.

Section 2 recalls the basic definitions and some relevant properties of the model, while Section 3 shows the main results of the paper. Section 4 draws a few conclusions.

Basic definitions and properties

We recall here the following definitions from [START_REF] Cherubini | Associative language descriptions[END_REF].

Let Σ be a finite alphabet, and let ∆ ∈ Σ be the placeholder. A stencil tree is a tree T such that: the internal nodes of T are labelled by ∆ and the leaves of T have labels in Σ ∪ {ǫ}. The constituents of a stencil tree are its subtrees of height one and leaves with labels in Σ ∪ {ǫ} ∪ {∆}. The frontier of a stencil tree T or of a constituent K is denoted, respectively, by τ (T ) and τ (K). A maximal subtree of T is a subtree of T whose leaves are also leaves of T .

Definition 2.1 (Left and right contexts)

Let T be a stencil tree. For an internal node i of T , let K i and T i be respectively the constituent and the maximal subtree of T having root i. Consider the tree T ′ obtained by excising the subtree T i from T , leaving only the root labelled ∆ of T i behind. Let s, t ∈ Σ * be two words such τ (T ′ ) = s∆t. The left context of K i in T and of T i in T is left(K i , T ) = left(T i , T ) = s; the right context of K i in T and of T i in T is right(K i , T ) = right(T i , T ) = t. Definition 2.2 (ALD, pattern, permissible contexts of a rule) Let ⊥ ∈ Σ be the left/right terminator. An Associative Language Description (ALD) A is a finite collection of triples (x, z, y), An ALD defines a set of constraints or test conditions that a stencil tree must satisfy, in the following sense. Definition 2.3 (Constituent matched by a rule, valid stencil tree) Let A be an ALD. A constituent K i of a stencil tree T is matched by a rule (x, z, y) of an ALD A iff:

K 1 K 2 K 3 K 4 ∆ ∆ aa b ∆ ∆ b K 2 b ∆ K 5 ε ε
1) z = τ (K i ), 2) x is a suffix of ⊥ lef t(K i , T ), and 3) y is a prefix of right(K i , T ) ⊥. A stencil tree T is valid for A iff each constituent K i of T is matched by a rule of A.
Definition 2.4 (Tree language and word language of an ALD) The (stencil) tree language defined by an ALD A, denoted by T (A), is the set of all stencil trees valid for A. The (word) language defined by an ALD A, denoted by L(A), is the set {x ∈ Σ * | x = τ (T ) for some tree T ∈ T (A)}.

Example 2.5 Consider the language L on the alphabet Σ = {a, b} defined by the regular expression b * aab * . An ALD A for L is: {(⊥, ∆aa∆, ⊥), (ǫ, b∆, a), (a, ∆b, ǫ), (a, ǫ, ǫ), (ǫ, ǫ, a)} A valid stencil tree for the word bbaab is shown in Figure 1.

Note that when a left/right context is ǫ then the actual context is irrelevant for a pattern. An ALD is a device for defining a set of stencil trees and a word language, corresponding to their frontiers by means of a test; hence, it is not a generative grammar. A simple example is the ALD: (⊥, ∆∆, ⊥), (⊥, a, b), (a, b, ⊥), defining the finite language ab. One cannot define an equivalent derivation relation →: ∆ → ∆∆ → a∆ → ab would not be correct, since each of the two rules (⊥, a, b), (a, b, ⊥) would require that the other one has already been applied.

Many other examples of regular and non regular languages belonging to ALD family as well as of CF languages which are not ALD can be found in [START_REF] Cherubini | Some structural properties of associative language descriptions[END_REF] and in [START_REF] Cherubini | Associative language descriptions[END_REF].

A few shorthands may be introduced to make the notation simpler and more compact. Given two words v, w and finite sets X, Y, Z of words, the notation (X, vZw, Y ) denotes the set of rules:

{(x, vzw, y) | x ∈ X, y ∈ Y, z ∈ Z}
Also, the new symbol Λ may be used to denote the optionality of one occurrence of ∆, that is Λ = {ǫ, ∆}. For instance, the ALD A of Example 2.5 may be rewritten as: {(⊥, ΛaaΛ, ⊥), (ǫ, bΛ, a), (a, Λb, ǫ)}. Moreover, for w

= a 1 • • • a n , with a 1 , • • • , a n ∈ Σ, Λ(w) denotes the language Λ(w) = Λa 1 Λ • • • Λa n Λ.
ALD languages have the following properties:

• Every ALD language is a CF -language (2).

• The ALD family is not closed under any of the following operations (2): union; (alphabetic, nonerasing) homomorphism; concatenation; Kleene star; intersection with regular languages; complementation; inverse alphabetic homomorphism.

• Both the degree (i.e., the length of the largest permissible context) and the width (i.e., the length of the longest pattern) classify the ALD family in an infinite, strict hierarchy.

• Every context-free language is the homomorphic image of an ALD language (1).

• Every 1-letter regular language is ALD (1).

• All regular languages of restricted star-height one are ALD (4).

Relations between regular languages and the ALD family

Since no proof has ever been found that every regular language is ALD, a natural approach is trying to prove that there are regular languages which are not ALD. However, this is not an immediate task. Before illustrating in the following subsections various new families of regular languages which are ALD, the next subsection illustrates a few techniques which might be used to solve the ALD vs. Regular problem.

Comparing ALD and regular languages

The nonclosure properties presented in Section 2 have been proven in (2) using nonregular ALD languages, and therefore do not help in ruling out that some regular language is not ALD. Also the obvious analogy between the ALD model and 1-variable CF grammars (definable by ALDs where all contexts are empty) do not help, even though regular languages are not included in the family of 1-variable CF languages. In fact, all languages of the form Ra, where R is a regular language on an alphabet Σ and a ∈ Σ are not 1-variable CF languages, but they are indeed ALD provided that R is an ALD language (if A is an ALD for R, an ALD for Ra is easily obtained by A transforming all the rules whose right context is ⊥ in rules whose right context is a ⊥ and adding the rule (⊥, ∆a, ⊥) to A if the empty word does not belong to R, the rule (⊥, Λa, ⊥) otherwise). The similarities of CF and ALD languages (due to the their structural equivalence) break down when considering regular languages. For example, it is well-known that all regular languages can be defined by a right-linear grammar. However, it is immediate to prove that this is not the case for right-linear ALD, as defined next. Definition 3.1 An ALD is right-linear if all its rules are of the form (x, yΛ, ⊥), for x ∈ (⊥ ∪ǫ)Σ * , y ∈ Σ + . Proposition 3.2 There exist regular languages that cannot be defined by a right-linear ALD.

Proof: Consider L = {w ∈ {a, b} * | |w| a = 1}, where |w| a gives the number of occurrences of the letter a in the word w. Assume that there is a right-linear ALD A for L of degree k > 0 and width m > 0. Consider a word zb 2m+k ab 2m+k corresponding to a stencil tree Z. Since the ALD is right-linear, there are two constituents

K, K ′ of Z such that τ (K) ∈ b + ∆, τ (K ′ ) ∈ b * ab * ∆ and left(K, Z) ∈ b * b k = left(K ′ , Z ′ ) ∈ b * b k , with right(K, Z) = right(K ′ , Z ′ ) =⊥. Hence, the stencil tree Z ′ obtained by replacing K ′ in Z with K is valid for A, but τ (Z ′ ) ∈ b + and hence is not in L. ✷
The proof above can be generalized to provide a general tool to prove that a language is not ALD, namely the Swapping Lemma (2), which allows the exchange of two subtrees of two ALD valid trees, provided they have similar profiles. Before presenting it, a few definitions are needed.

Definition 3.3 (f irst k , last k ,left k , right k )
For every w ∈ Σ∪ ⊥ * , first k (w) denotes the prefix of length k of w if |w| ≥ k, otherwise it denotes w; last k (w) is the suffix of w of length k if |w| ≥ k, otherwise w. The two operators are extended to every stencil tree

T : first k (T ) =first k (τ (T )), last k (T ) = last k (τ (T )).
Let Z be a stencil tree and T be one of its maximal subtrees:

left k (T, Z) = last k (lef t(T, Z)), that is the left context of length k of T in Z. Symmetrically, right k (T, Z) = f irst k (right(T, Z)), that is the right context of length k of T in Z.

Lemma 3.4 (Swapping Lemma)

Let A be an ALD of degree k ≥ 0 and let Z and Z ′ be two valid trees of A, not necessarily distinct. Suppose that there exist two maximal subtrees T of Z and T ′ of Z ′ such that:

left k (T, Z) = left k (T ′ , Z ′ ), right k (T, Z) = right k (T ′ , Z ′ ), last k (T ) = last k (T ′ ), first k (T ) = first k (T ′ ).
Then also the stencil tree Z ′′ obtained from Z by replacing the subtree T with the subtree T ′ is a valid tree of A.

The crux of Lemma 3.4 for proving that a regular language R is not ALD is that it requires identifying valid stencil trees for a word of R: unfortunately, in general, one does not have much information about their structure. The lemma is however particularly useful to prove that certain nonregular languages are not ALD, by combining it with traditional pumping lemmata of CF languages (that allow the identification of valid ALD trees for a word), as shown in Prop. 3.8 below (which is a more precise version of Corollary 3.7 of (2)). We first recall a traditional periodicity result for CF languages, namely the Ogden Lemma. A few preliminary definitions are useful. The symbols in a word z may be characterized by their positions: 1, 2, . . . , |z| in z, starting from the leftmost and going to the rightmost. A m-marked word mmk(z) is a word z with a set of at least m ≥ 0 positions of z. Definition 3.5 Given a language L, an integer m ≥ 0 and a m-marked word mmk(z), with z ∈ L and |z| ≥ m, an Ogden factorization of z is a 5-tuple (x, u, w, v, y) such that:

1. z = xuwvy; 2. u and v together correspond to at least one marked position in mmk(z); 3. uwv corresponds to at most m marked positions in mmk(z); 4. for every i ≥ 0, xu i wv i y ∈ L. Lemma 3.6 (Ogden's Lemma) For an infinite CF language L there exists an integer m > 0 such that for all m-marked words mmk(z), with z ∈ L and |z| > m, there exists an Ogden factorization.

We remind the reader that if all positions are marked, then Ogden's Lemma is reduced to what is typically called the Pumping Lemma for CF languages. Definition 3.7 Two Ogden factorizations (x, u, w, v, y) and (x ′ , u ′ , w ′ , v ′ , y ′ ) are k-similar if the following conditions hold for some i, j ≥ 0:

1. f irst k (u i wv i ) = f irst k (u ′ j w ′ v ′ j ), 2. last k (u j wv i ) = last k (u ′ j w ′ v ′ j ), 3. f irst k (y) = f irst k (y ′ ), 4. last k (x) = last k (x ′ ). Proposition 3.8 For any ALD language L ⊆ Σ * of degree k ≥ 0, there exists a constant m > 0 such that, given two marked words m -mk(z), m -mk ′ (z ′ ), with z, z ′ ∈ L and |z| > m, |z ′ | > m,
if all pairs of Ogden factorizations for mmk(z) and mmk ′ (z ′ ) are k-similar, then for every pair of Ogden factorizations (x, u, w, v, y) and (x ′ , u ′ , w ′ , v ′ , y ′ ) of mmk(z) and mmk ′ (z ′ ) (respectively), xu ′h w ′ v ′h y ∈ L for every h ≥ 0.

To show that a language L is not ALD, one has to suppose that there is an ALD of degree k, select z, z ′ ∈ L and a marking for z and a marking for z ′ ; then, find all possible Ogden factorizations of z and z ′ , show they are all pairwise k-similar and then prove that a contradiction ensues for every factorization, by creating for each case a word z ′′ ∈ L. For instance, we can show that the (nonregular) language {a n cb n a m db m | n, m ≥ 0} is not ALD. Apply Ogden's Lemma to a string z = a n cb n a m db m , where n and m are greater than the constant of the Lemma. Mark the leftmost group of a in z: by Ogden's Lemma, for every corresponding Ogden factorization

(x, u, w, v, y) of z then f irst k (uwv) = a k = last k (x), last k (uwv) = b k = f irst k (y) and uwv is of the form a + cb + (if |u| < k or |v| < k consider xu k wv k y instead). Analogously, by marking the rightmost group of a, if (x ′ , u ′ , w ′ , v ′ , y ′ ) is an Ogden factorization then f irst k (u ′ w ′ v ′ ) = a k = last k (x ′ ), last k (u ′ w ′ v ′ ) = b k = f irst k (y ′ ) and u ′ w ′ v ′ is
of the form a + db + . By applying Proposition 3.8 to z ′ = z, a word in a + db + a + cd + should be in the language, a contradiction.

Unfortunately, Proposition 3.8 does not seem very helpful in proving that some regular languages are not ALD. In fact, Ogden's Lemma seems too weak, when applied to regular languages, to restrict enough the possible Ogden factorizations of a word. For instance, the proof above does not work for the (ALD) regular language L = a * cb * a * db * . As above, consider in fact a string z = z ′ = a n cb n a m db m , where n and m are greater than the constant of Ogden's Lemma. Mark the leftmost group of a in z. Then two sets of Ogden factorizations (x, u, w, v, y) of z are possible: a set o 1 of factorizations such that x ∈ a * , uwv ∈ a + , y ∈ a * cb n a m db m , and a set o 2 such that x ∈ a * , uwv ∈ a + cb + , y ∈ b + a m db m . Similarly, by marking the rightmost group of a in z, at least two sets of Ogden factorizations (x

′ , u ′ , w ′ , v ′ , y ′ ) of z are pos- sible: a set o ′ 1 such that x ′ ∈ a n cb n a * , u ′ w ′ v ′ ∈ a + , y ∈ a + db m , and another set o ′ 2 such that x ′ ∈ a n cb n a * , u ′ w ′ v ′ ∈ a + db + , y ∈ b + .
Then the Ogden factorizations in o 1 and o ′ 2 are not even k-similar, and Proposition 3.8 cannot be applied. Also, even if non-k-similar factorizations could be eliminated, the statement of Proposition 3.8 may not lead to a contradiction. For instance, if

(x, u, w, v, y) ∈ o 1 and (x ′ , u ′ , w ′ , v ′ , y ′ ) ∈ o ′ 1 are k-similar, then for every h ≥ 0, xu ′h w ′ v ′h y is of the form a * a + a * cb n a m db m , which is in L.

Regular threshold locally testable languages

Threshold locally testable languages are a generalization of better known locally testable languages. In this section we prove that the class of regular threshold locally testable languages is contained in the ALD family. For any regular threshold locally testable language, an ALD can be devised in such a way to simulate the run of a scanner that reading a word from left to right counts the occurrences of meaningful factors.

Let Σ be a finite alphabet. Denote with Σ <h the set {ǫ} ∪ Σ ∪ Σ 2 ∪ . . . Σ h-1 . For every word x, w ∈ Σ + let |w| x be the number of occurrences of x as a factor of w and let F(w) be the set of factors of w. For every integer h, let

F (x, h) = {w ∈ Σ * | |w| x ≥ h ≥ 0}. For instance, F (x, 1)
is the language Σ * xΣ * and its complement F (x, 1) is the set of words where x is a forbidden factor. Let A ⊆ Σ + be a finite set. A regular language L is said to be threshold locally testable (tlt (3)) if may be described as a boolean composition of a finite set B of languages of the form Σ * x, xΣ * , {x}, F (x, h), with x ∈ Σ + , h ≥ 0. A locally testable language is a special case of tlt where each language of the form F (x, h) has h = 1.

To prepare the proof of the next theorem, we need a few more definitions. Given B as above, there is a finite set G B ⊆ (⊥ ∪Σ) + such that:

G B = {x ⊥| Σ * x ∈ B} ∪ {⊥ x | xΣ * ∈ B} ∪ {⊥ x ⊥| {x} ∈ B} ∪ {x | ∃h ≥ 0 : F (x, h) ∈ B}.
We also extend the notion of stencil tree to a generalized stencil tree: Definition 3.9 A tree α is a generalized stencil tree if the internal nodes of α are labelled by ∆ and the leaves of α have labels in Σ ∪ {ǫ, ∆} (i.e., ∆ is allowed on the frontier of α).

The concepts of constituents and validity can be immediately extended to generalized stencil trees. The generalized tree language G T (A) of an ALD A is the set of generalized stencil trees valid for A. Notice that the word language L(A) is equal to {x ∈ Σ * | x = τ (α) for some tree α ∈ G T (A)}.

The proof that every tlt L, defined by a boolean function of a set B, is ALD is based on the following observation. To decide whether a word w is in L it is possible to use a scanner endowed with one vector V of monotonic, finite counters, with one counter V x for all x ∈ G B : the scanner reads the word from left to right, one letter at a time, and increments one counter V x whenever: 1) the current prefix of w ends in the factor x, and 2) the counter V x has not reached its threshold. At the end of the scan of w, the scanner may check whether the various counters have reached their threshold, storing the results in a boolean vector. To check if w ∈ L, it is enough to apply a suitable boolean function, depending on L, to this boolean vector. A linear ALD A can be devised in such a way that a root-to-frontier visit of the constituents of a valid tree of frontier w, for every long enough w ∈ Σ + , replicates the left-to-right run of the above scanner on w, with the left context l representing the prefix of w already examined by the scanner, and the length of the right context as a monotonic encoding of the vector V. An ALD for this contains (apart from some suitable initialization and termination rules to be described next) rules of the following form:

(y, a∆Σ h , Σ j ⊥)

with y ∈ Σ k-1 (k being the length of the largest word in G B ) , a ∈ Σ, and h, j defined by a suitable encoding rule to be discussed. Hence, a rule as above simulates a move of the scanner reading a after a factor y (hence, matching a factor ya), with a counter configuration V encoded by j, and moving to the new configuration V ′ encoded by h + j.

Initialization rules (i.e., matching only constituents at the root of a valid tree) are quite straightforward. They have the form (⊥, y∆Σ h , ⊥) with y ∈ Σ k-1 and h encoding the factor of y in G B .

Termination rules are those matching only constituents without children, i.e., constituents at the frontier of a valid tree. The idea is that a generalized stencil tree, valid for A, has a frontier always of the form v∆z, with v, z ∈ Σ * , and |z| bounded. Hence, a termination rule of the form:

(y, ǫ, z ⊥) with y ∈ Σ k-1 , z ∈ Σ * is
in A whenever the encoding |z| corresponds to an acceptance configuration of the scanner. More precisely, since |z| only encodes the configuration of the scanner after reading v, and not after reading w = vz itself, one has to add a termination rule (y, ǫ, z ⊥) considering the configuration reached by the scanner after reading vz: there may be other factors of G B in z that have not been already counted. However, this test need not know the exact (unbounded) prefix v encountered by the scanner, but only its (bounded) encoding |z|, the bounded suffix y of v, and the factors in G B of the bounded word yz. Hence, for a tlt L there is finite set of possibilities and therefore the termination rules are finite and can be added to A.

Notice that all words whose encoding is longer than the word itself are not dealt with by the above construction. However, since the possible encodings are finite, the set F of words x ∈ L that are not longer than the largest encoding is finite. Hence, we just add to A a finite set of rules of the form (⊥, x, ⊥), for every x ∈ F .

The encoding used to store the vector V of monotonic counters is based on traditional ideas, loosely inspired by Gödel's famous encoding, based on prime factors, of sentences, proofs and theorems of arithmetic theory in his historical proof of the Incompleteness Theorem. Let g : G B → P, where P is the set of prime numbers, and g is one-to-one. We extend g to every x in the set (⊥ ∪Σ) * , by defining g(x) = 1 for each x ∈ G B . Now, given an integer j ≥ 0 and the decomposition p e1 1 p e2 2 . . . , with p i ∈ P, e i ≥ 0 in prime factors of an integer q > 0, define [q] j = p min(j,e1) 1 p min(j,e2) 2 . . . . Define ḡ to enumerate all relevant factors of each word v ∈ (Σ∪ ⊥) * as follows: ḡ(ǫ) = 0 and for v = ǫ:

ḡ(v) = w∈GB g(w) |v|w n (1)
Hence, the encoding ḡ(v) of v stores all counter values up to the largest threshold n. As an example, consider G B = {⊥ a, ⊥ b, aa, ab, ba, abab, abba, b ⊥, ⊥ aba ⊥}, with n = 2. An enumeration g is g(⊥ a) = 2, g(⊥ b) = 3, g(ab) = 5, g(ba) = 7, g(aa) = 11, g(b ⊥) = 13, g(⊥ aba ⊥) = 17, g(abab) = 19, g(abba

) = 23. Then, ḡ(⊥ aabab ⊥) = 2 × 3 × 5 2 × 7 × 11 × 13 × 19.
The complete proof of following Prop. 3.10 contains the correct update rules of the encodings used in the right contexts. Proposition 3.10 Each regular threshold locally testable language is an ALD language.

Proof:

Let L be a tlt, with B, G B defined as above. Let n = max (h | ∃x ∈ Σ + : F (x, h) ∈ B), and let k be the length of the largest word in G B . We claim that there exists an ALD Q such that L(Q) = L. The following property of the above-defined enumeration ḡ is immediate, for all

x, z ∈ Σ + , y ∈ Σ ≤k : ḡ(xyz) = [ḡ(xy) • ḡ(yz)/ḡ(y)] n (2)
Let G = {h ≥ 0 | ∃v ∈ Σ * : v ∈ Σ * ∧ h = ḡ(⊥ v ⊥)}. Clearly, G is finite. Let M = {m ≥ 0 | ∃v ∈ Σ + : v ∈ L ∧ m = ḡ(⊥ v ⊥)}. We claim that v ∈ L iff ḡ(v) ∈ M (with M finite).
The "only if" part is obvious from the definition of M , while the "if" part follows from the fact that L is a tlt: L is testable by checking a boolean expression, whose atoms can be checked for truth by looking at the encoding ḡ(⊥ v ⊥) (each F (x, h) can be checked since h ≤ n).

Let

Q 1 = {(⊥, x, ⊥) | x ∈ Σ * , |x| ≤ k + max(G), x ∈ L}. Q 1 is
the ALD defining exactly all the (finite number of) words of L of length not greater than k + max(G) (thus, Q 1 can always be constructed by checking all words of length up to k + max(G)).

Let

Q 2 = Q ′ 2 ∪ Q ′′ 2 , with: Q ′ 2 = (⊥, y∆Σ h , ⊥) | y ∈ Σ k-1 , h = ḡ(⊥ y) Q ′′ 2 = (y, a∆Σ h , Σ j ⊥) | y ∈ Σ k-1 , a ∈ Σ, j ∈ G, h[j • ḡ(ya)/ḡ(y)] n -j We claim that: (*) if a generalized stencil tree α is valid for Q 2 (i.e., α ∈ G T (Q 2 )), then ∃v, z ∈ Σ * : τ (α) = v∆z, ḡ(⊥ v) = |z|.
The proof of (*) is by induction on the number i of constituents of a (obviously linear) generalized stencil tree α valid for Q 2 . The base case i = 1 is immediate from the definition of Q ′ 2 . Let α have i + 1 constituents for i > 0. Then there exist

a ∈ Σ, x, v 1 , z ∈ Σ * , y ∈ Σ k-1 , β ∈ G T (Q 2 ) such that τ (β)v 1 y∆z, τ (α) = v 1 ya∆xz.
Hence, α has one constituent more than β, matched by the rule (y, a∆x, z

⊥) ∈ Q ′′ 2 . Hence, by definition of Q ′′ 2 , |x| = [|z| • ḡ(ya)/ḡ(y)] n -|z|. By (2), ḡ(v 1 ya) = [ḡ(v 1 y) • ḡ(ya)/ḡ(y)] n . By induction hypothesis (applied to β), ḡ(⊥ v 1 y) = |z|. Hence, |xz| = |x| + |z|([|z| • ḡ(ya)/ḡ(y)] n -|z|) + |z|[|z| • ḡ(ya)/ḡ(y)] n = [ḡ(⊥ v 1 y) • ḡ(ya)/ḡ(y)] n ḡ(⊥ v 1 ya).
We also claim that: (+) for every v ∈ Σ k-1 Σ * , z ∈ Σ * such that ḡ(⊥ v) = |z|, there exists a generalized stencil tree α ∈ G T (Q 2 ) such that τ (α) = v∆z. The proof of (+) is by induction on the length of v. The base case is v ∈ Σ k-1 : the thesis follows immediately from the definition of [START_REF] Cherubini | Associative language descriptions[END_REF], is equal to ḡ(⊥ w ′ a) = ḡ(⊥ v), which by hypothesis is exactly equal to |z|.

Q ′ 2 . If |v| > 0 then let v = w ′ a, w ′ ∈ Σ * , a ∈ Σ. By induction hypothesis, for all z ′ ∈ Σ + such that |z ′ | = ḡ(⊥ w ′ ) there exists a generalized stencil tree in G T (Q 2 ) of frontier w ′ ∆z ′ . In particular, we can select z ′ to be a suffix of z (|z ′ | = ḡ(⊥ w ′ ) ≤ ḡ(⊥ w ′ a) = |z|): z = z ′′ z ′ for one z ′′ ∈ Σ * . Let w ′′ be the suffix of length k-1 of w ′ . The claim is proved if (w ′′ , a∆z ′′ , z ′ ) ∈ Q 2 . By definition of Q 2 , it is enough to show that |z ′′ | = [|z ′ | • ḡ(w ′′ a)/ḡ(w ′′ )] n -|z ′ |, that is equivalent to show that |z| = |z ′ | + |z ′′ | must equal [|z ′ | • ḡ(w ′′ a)/ḡ(w ′′ )] n . By induction hypothesis, |z ′ | = ḡ(⊥ w ′ ): [|z ′ | • ḡ(w ′′ a)/ḡ(w ′′ )] n [ḡ(⊥ w ′ ) • ḡ(w ′′ a)/ḡ(w ′′ )] n , which by
Let

Q 3 = (y, ǫ, z ⊥) | y ∈ Σ k-1 , z ∈ Σ * , |z| ≤ max(G), [|z| • ḡ(yz ⊥)/ḡ(y)] n ∈ M, . We claim that an ALD Q for L is Q 1 ∪ Q 2 ∪ Q 3 . To show that L ⊆ L(Q), suppose v ∈ L. If |v| ≤ k + max(G) then v ∈ L(Q 1 ) ⊆ L(Q). If v > k + max(G) then ∃!x, x ′ ∈ Σ + | v = xx ′ and |x ′ | = max(G) (therefore, |x| ≥ k).
Hence, since ḡ(⊥ v) ≤ max(G), ∃w, z ∈ Σ + such that x ′ = wz and |z| = ḡ(⊥ v). Q 2 defines, by the above property (+), also the valid generalized stencil tree with frontier x∆z. It is enough to show that there is a rule in Q 3 of type (y, w, z ⊥), and v = xwz ∈ L(Q). To this effect, the other conditions being obviously verified, we need to prove that [|z| • ḡ(ywz ⊥)/ḡ(y)] n ∈ M , with y being the suffix of length k -

1 of x (|x| ≥ k). But |z|ḡ(⊥ x). Hence, [|z| • ḡ(ywz ⊥)/ḡ(y)] n = [ḡ(⊥ x) • ḡ(ywz ⊥)/ḡ(y)] n , which by (2) (and since y is a suffix of x) is equal to ḡ(⊥ xwz ⊥) ∈ M . To show that L(Q) ⊆ L, suppose that v ∈ L(Q 2 ∪ Q 3 ) (since L(Q) = L(Q 1 ) ∪ L(Q 2 ∪ Q 3
) and because we can ignore the obvious case v ∈ L(Q 1 )). Then v = xwz, where x, w, z ∈ Σ * and x∆z is the frontier of a generalized stencil tree valid for

Q 2 ⊆ Q, with (y, w, z ⊥) ∈ Q 3 , where y ∈ Σ k-1 is suffix of ⊥ x. By (2), ḡ(⊥ xwz ⊥) = [ḡ(⊥ x) • ḡ(ywz ⊥)/ḡ(y)] n , which is equal, since ḡ(⊥ x) = |z| by the above property (*) of Q 2 , to [|z| • ḡ(ywz ⊥)/ḡ(y)] n that by definition of Q 3 is in M . By definition of M , v = xwz ∈ L. ✷ Example 3.
11 We show here an example of the construction used in the proof of Prop 3.10. Consider the following tlt language L:

{aΣ * } ∩ F (aa, 2) ∩ ¬{Σ * b} ∪ ¬{aΣ * } ∩ ¬F (aa, 2) ∩ {Σ * b} Then G B = {⊥ a, aa, b ⊥}. Let g(⊥ a) = 2, g(aa) = 3, g(b ⊥) = 5. Hence, n = k = 2 and G = h | ∃0 ≤ h 1 , h 2 , h 3 ≤ 2ih = 2 h1 3 h2 5 h3 , with max(G) = 2 2 • 3 2 • 5 2 .
A few of the elements of G are actually useless, since for every word w,the exponent of factors 2 and 5 in ḡ(⊥ w ⊥) can never be larger than 1. M , by the definition of the expression of L and of the encoding g, is:

2 • 3 2 , 5, 3 • 5 . Q 1 is the finite set (⊥, x, ⊥) | x ∈ Σ * , |x| ≤ 2 + 2 2 3 2 5 2 , x ∈ L . Q ′ 2 = (⊥, y∆Σ h , ⊥) | y ∈ Σ k-1 , h = ḡ(y) = (⊥, a∆Σ 2 2 , ⊥), (⊥, b∆, ⊥) . Q ′′ 2 = (y, a∆Σ h , Σ j ⊥) | y ∈ Σ k-1 , a ∈ Σ, j ∈ G, h = [j • ḡ(ya)/ḡ(y)] n -j is the union of four sets AA, AB, BA, BB. AA = (a, a∆Σ h , Σ j ⊥) | j ∈ G, h = [j • ḡ(aa)/ḡ(a)] 2 -j
By the definition of ḡ and of the operator [] 2 , h in the expression of AA is equal to [3j] 2j, which is equal to 0 if j is a multiple of 3 2 , 2j otherwise. Rules in AA introduce a new occurrence of the factor aa: if the current encoding j has already counted factors aa up to the threshold 2, then the presence of the factor is disregarded. Otherwise, the length of the right context is incremented by twice its amount, i.e., it is multiplied by 3 = g(aa).

AB = (a, b∆Σ h , Σ j ⊥) | j ∈ G, h = [j • ḡ(ab)/ḡ(a)] 2 -j
By the definition of ḡ and of the operator [] 2 , h in the expression of AB is equal to [j] 2j, which is equal to 0. Rules in AB introduce a new occurrence of the factor ab, which is not in G B . Hence, the presence of this factor may be disregarded.

The other two sets can be computed as for the case of AB, obtaining h = 0 since they cannot add any factor of G B :

BA = (b, a∆, Σ j ⊥) | j ∈ G , BB = (b, b∆, Σ j ⊥) | j ∈ G
being very similar to AB.

Finally, the set Q 3 is too large to be computed here, since one has to check, for every h ∈ M , if every word yz in Σ h + 1 is such that ḡ(yz ⊥) ∈ M . For instance, we must check all 2 19 words of length k -1 + max(M ). We just give an example of a rule in Q 3 : (a, ǫ, b 5 ⊥) (in Q 3 since 5 ∈ M and ḡ(ab 5 ⊥) = 5 ∈ M ) and another example of a similar rule not in Q 3 : (a, ǫ, a 5 ⊥) (since 5 ∈ M and ḡ(aa 5 ⊥) = 3 2 ∈ M ).

Relations with the Star-height Hierarchy

In this section we consider the (restricted) star height hierarchy of regular languages and show that there is an ALD language in each level of this hierarchy. This implies that ALD languages are well distributed inside the class of regular languages.

Let consider for each i ≥ 0 the language R i on a binary alphabet given by a regular expression e i defined recursively as follows:

• e 0 = ǫ • e i+1 = (a 2 i e i b 2 i e i ) * , i ≥ 0.
The language R i has star height i (9). We introduce below, for each i, an ALD A i defining R i . Assuming that we are able of giving an ALD A i-1 defining R i-1 , the idea of the construction is that we can modify the rules of A i-1 to obtain a subset of rules of A i . In particular, by appending valid trees of A i-1 to a placeholder of a generalized valid tree with frontier (a 2 i Λb 2 i Λ) n , n ≥ 0 we obtain a tree whose frontier is in R i . Proposition 3.12 There is an ALD language in each level of the star height hierarchy.

Proof: We claim that R i is defined by the ALD A i whose rules are the following: x,y,ǫ)) = (xa 2 i , y, ǫ) for all (x, y, ǫ) ∈ A i (⊥) ∪ A i (b), and finally let

{(⊥, Λa 2 i-1 X i-1 Λ, ǫ), (⊥, ǫ, ⊥)} ∪ 1≤h<i (⊥ a 2 i-1 a 2 i-2 • • • a 2 i-h , Λa 2 i-h-1 X i-h-1 Λ, ǫ) ∪ 1≤h<i,i-h≤k<i {(ba 2 k a 2 k-1 • • • a 2 i-h , Λa 2 i-h-1 X i-h-1 Λ, ǫ)}∪ 1≤h<i,2 i-h ≤j<2 i-h+1 {(ab j , Λa 2 i-h-1 X i-h-1 Λ, ǫ)} where X t = Λb 2 t if t > 0 and X 0 = b. Let A i (⊥) = {(⊥ a 2 i-1 a 2 i-2 • • • a 2 i-h , Λa 2 i-h-1 X i-h-1 Λ, ǫ) | 1 ≤ h < i}, A i (b) = {(ba 2 k a 2 k-1 • • • a 2 i-h , Λa 2 i-h-1 X i-h-1 Λ, ǫ) | 1 ≤ h < i, i -h ≤ k < i} A i (a) = {(ab j , Λa 2 i-h-1 X i-h-1 Λ, ǫ) |1 ≤ h < i, 2 i-h ≤ j < 2 i-h+1 } let σ i ((
σ i ((⊥, Λa 2 i-1 X i-1 Λ, ǫ)) = {(⊥ a 2 i , Λa 2 i-1 X i-1 Λ, ǫ), (ba 2 i , Λa 2 i-1 X i-1 Λ, ǫ)} ∪{xb 2 i , Λa 2 i-1 X i-1 Λ, ǫ) |(x, Λa 2 i-2 X i-2 Λ, ǫ) ∈ A i (a)}
Then the ALDs A i can be recursively defined as follow:

A 1 = {(⊥, ΛabΛ, ǫ), (⊥, ǫ, ⊥)} A i+1 = {(⊥, Λa 2 i-1 X i-1 Λ, ǫ), (⊥, ǫ, ⊥)} ∪ A i (a) ∪ A i (b) ∪ σ i ((⊥, Λa 2 i-1 X i-1 Λ, ǫ)) ∪ (x,y,ǫ)∈Ai(⊥)∪Ai(b) σ i ((x, y, ǫ))
We will prove by induction on i that

R i = L(A i ). The case i = 1 is trivial (R 1 = (ab) * is ALD). Assume that R i-1 = L(A i-1
). We first show that R i ⊆ L(A i ). The proof that for all w ∈ R i it is the case that w ∈ L(A i ) is by induction on |w|. Both the empty word and the shortest non-empty word in R i ,

a 2 i-1 b 2 i-1 , belong to R i and to L(A i ). Then let w = 1≤h≤n (a 2 i-1 u h b 2 i-1 v h ) (where denotes concatenation) with u h , v h ∈ R i-1 , 1 ≤ h ≤ n and u 1 v 1 = ǫ if n = 1. First suppose n = 1. If v 1 = ǫ then w 0 = a 2 i-1 u 1 b 2 i-1
is a word of R i shorter than w, so there are both a valid tree T (w 0 ) of A i for w 0 and a generalized valid tree T 0 (see Def. 3.9) of A i , with τ (T 0 ) = w 0 ∆. Moreover, v 1 ∈ R i-1 , and hence there is a valid tree T (v 1 ) of A i-1 for v 1 . Since the proof now requires references to individual nodes of a stencil tree, we denote every node by the progressive integer obtained by enumerating the nodes of the tree in a breadth-first, left-to-right visit of the tree starting at the root (Hence, the nodes are numbered 0, 1, 2...). Let j be the leaf of T 0 labelled by ∆. Appending T (v 1 ) to the node j in T 0 results into a tree T with τ (T ) = w. To prove that T is a valid tree of A i we have to prove that each constituent of the maximal subtree T j , whose root is j, is matched by a rule of A i . Since T j is a copy of T (v 1 ), each constituent K of T j has in T (v 1 ) a copy matched by a rule r i-1 (K) ∈ A i-1 . Moreover, left(K, T ) = w 0 x with left(K, T (v 1 )) =⊥ x and either x = ǫ or f irst

2 i-2 (x) = a 2 i-2 . Hence, if r i-1 (K) ∈ A i-1 (a) ∪ A i-1 (b) ⊂ A i , K is matched by the same rule (of A i ) in T . Then suppose r i-1 (K) ∈ A i-1 (⊥) ∪ {(⊥, Λa 2 i-2 X i-2 Λ, ǫ)}. If r i-1 (K) is the rule (⊥ a 2 i-2 a 2 i-3 • • • a 2 i-h-1 , Λa 2 i-h-2 X i-h-2 Λ, ǫ) for some h, 1 ≤ h < i -1, then left(K, T ) = w 0 a 2 i-2 a 2 i-3 • • • a 2 i-h-1 and since last 1 (w 0 ) = b, K is matched in T by the rule (ba 2 i-2 a 2 i-3 • • • a 2 i-h-1 , Λa 2 i-h-2 X i-h-2 Λ, ǫ) ∈ A i-1 (b) ⊂ A i . Otherwise, if r i-1 (K) is the rule (⊥, Λa 2 i-2 X i-2 Λ, ǫ) then left(K, T ) = w 0 and since last 2 i (w 0 ) = a t b 2 i -t for some t > 0 such that 2 i -t ≥ 2 i-1 , then K is matched in T by the rule (ab 2 i -t , Λa 2 i-2 X i-2 Λ, ǫ) ∈ σ i-1 ((⊥, Λa 2 i-2 X i-2 Λ, ǫ)) ⊂ A i . Hence, each constituent K of T is matched by some rule of A i , and therefore T is a valid tree of A i . If v 1 = ǫ, then w 0 = a 2 i-1 u 1 b 2 i-1 with u 1 = ǫ, u 1 ∈ R i-1 .
Hence there is a valid tree T (u 1 ) for u 1 in A i-1 . Then let T 0 be the generalized stencil tree of A i formed by the constituent matched by the initial rule (⊥, a 2 i-1 ∆b 2 i-1 , ⊥). Appending T (u 1 ) to the placeholder of T 0 , we get a tree T with τ (T ) = w. Each constituent K of T (u 1 ) is matched by a rule r i-1 (K) ∈ A i-1 . Again, we can assume r i-1 (K)

∈ A i-1 (⊥)∪ {(⊥, Λa 2 i-2 X i-2 Λ, ǫ)}. If r i-1 (K) is the rule (⊥ a 2 i-2 a 2 i-3 • • • a 2 i-h-1 , Λa 2 i-h-2 X i-h-2 Λ, ǫ) for some h, 1 ≤ h < i -1, then left(K, T ) = a 2 i-1 a 2 i-2 a 2 i-3 • • • a 2 i-h-1 and K is matched by the rule (⊥ a 2 i-1 a 2 i-2 a 2 i-2 a 2 i-3 • • • a 2 i-h-1 , Λa 2 i-h-2 X i-h-2 Λ, ǫ) ∈ σ i-1 (A i-1 (⊥)) ⊂ A i . Otherwise, if r i-1 (K) is the rule (⊥, Λa 2 i-2 X i-2 Λ, ǫ) then left(K, T ) = a 2 i-1 and K is matched by the rule (⊥ a 2 i-1 , Λa 2 i-2 X i-2 Λ, ǫ) ∈ σ i-1 ((⊥, Λa 2 i-2 X i-2 Λ, ǫ)) ⊂ A i .
Then, in any case, each constituent K of T is matched by some rule of A i , and T is again a valid tree of A i . Then consider the case n ≥ 1. Both

w 1 = a 2 i-1 u 1 b 2 i-1 v 1 , w 2 = 2≤h≤n (a 2 i-1 u h b 2 i-1 v h )
are shorter than w and belong to R i : by induction, there are two valid trees T (w 1 ) and T (w 2 ) of A i such that τ (T (w 1 )) = w 1 , τ (T (w 2 )) = w 2 . T (w 2 ) has a unique constituent K matched by a rule of the form (⊥, x, ǫ) with x ∈ {a 2 i-1 Λb 2 i-1 Λ}. Replacing K with a constituent K ′ matched by the rule (⊥, ∆x, ǫ), we get a generalized valid stencil tree T 2 whose frontier is ∆w 2 . Let j be the unique leaf of T 2 labelled by a placeholder. Appending T (w 1 ) to the node j of T 2 results in a tree T with τ (T ) = w 1 w 2 = w. To prove that T is a valid tree, it is enough to verify that all of its constituents appended to a node k ≥ j are matched by some rule of A i . Let T 1 be the maximal subtree of T of root j. T 1 is a copy of T (w 1 ), so each constituent C appended to a node of T 1 has the same left context of its copy in T (w 1 ): it must be matched by some rule of A i . Now let C be a constituent of T appended to a node m > j not belonging to the set of nodes of

T 1 . C is a constituent of T 2 : it is matched in T 2 by a rule r i (C) of A i . Obviously, left(C, T ) = w 1 x where left(C, T 2 ) =⊥ x and f irst 2 i-1 (x) = a 2 i-1 . So if r i (C) ∈ A i (a) ∪ A i (b) then C is matched by r i (C) also in T . Then let r i (C) ∈ A i (⊥)∪ {(⊥, Λa 2 i-1 X i-1 Λ, ǫ)}. If r i (C) is the rule (⊥ a 2 i-1 a 2 i-2 • • • a 2 i-h , Λa 2 i-h-1 X i-h-1 Λ, ǫ) for some h, 1 ≤ h < i, then left(C, T ) = w 1 a 2 i-1 a 2 i-2 • • • a 2 i-h and since last 1 (w 1 ) = b, K is matched in T by the rule (ba 2 i-1 a 2 i-2 • • • a 2 i-h , Λa 2 i-h-1 X i-h-1 Λ, ǫ) ∈ (A i (b)) ⊂ A i . Otherwise, if r i (C) is the rule (⊥, Λa 2 i-1 X i-1 Λ, ǫ)
, then left(C, T ) = w 1 and since last 2 i (w 0 ) = a t b 2 i -t for some t > 0 such that 2 it ≥ 2 i-1 , C must be matched in T by the rule (ab

2 i -t , Λa 2 i-1 X i-1 Λ, ǫ) ∈ A i (a) ⊂ A i .
Hence, each constituent C of T is matched by some rule of A i : T is a valid tree of A i . So R i ⊆ L(A i ) for all positive integers i.

To prove the opposite inclusion, R i ⊇ L(A i ), we have to show that the frontier of each valid tree of A i belongs to R i for each i > 0. Again, the proof is by induction on i. Let T be a valid tree of

A i . Of course, if T has height 1, τ (T ) = a 2 i-1 b 2 i-1 ∈ R i . Assume τ (T ′ ) ∈ R i for each valid tree T ′ of A i of
height m < n and let T a valid tree of height n. The constituent K 0 of T with the same root 0 of T is matched by a rule (⊥, Λa 2 i-1 Λb 2 i-1 Λ, ⊥). Enumerate all the nodes in T also when they are labelled by Λ = ǫ, and denote by T i the maximal subtree of T appended to the node i. T 1 (if non empty) is a valid tree of

A i of height m ≤ n -1, hence w 1 = τ (T 1 ) ∈ R i . T 2+2 i-1 , T 3+2 i (if non empty) are valid trees of A i-1 , shortly called T 2 and T 3 , hence w 2 = τ (T 2 ), w 3 = τ (T 3 ) ∈ R i-1 . So the frontier of T is w 1 a 2 i-1 w 2 b 2 i-1 w3 which obviously is in R i . ✷

Regular group languages

A group language is a language whose syntactic monoid is a group. We will show that any regular group language can be defined by an ALD. The proof is based on the analysis of the loops in a particular automaton recognizing the language that is related to its syntactic monoid. Let us firstly introduce some notations. Let L ⊆ Σ * be a regular language. Let us denote: ≡ L the syntactic congruence on L, M (L) the syntactic monoid of L with identity 1, and [w] L the ≡ Lcongruence class of w ∈ Σ * . Further, let us denote SYM(L) the automaton of transitions in M (L), that is the automaton whose graph is the Cayley graph of M (L), the identity 1 is the initial state and the final states are those ones representing words in L. It is well-known that SYM(L) recognizes L. We will say that a path (q 1 , q 2 , • • • , q n ) in a finite automaton has loop-nesting degree d = 0 if the path is simple (i.e., without loops) (q i = q j for any 1 ≤ i < j ≤ n); it has loop-nesting degree

d ≥ 1 if there exist 1 ≤ i 1 < i 2 < • • • < i 2k-1 < i 2k ≤ i n such that for any odd h = 1, • • • , 2k -1 we have that: q i h = q i h+1 , the path (q 1 , • • • , q i1 , q i2+1 , • • • , q i3 , q i4+1 , • • • , q i 2k-1 , q i 2k +1 , • • • , q n )
has loop-nesting degree d -1 and the path (q i h , q i h +1 , • • • , q i h+1 ) has no repetition of states unless for state q i h . Finally, given an automaton A, we denote by SSP (A), the set of labels of all successful simple paths (a simple path from an initial to a final state) in A, and by SL(A), the set of labels of all simple loops on the initial state of A. The reference to the automaton is dropped when there is no ambiguity on the automaton to be considered.

Remark that the automaton of transitions in M (L) is a deterministic automaton, and that in general it is bigger than the minimal automaton. Nevertheless its introduction here is useful because in the case of group languages its loops are very special: they can be inserted in any position of any word of the language, regardless to the contexts. This property allows us to construct an ALD defining the language. Proposition 3.13 Each regular group language is an ALD language.

Proof: Let L ⊆ Σ * be a regular language whose syntactic monoid M (L) is a group. Consider the automaton SYM(L) of transitions in M (L) and let y be the label of any loop on a state m in SYM(L). Hence my ≡ L m. Since M (L) is a group, there exists m ′ ∈ M (L) such that m ′ m = 1 and then [y] L = m ′ m [y] L = m ′ m = 1. This implies that any loop in SYM(L) is also a loop on any state and that for any u, v ∈ Σ * we have uv ∈ L iff uyv ∈ L. An ALD A(L) defining L can therefore be constructed as follows. The rules of A(L) are the following: {(⊥, Λ(w), ⊥) | w ∈ SSP } and {(ǫ, Λ(w), ǫ) | w ∈ SL}.

We claim that a word (is in L iff it) is recognized by SYM(L) iff it is defined by A(L). Remark that since w is in Λ(w), and because of the special kind of rules in A(L), we have that there is a valid stencil tree in A(L) with frontier w iff there is a valid generalized stencil tree (see Def. 3.9) in A(L) with frontier w ′ for any w ′ in Λ(w). A word w is recognized by SYM(L) iff there is a successful path in SYM(L) labelled w. We show by induction that there is a successful path labelled w in SYM(L) of loop-nesting degree d iff there is a valid generalized stencil tree for A(L) with frontier w ′ for any w ′ in Λ(w) and height h with h = d. One has d = 0 iff the path is simple iff the rules (⊥, Λ(w), ⊥) are in A(L), giving raise to a generalized valid stencil tree of height h = 0 whose frontier is w ′ for any w ′ in Λ(w). Suppose now d > 0. According to the above definition, a successful path of loop-nesting degree d > 0 is a successful path label z, where some simple loops with labels y 1 , • • • , y l are inserted on q i1 , q i3 , • • • , q i 2k+1 (note l ≥ k + 1). By induction, this holds iff there is a valid generalized stencil tree for A(L) of height h -1 = d -1 and frontier z ′ for any z ′ in Λ(z), and the rules (ǫ, Λ(y 1 ), ǫ), • • • , (ǫ, Λ(y l ), ǫ) are in A(L). Finally this condition holds iff there is a valid generalized stencil tree for A(L) of height h = d and frontier w ′ for any w ′ in Λ(w). ✷ Example 3.14 Let L ⊆ {a, b} * be the language recognized by the finite automaton ({1, 2, 3}, {a, b}, {1}, {1}, δ), where the transition function is given by: δ The sets SSP and SL for SYM(L) are the following: SSP = {1, ab, ba 2 , a 2 ba}, and SL = {b 2 , a 3 , abab, baba, ba 2 ba 2 , a 2 ba 2 b, aba 2 ba}. According to Proposition 3.13, an ALD defining language L is given by the set of the following rules: (⊥, ǫ, ⊥), (⊥, Λ(ab), ⊥), (⊥, Λ(ba 2 ), ⊥ ), (⊥, Λ(a 2 ba), ⊥), and (ǫ, Λ(b 2 ), ǫ), (ǫ, Λ(a 3 ), ǫ), (ǫ, Λ(abab), ǫ), (ǫ, Λ(baba), ǫ), (ǫ, Λ(ba 2 ba 2 ), ǫ), (ǫ, Λ(a 2 ba 2 b), ǫ), (ǫ, Λ(aba 2 ba), ǫ).

(q 1 , • • • , q i1 , q i2+1 , • • • , q i3 , q i4+1 , • • • , q i 2k-1 , q i 2k +1 , • • • , q n ) having loop-nesting degree d -1 and
(1, a) = δ(1, b) = 2, δ(2, a) = 3, δ(2, b) = 1, δ (3,

Relations with regular commutative languages

In this section we consider regular commutative languages. The family of regular commutative languages on an alphabet Σ is the boolean algebra generated by languages of the form

F (x, k) = {u ∈ Σ * | |u| x ≥ k ≥ 0} or F (x, k, n) = {u ∈ Σ * | |u| x ≡ k (mod n)} with 0 < k < n, for x ∈ Σ.
Any regular commutative language has a normal form and is recognized by a normal automaton. From the normal automaton we are able to construct an ALD for two classes of regular commutative languages: regular languages in Com + , the positive boolean algebra generated by languages of the form F (x, k), F (x, k, n), and regular commutative languages on an alphabet of at most two letters.

To introduce the normal form we need some notations. Define

E(x, k) = {u ∈ Σ * | |u| x = k} and for every k ≥ 0 define E(x, k, n) = {u ∈ Σ * | |u| x ≡ k(mod n), |u| x ≥ k}. Then: F (x, k) = 0≤i<k E(x, i), F (x, k, n) = 0≤i<n,i =k F (x, i, n), F (x, k) = E(x, k, 1)
, and, for k < n, E(x, k, n) = F (x, k, n). Hence, each regular commutative language belongs to the positive (i.e., negation-free) boolean algebra generated by the languages of the form E(x, k) or E(x, k, n) (called in the sequel literals L(x) on x) where k ≥ 0, n > 0, x ∈ Σ. Moreover, for each x ∈ Σ, L(x) = L(x) ∩ E(y, 0, 1), x = y and ∀h > 0 : E(x, k, n) = 0≤i<t E(x, k + in, hn) where t is the least integer such that k + tn ≥ hn. Definition 3.15 A regular commutative language L on Σ is representable in normal form if: ∃r > 0 : L = 1≤j≤r C j , where C j = x∈Σ L j (x), with either L j (x) = E(x, k j,x ) or L j (x) = E(x, k j,x , n x ) for some nonnegative integer k j,x depending on j and x and a positive integer n x only depending on x. The terms C j are called normal terms of L.

From previous remarks, using standard set operation properties, it is immediate to prove the following result. Fact 3.16 Each regular commutative language can be represented in normal form. Now we show how to construct a normal automaton recognizing a regular commutative language, starting from its normal form. The normal automaton is divided in some regions characterized by the allowed letters in the loops. Further the loops in a region can be inserted on any state in that region. This allows us to construct an ALD for any language of labels of successful paths ending in a same region.

In the sequel L will denote a regular commutative language in normal form on the alphabet Σ = {a 1 , a 2 , ..., a n }, and then L = 1≤j≤r C j for some positive integer r, with

C j = i=1,••• ,n L j (a i ). Let L i = 1≤j≤r L j (a i ) = ( j ′ ∈J ′ i E(a i , k j ′ ,ai )) ∪ ( j ′′ ∈J ′′ i E(x, k j ′′ ,ai , n ai )) be the union of all literals on a i occurring in L. Denote n i = n ai , k j,ai = k j,i and let K i = max j ′ ∈J ′ i {k j ′ ,i }, ( where
K i = 0 if J ′ i = ∅ and n i = 1 if J ′′ i = ∅). The Cayley graph Γ(L i ) of the syntactic monoid of L i has K i + n i + 1 vertices X i,l , 0 ≤ l ≤ K i + n i ,
loops labelled by a j with j = i are based at each vertex, an edge labelled by a i goes from X i,t to X i,t+1 for each t, 0 ≤ t ≤ K i + n i -1 and an edge with label a i from X i,Ki+ni to X i,Ki+1 . The graph Γ(L i ) has two parts: the first part contains the K i + 1 vertices X i,l , 0 ≤ l ≤ K i , and no loops whose labels contain a i are based at its vertices, the second part contains the n i vertices X i,l , K i + 1 ≤ l ≤ K i + n i and a loop labelled by a ni i is based at each vertex. The automaton SYM(L i ) has Γ(L i ) as underlying graph, initial state X i,0 and final states {X i,k j ′ ,i | j ′ ∈ J ′ i } ∪ j ′′ ∈J ′′ i {X i, kj ′′ ,i | kj ′′ ,i ≡ k j ′′ ,i (mod n i ) ∧ k j ′′ ,i ≤ kj ′′ ,i ≤ K i + n i }. Let Γ = i=1,n Γ(L i ). Γ is partitioned in 2 n regions denoted by Γ (η1,...,ηn) , with η i = 0, 1, composed as follows. Definition 3.17 Using the above notations, the normal automaton of a regular commutative language L on the alphabet Σ is an automaton A =< Γ, V (0,0,...,0) , F >, (with Γ the underlying graph, V (0,0,...,0) the initial state, F the set of final states) such that a vertex V (m1,m2,...,mn) ∈ F iff there exists a normal term C j = 1≤i≤n L j (a i ) of L and either L j (a i ) = E(a i , m i ) or L j (a i ) = E(a i , t i , n i ) with t i ≡ m i (mod n i ) and t i ≤ m i ≤ K i + n i .

Example 3.18 Let L ⊆ {a, b} * be the commutative language L = C 1 ∪C 2 , where C 1 = E(a, 2, 3)∩ E(b, 3) and C 2 = E(a, 3, 3) ∩ E(b, 4, 2). Following the above definitions and considering a = a 1 , b = a 2 , we have: n a = 3, n b = 2, J ′ 1 = ∅, J ′′ 1 = {1, 2}, J ′ 2 = {1}, J ′′ 2 = {2}, K 1 = 0 and K 2 = 3. The normal automaton of L is represented in Fig. 3, where the four regions Γ (0,0) , Γ (1,0) , Γ (0,1) and Γ (1,1) are shown. We find that in Γ (0,0) there are no loops on the vertices; in Γ (1,0) there are only loops labelled a 3 based on each vertex; in Γ (0,1) there are only loops labelled b2 based on each vertex; and in Γ (1,1) there is the same set of loops based on each vertex labelled by any anagram of a 3t b 2s , for some t, s ≥ 0. Fig. 3 also shows the way one can move from a region of the automaton to another one.

It is easy to verify that the normal automaton of a language L recognizes L. Moreover, for each V (m1,m2,...,mn) ∈ F , denote by A (m1,m2,...,mn) the automaton < Γ, V (0,0,...,0) , V (m1,m2,...,mn) >, whose unique final state is V (m1,m2,...,mn) . Then, the language L(A (m1,m2,...,mn) ) is a normal term of L; conversely, each normal term of L is a language L(A (m1,m2,...,mn) ) for some V (m1,m2,...,mn) ∈ F . If V (m1,m2,...,mn) is in the region Γ (η1,...,ηn) of Γ, L(A (m1,m2,...,mn) ) will be called for shortness an (η 1 , ..., η n )-normal term of L. A word w belonging to an (η 1 , ..., η n )-normal term of L, has m i occurrences of a i for i ∈ I ′′ (η1,...,ηn) while no upper bound is given for the occurrences of a i with i ∈ I ′ (η1,...,ηn) . For the definitions of SSP and SL, see Section 3.4. Lemma 3.19 With the above notations, each (η 1 , ..., η n )-normal term of a regular commutative language L on the alphabet Σ is an ALD language.

Proof: Obviously a (0, 0, ..., 0)-normal term of L is a finite language L(A (m1,m2,...,mn) ) (and it is On the other hand, the techniques used to capture these families in this paper do not seem to be generalizable to all regular languages. For instance, the method used here for showing that threshold locally testable (tlt) languages are ALD does not work for showing that regular languages in Com + (Σ) are ALD; but the method used to prove the latter, does not work for many commutative languages that are not in Com + (Σ) but are actually tlt (and hence ALD).

Other open questions for the ALD family concern the hierarchy with respect to the number of placeholders, various decidability properties, minimization in the length of contexts and of patterns of the rules.

  c 2007 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France

Fig. 1 :

 1 Fig. 1: A valid stencil tree for Example 2.5. Each Ki denotes a constituent matched by a rule. called rules, where x ∈ (ǫ ∪ ⊥)Σ * , y ∈ Σ * (⊥ ∪ ǫ), and z ∈ (Σ ∪ {∆}) * -{∆}. The word z is called the pattern of the rule (x, z, y) and the words x and y are called the permissible left/right contexts.

Fig. 2 :

 2 Fig. 2: The automaton SYM(L) for the language L in Example 3.14.

  a) = 1 and δ(3, b) = 3. The syntactic monoid of L is M (L) = {1, a, b, a 2 , ab, ba} with relations b 2 = 1, a 3 = 1, a 2 b = ba, aba = b, ba 2 = ab, and bab = a 2 . We have that M (L) is a group. The automaton SYM(L) of transitions in M (L) is given in Fig. 2.

Fig. 3 :

 3 Fig. 3: The normal automaton for language L of Example 3.18.

(0,0,...,0) (m1,m2,...,mn) = (X 1,m1 , ..., X n,mn ) with 0 ≤ m i ≤ K i , and no loop is based on its vertices. The apices on the vertex names indicate the region of Γ which the vertex belongs to and can be omitted.

1 0 b

Acknowledgements: We are indebted with many people for long discussions on the issue of inclusion of regular languages in ALD. Among them, we gratefully thank Eberhard Bertsch and Mark-Jan Nederhof, who proposed many candidate counterexamples and found the first proof that star-height one languages are ALD, and M. Volkov, who suggested some possible extensions to the results presented here.

obviously defined by the ALD A (0,0,...,0) (m1,m2,...,mn) whose rules are {(⊥, w, ⊥) | w ∈ L(A (m1,m2,...,mn) )}). Then let L(A (m1,m2,...,mn) ) be a (η 1 , ..., η n )-normal term of L with (η 1 , ..., η n ) = (0, 0, ..., 0). It is easy to verify that the automaton A (η1,...,ηn) (m1,m2,...,mn) , obtained by A (m1,...,mn) adding an edge labelled by a i going from each vertex V (h1,...,hi,...,hn) , with h i ≥ n ai -1, to the vertex V h1,...,hi-na i +1,...,hn for all i ∈ I ′ (η1,η2,...,ηn) recognizes L(A (m1,m2,...,mn) ). The same set of loops is based at each vertex of the automaton A (η1,...,ηn) (m1,m2,...,mn) , so using an argument similar to the one used in the proof of of Proposition 3.13, it is easy to prove that the ALD A (η1,...,ηn) (m1,m2,...,mn) whose rules are {(⊥, Λ(w), ⊥) | w ∈ SSP (A (η1,...,ηn) (m1,m2,...,mn) )} and {(ǫ, Λ(w), ǫ) | w ∈ SL(A (η1,...,ηn) (m1,m2,...,mn) )}, defines L(A (m1,m2,...,mn) ). ✷ Remark 3.20 For each commutative regular language L on the alphabet Σ, denote by F (η1,η2,...,ηn) the set of final states of its normal automaton belonging to the region Γ (η1,...,ηn) . If either F = F (η1,η2,...,ηn) or F = F (0,0,...,0) ∪ F (η1,η2,...,ηn) for some region Γ (η1,...,ηn) then L is an ALDlanguage. In fact, in such cases, all normal terms of L are either (η 1 , η 2 , ..., η n ) or (0, 0, ...0)normal terms. The ALDs defining (η 1 , η 2 , ..., η n )-normal terms differ only for their initial rules (i.e., rules of the form (⊥ u, v, w ⊥) for some u, w ∈ Σ * , v ∈ (Σ ∪ ∆) * ) and the ALDs defining (0, 0, ..., 0)-normal terms have only initial rules. Then the ALD defining L is obtained by taking all the rules of the ALDs defining the terms of L. In the other cases the union A of the ALDs defining the normal terms of L does not define L because the pattern of non initial rules of an ALD defining an (η 1 , η 2 , ..., η n )-normal term ((η 1 , η 2 , ..., η n ) = (0, 0, ..., 0)) of L, are different from the patterns of non initial rules of an ALD defining an

)) of L but these rules are not distinguished by means of their contexts, hence some words not belonging to L can be the frontier of a valid tree of the ALD A.

We have shown how to construct an ALD for any normal term of a regular commutative language. Unfortunately we are not able to construct an ALD in the general case of a regular commutative language, since the union of the ALD for each normal term does not always define the language (see Remark 3.20). Now we show how to solve the problem in two particular cases: regular languages in Com + (Proposition 3.21); and regular commutative languages on alphabets with two letters at most (Proposition 3.22).

Consider a language L belonging to Com + (Σ), i.e., to the positive boolean algebra generated by the languages of the form F (x, k) or F (x, k, n) with k < n and x ∈ Σ. In this case all final states of L are in the region Γ (1,...,1) of the normal automaton of L. Hence by Lemma 3.19 and Remark 3.20 the following Proposition immediately follows. Proposition 3.21 Let Σ be a finite alphabet. Each language in Com + (Σ) is an ALD language.

The following result for regular commutative languages on small alphabets can also be proved.

Proposition 3.22 A regular commutative language on an alphabet Σ with |Σ| ≤ 2 is an ALD language.

Proof: In (2), it was proved that each unary regular language is an ALD language. Then, let L be a regular commutative language in normal form on Σ = {a 1 , a 2 } and let A =< Γ, V (0,0) , F > be the normal automaton recognizing L. Obviously A has four regions. By Remark 3.20, it follows that the ALDs A

the non initial rules of the ALD defining an (η 1 , η 2 )-normal term have the same contexts of a non initial rule of the ALD defining an (η ′ 1 , η ′ 2 )-normal term only if they also have equal patterns. The regions of the normal automaton of L are four, and for each region (η 1 , η 2 ) a corresponding type of ALD A (η1,η2) was defined in Lemma 3.19. The ALDs A (0,0) defining (0, 0)-normal terms contain only initial rules, so they do not require modifications, hence

) is a (0, 0)-normal term of L. So we have to deal with the following three regions.

(i,j) ). In fact, the initial rules allow the introduction, by means of a valid tree of height 1, of all the words belonging to L(A

The non initial rules allow to pump a n1 1 . Region (0, 1). Let L(A (0,1) (i,j) ) be a (0, 1)-normal term. For every w ∈ Σ * , define EXP (0,1) (w) = Λ({Sh(w, a hn2

2

(i,j) with the following rules:

). The same argument of Region (1, 0) applies.

Region (1, 1). Let L(A

(1,1) (i,j) ) be a (1, 1)-normal term. For every w ∈ Σ * , define EXP (1,1) (w) = Λ({Sh(w, Sh(a hn1 1 , a ln2 2 )) | h, l ≤ 2(|w| + 1)}). Then let A

(1,1) (i,j) be the ALD with the following rules:

(i,j) ). Of course the frontier of each valid stencil tree is a word in L(A

(1,1) (i,j) ); conversely, a standard proof based on induction on the length of the words gives that a word w ∈ L(A (1,1) (i,j) ) belongs to the language defined by A (1,1) (i,j) . Now in the initial rules of ALDs A (1,0) defining the (1, 0)-normal terms of L, each placeholder has a left context of the form va n1 1 for some v ∈ Σ * ; hence, only the rule (a n1 1 , Λa n1 1 , ǫ) matches a constituent and does not affect the left context of the placeholder. Analogously, in the initial rules of ALDs A (0,1) , defining the (0, 1)-normal terms of L, each placeholder has a left context of the form va n2 2 , for some v ∈ Σ * ; hence, only the rule (a n2 2 , Λa n2 2 , ǫ) matches a constituent and does not affect the left context of the placeholder. So the non initial rules ALDs A (1,1) , whose left context belong to the set {(a 2 a t 1 | 0 < t < n 1 } ∪ {(a 1 a s 2 | 0 < s < n 2 }, which are the only rules whose patterns can contain both a 1 , a 2 can be applied only when the rule used as initial rule belongs to an ALD A (1,1) Unfortunately the ALD A

(1,0)

(2,3) ∪ A

(1,1)

(3,4) does not define L; indeed it also defines some word not belonging to L: as an example it defines a 2 b 5 . Following Proposition 3.22, let us construct another ALD A (2,3) has the following rules:

That is the initial rules are obtained from some x that is the shuffle of an anagram of a 2 b 3 with some a 3h with h ≤ 12 where we can put Λ only just after an a 3 . As an example for h = 1 we obtain as x: a 5 Λb 3 , ba 5 Λb 2 , b 2 a 5 Λb, b 3 a 5 Λ; for h = 2 we obtain: a 3 Λa 5 Λb 3 , ba 3 Λba 5 Λb, and so on.

The ALD A

Conclusions

In this paper, we partially tackled the inclusion of regular languages in the ALD family. The classes of regular languages known to be ALD do not cover all regular languages, but exhibit a remarkable variedness. For instance, group and locally testable languages have completely different syntactic monoids (groups and aperiodic monoids, respectively). Star-height one languages have non-empty intersection with both classes, and Proposition 3.12 says that ALD languages are "well-distributed" inside the class of regular languages, and that may be all regular languages are indeed ALD


A N Trahtman
email: trakht@macs.biu.ac.il

The Černý Conjecture for Aperiodic Automata

Keywords: deterministic finite automaton, synchronizing word, star-free language

A word w is called a synchronizing (recurrent, reset, directable) word of a deterministic finite automaton (DFA) if w brings all states of the automaton to some specific state; a DFA that has a synchronizing word is said to be synchronizable. Černý conjectured in 1964 that every n-state synchronizable DFA possesses a synchronizing word of length at most (n -1) 2 . We consider automata with aperiodic transition monoid (such automata are called aperiodic). We show that every synchronizable n-state aperiodic DFA has a synchronizing word of length at most n(n -1)/2. Thus, for aperiodic automata as well as for automata accepting only star-free languages, the Černý conjecture holds true.

Introduction

The problem of synchronization of DFA is natural and various aspects of this problem were touched upon the literature. We pay attention to the problem of the existence and of the length of a synchronizing word.

An important problem with a long story is estimating the shortest length of a synchronizing word. Best known as the Černý conjecture, it was proposed independently by several authors. Černý found in 1964 [START_REF] Černý | Poznamka k homogenym eksperimentom s konechnymi automatami[END_REF] an n-state DFA whose shortest synchronizing word was of length (n-1) 2 . He conjectured that this is the maximum length of the shortest synchronizing word for any DFA with n states. The conjecture has been verified for several partial cases [START_REF] Ananichev | Some results on Černý type problems for transformation semigroups[END_REF][START_REF] Dubuc | Sur le automates circulaires et la conjecture de Černý[END_REF][START_REF] Eppstein | Reset sequences for monotonic automata[END_REF][START_REF] Kari | Synchronizing finite automata on Eulerian digraphs[END_REF][START_REF] Rystsov | Almost optimal bound on recurrent word length for regular automata[END_REF][START_REF] Pin | Sur un cas particulier de la conjecture de Černý[END_REF] but in general the question still remains open. By now, this simply looking conjecture is arguably one of the most longstanding open problems in the theory of finite automata. The best upper bound for the length of the shortest synchronizing word for DFA with n states known so far is equal to (n 3n)/6 [START_REF] Frankl | An extremal problem for two families of sets[END_REF][START_REF] Kljachko | An extremal combinatorial problem connected with the bound on the length of a recurrent word in an automata[END_REF][START_REF] Pin | On two combinatorial problems arising from automata theory[END_REF]. For the rich and intriguing story of investigations in this area see [START_REF] Salomaa | Generation of constants and synchronization of finite automata[END_REF].

The existence of some non-trivial subgroup in the transition semigroup of the automaton is essential in many investigations of the Černý conjecture, see, e.g., [START_REF] Dubuc | Sur le automates circulaires et la conjecture de Černý[END_REF][START_REF] Pin | Sur un cas particulier de la conjecture de Černý[END_REF]. We use another approach and consider transition semigroups without non-trivial subgroups. This condition distinguishes a wide class of so-called aperiodic automata that, as shown by Schützenberger [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF], accept precisely star-free languages (also known as languages of star height 0). Star-free languages play a significant role in formal language theory.

We prove that every n-state aperiodic DFA with a state that is accessible from every state of the automaton has a synchronizing word of length not greater than n(n -1)/2, and therefore, for aperiodic automata as well as for automata accepting only star-free languages, the Černý conjecture holds true.

In the case when the underlying graph of the aperiodic DFA is strongly connected, this upper bound has been recently improved by Volkov who has reduced the estimation to n(n + 1)/6.

Preliminaries

We consider a complete DFA A with the input alphabet Σ. The transition graph of A is denoted by Γ and the transition semigroup of A is denoted by S.

Let p and q be two (not necessarily distinct) states of the automaton A. If there exists a path in A from the state p to the state q and the transitions of the path are consecutively labelled by σ 1 , . . . , σ k ∈ Σ then for s = σ 1 . . . σ k we write q = ps. We call a state q a sink if for every state p of A there exists a word s such that ps = q. For a set P of states and s ∈ Σ * , let P s denote the set {ps | p ∈ P }. A word s ∈ Σ + is called a synchronizing word for P if |P s| = 1, that is, ps = qs for all states p, q ∈ P . A word is said to be a synchronizing word of the automaton A (of the graph Γ) if it is synchronizing for the set of all states of A (the set of all vertices of Γ).

A binary relation β on the state set of A is called stable if, for any pair of states q, p and any σ ∈ Σ, from q β p it follows qσ β pσ. Recall that a stable equivalence relation on the state set of A is called a congruence of A. If ρ is a congruence of A, we denote by [q] ρ the ρ-class containing the state q. The quotient A/ρ is the automaton with the states [q] ρ and the transition function defined by the rule [q] ρ σ = [qσ] ρ for any σ ∈ Σ. For a word s over the alphabet Σ, we denote its length by |s|.

2 The graph Γ 2

The direct square Γ 2 of the transition graph Γ has as vertices all pairs (p, q), where p, q are vertices of Γ. The edges of the graph Γ 2 have the form (p, q) → (pσ, qσ) where σ ∈ Σ; such an edge is labelled by σ.

For brevity, a strongly connected component of a directed graph is referred to as an SCC. An SCC M of the graph Γ 2 is called almost minimal if, for every pair (p, q) ∈ M , one has p = q and, for every σ ∈ Σ such that pσ = qσ, there exists a word s ∈ Σ * such that (pσ, qσ)s = (p, q). We observe that then (pσ, qσ) ∈ M by the definition of an SCC. By Γ(M ) we denote the set of states that appear as components in the pairs from the almost minimal SCC M .

If M is an almost minimal SCC, we define the relation ≻ M as the transitive closure of M (where M is treated as a relation on the state set of our automaton). So r ≻ M q if there exists a sequence of states r = p 1 , . . . , p n = q such that n > 1 and (p i , p i+1 ) ∈ M for all i = 1, . . . , n -1. Let M be the reflexive closure and ρ M the equivalent closure of the relation ≻ M .

Lemma 1 For any almost minimal SCC M , the relation M is stable and the relation ρ M is a congruence.

Proof: Suppose u ρ M v. Then there exists a sequence of states

u = p 1 , . . . , p n = v (1)
such that for every integer i < n at least one of the pairs (p i+1 , p i ), (p i , p i+1 ) belongs to the almost minimal SCC M . Therefore in the sequence of states rs = p 1 s, . . . , p n s = qs, for any two distinct neighbors p i s, p i+1 s, the pair (p i s, p i+1 s) or its dual belongs to M . Hence rs ρ M qs.

If u M v, then there exists a sequence (1) such that for every integer i < n the pair (p i , p i+1 ) belongs to M . Then either (p i s, p i+1 s) ∈ M or p i s = p i+1 s, and therefore, p i s M p i+1 s in any case. Hence us M vs. ✷

From the definition of the relation ≻ M and Lemma 1, we obtain

Corollary 2 If r ≻ M q and rs / ∈ Γ(M ) for some word s, then rs = qs.

We also observe the following obvious property:

Corollary 3 Each state p from Γ(M ) belongs to a ρ M -class of size at least two.
Let us present the following new formulation of a result from [START_REF] Černý | Poznamka k homogenym eksperimentom s konechnymi automatami[END_REF]:

Lemma 4 An automaton A with the transition graph Γ is synchronizing if and only if the graph Γ 2 has a sink.

Proof: Let s be a synchronizing word of A. Then the unique pair of the set Γ 2 s is a sink of Γ 2 . Conversely, the components of a sink of Γ 2 obviously are equal. Let (t, t) be a sink. For any pair (p, q), there exists a word s such that (p, q)s = (t, t), that is, ps = qs = t. Some product of such words s taken for all pairs of distinct states from Γ is a synchronizing word of the graph Γ. ✷ Lemma 5 The sets of synchronizing words of the graphs Γ and Γ 2 coincide.

Proof: Let s be a synchronizing word of the graph Γ. Then there is a state q from Γ such that ps = q for every state p. Therefore for every pair (p, r) one has (p, r)s = (q, q). Thus, s is a synchronizing word of the graph Γ 2 . Now let t be a synchronizing word of the graph Γ 2 . Then there is a pair (q, v) such that (p, r)t = (q, v) for every pair (p, r). Therefore pt = q for an arbitrary state p from Γ and rt = v for an arbitrary state r from Γ. Consequently, v = q and t is a synchronizing word of the graph Γ. ✷

Aperiodic automata

A semigroup without non-trivial subgroups is called aperiodic. A DFA with aperiodic transition semigroup is called aperiodic too.

Let us recall that the syntactic semigroup of a star-free language is finite and aperiodic [START_REF] Schützenberger | On finite monoids having only trivial subgroups[END_REF] and the semigroup satisfies the identity x n = x n+1 for some suitable n. Therefore, for any state p ∈ Γ, any s ∈ S and for some suitable k, one has ps k = ps k+1 . Lemma 6 Let A be an aperiodic DFA. Then the existence of a sink in A is equivalent to the existence of a synchronizing word.

Proof: It is clear that, for any DFA, the existence of a synchronizing word implies the existence of a sink. Now suppose that A has at least one sink. For any state p and any sink p 0 , there exists an element s from the transition semigroup S such that ps = p 0 . The semigroup S is aperiodic, whence for some positive integer m we have s m = s m+1 . Therefore ps m = ps m+1 = p 0 s m , whence the element s m brings both p and p 0 to the same state p 0 s m which is a sink again. We repeat the process reducing the number of states on each step. Then some product of all elements of the form s m arising on each step brings all states of the automaton to some sink. Thus, we obtain in this way a synchronizing word. ✷

Let M be an almost minimal SCC. A t-cycle for M is a sequence of states

p 1 , p 2 , . . . , p m-1 , p m = p 1 (2)
such that n > 1 and (p i , p i+1 ) ∈ M for all i = 1, . . . , m -1. The next observation is the key ingredient of the proof.

Lemma 7 Let A be an aperiodic DFA and let M be an almost minimal SCC. Then there is no t-cycle for M and the quasi-order M is a partial order.

Proof: Suppose that ( 2) is a t-cycle of minimum size m among all t-cycles for the almost minimal SCC M . Let us first establish that m > 2. Indeed, p 1 = p 2 , whence m > 1. If m = 2 then the two pairs (p 1 , p 2 ) and (p 2 , p 1 ) belong to the SCC M . For some element u from the transition semigroup S, we have (p 1 , p 2 )u = (p 2 , p 1 ). Therefore p 1 u = p 2 , p 2 u = p 1 , whence p 1 u 2 = p 1 = p 1 u. This implies p 1 u 2k = p 1 = p 1 u = p 1 u 2k+1 for any integer k. However, semigroup S is finite and aperiodic, and therefore, for some k we have u 2k = u 2k+1 , whence p 1 u 2k = p 1 u 2k+1 , a contradiction. Thus, we can assume that m > 2 and suppose that the states p 1 , p 2 , p 3 are distinct. For some element s ∈ S, we have (p 1 , p 2 )s = (p 2 , p 3 ). Hence

p 2 = p 1 s, p 3 = p 1 s 2 .
For any element u ∈ S and any pair (p i , p i+1 ) from M , we have either p i u = p i+1 u or (p i u, p i+1 u) ∈ M . Therefore, for any element u ∈ S, the sequence of states p 1 u, . . . , p m u either reduces to just one element repeated m times or forms a t-cycle of size m (because of the minimality of m).

The states p 1 , p 1 s, p 1 s 2 are distinct. Since S is an aperiodic finite semigroup, there exists some integer ℓ such that s ℓ = s ℓ+1 = s ℓ+2 . Therefore there exists an k ≤ ℓ such that p 1 s k = p 1 s k+1 = p 1 s k+2 the sequence p 1 s k , p 2 s k = p 1 s k+1 , p 3 s k = p 1 s k+2 ,. . . , p m s k has more than 1 but less than m distinct elements. This contradicts the conclusion of the previous paragraph applied to the element u = s k .

It is easy to see that if the quasi-order M is not antisymmetric that there exists a t-cycle for M . Hence M is a partial order. ✷

The Černý conjecture

Lemma 8 Let A be an aperiodic DFA with n states and strongly connected graph, M an almost minimal SCC. Let r be the number of ρ M -classes and let R be a ρ M -class. Then |Rs| = 1 for some word s ∈ Σ * of length ar most (nr + 1)(n -1)/2.

Proof: Suppose |R| > 1. Let M ax be the set of all maximal and M in the set of all minimal states from R with respect to the order ≻ M . Observe that there is no ambiguity here: since the order ≻ M is contained in the congruence ρ M , maximal (minimal) states of the ordered set (R, ≻ M ) are precisely those maximal (minimal) states of the automaton A that belong to R. Further, M ax ∩ M in = ∅ because the congruence ρ M is the equivalent closure of the order ≻ M whence for every state q ∈ R there must be a state p ∈ R such that either q ≻ M p or p ≻ M q. Without loss of generality, we may assume that |M ax| ≥ |M in|.

Then |M in| ≤ |R|/2 ≤ (n -r + 1)/2.
We need three properties of ordered sets of the form (Rs, ≻ M ) where s is a word. Let M ax s (M in s ) stand for the set of all maximal (respectively all minimal) states in (Rs, ≻ M ).

Claim 1. If |Rs| > 1, then M in s ∩ M ax s = ∅.
Proof: Take an arbitrary state p ′ ∈ M in s and let q ′ be any state in Rs \ {p ′ }. Consider some preimages p, q ∈ R of p ′ and respectively q ′ . Since R is a ρ M -class, there is a sequence of states q 0 , q 1 , . . . , q k ∈ R such that p = q 0 , q k = q, and for each i = 1, . . . , k either q i-1 M q i or q i M q i-1 . Let q ′ i = q i s ∈ Rs, i = 0, . . . , k. Since the order M is stable (Lemma 1), we conclude that there is a sequence of states q ′ 0 , q ′ 1 , . . . , q ′ k ∈ Rs such that p ′ = q ′ 0 , q ′ k = q ′ , and

for each i = 1, . . . , k either q ′ i-1 M q ′ i or q ′ i M q ′ i-1 . Since p ′ = q ′ ,
some of these inequalities must be strict. Let j be the least index such that q ′ j-1 = q ′ j . Then p ′ = q ′ 0 = . . . = q ′ j-1

whence either p ′ ≻ M q ′ j or q ′ j ≻ M p ′ . As the first inequality would contradict the assumption that p ′ is a minimal element of (Rs, ≻ M ), we conclude that the second inequality holds true whence p ′ is not a maximal element of (Rs, ≻ M ). Thus, no state in M in s can belong to M ax s . ✷ Claim 2. If s, t ∈ Σ * are two arbitrary words, then M in ts ⊆ M in t s.

Proof: Take an arbitrary state p ′ ∈ M in ts and consider its arbitrary preimage p ∈ Rt. There exists a state q ∈ M in t such that p M q. Since the order M is stable (Lemma 1), we then have p ′ = p s M q s = q ′ . The state q ′ belongs to the set Rts, and therefore, q ′ = p ′ because p ′ has been chosen to be a minimal element in this set. Thus, we have found a preimage for p ′ in M in t whence M in ts ⊆ M in t s. ✷ Claim 3. For any word t ∈ Σ * , there exists a word s ∈ Σ * of length at most n -1 such that either |Rst| = 1 or |M in ts | < |M in t |.

Proof: Now take arbitrary state q ∈ M in t . Since the graph Γ is strongly connected, there exists a word that maps q to an element of M ax. If s is a word of minimum length with this property then the path labelled s does not visit any state of A twice whence |s| ≤ n -1. Observe that since qs ∈ M ax, we also have qs ∈ M ax ts . Therefore either |Rst| = 1 or, by Claim 1 above, qs / ∈ M in ts . Since qs ∈ M in t s, we conclude from Claim 2 that M in ts ⊂ M in t s. Thus,

|M in ts | < |M in t s| ≤ |M in t |. ✷
Using Claim 3, we can easily complete the proof of the lemma. Indeed, applying it to the case when t is the empty word, we can find a word s 1 of length at most n -1 such that either |Rs 1 | = 1 or |M in s1 | < |M in|. In the latter case, applying Claim 3 again, we can find a word s 2 of length at most n -1 such that either |Rs Proof: All states of a DFA whose transition graph is strongly connected are sinks. Therefore the automaton is synchronizable (Lemma 6).

There exists at least one almost minimal SCC M in Γ 2 because the number of SCC's is finite and the set of SCC's is partially ordered under the attainability relation. Consider the congruence ρ M (Lemma 1) and the quotient Γ/ρ M .

It is clear that any synchronizing word of Γ synchronizes also Γ/ρ M and that Γ/ρ M is aperiodic and strongly connected. Therefore the graph Γ has a synchronizing word uv where u is a synchronizing word of Γ/ρ M and v is a synchronizing word of the preimage R of the singleton set (Γ/ρ M ) u. By Corollary 3, ρ M is not trivial, therefore r = |Γ/ρ M | < n and we can use induction assuming |u| ≤ (r -1)r/2. By Lemma 8, a word v of length at most (nr + 1)(n -1)/2 synchronizes R. Therefore |uv| ≤ r(r-1)

2 + (n-r+1)(n-1) 2 ≤ (r-1)(n-1) 2 + (n-r+1)(n-1) 2 ≤ n(n-1) 2 as required. ✷
Let us go to the general case.

Theorem 10 Let A be an aperiodic DFA with n states. Then the existence of a sink in A is equivalent to the existence of a synchronizing word of length at most n(n -1)/2.

Proof: It is clear that the existence of a synchronizing word implies the existence of a sink. For the converse, let us consider a DFA with at least one sink. By Lemma 6, the automaton is synchronizable. We may assume in view of Theorem 9 that the transition graph Γ of A is not strongly connected.

It is clear that the collection C of all sinks of Γ forms a SCC of Γ which is the least SCC with respect to the attainability order. Let r < n stand for the cardinality of C. Let Γ i (i = 1, 2, . . . , k) be all other SCC's of Γ. We may assume that Γ i are numbered so that i ≤ j whenever there is a path in Γ from Γ i to Γ j . Let r i be the cardinality of Γ i . It easily follows from [START_REF] Rystsov | Reset words for commutative and solvable automata[END_REF]Theorem 6.1] that there exists a word s i of length at most r i (r i + 1)/2 such that Γ i s i ∩ Γ i is empty. Then the product s 1 • • • s k of maps Γ into the SCC C. By Theorem 9, C has a synchronizing word s of length at most r(r -1)/2. Therefore the word s 1 • • • s k s synchronizes Γ and

|s 1 . . . s k s| ≤ k i=1 r i (r i + 1) 2 + r(r -1) 2 . ( 3
)
Using the equality k i=1 r i +r = n, it is easy to calculate that the right-hand side of the inequality 3 does not exceed (n -1)n/2. ✷

1 s 2 |Theorem 9

 29 = 1 or |M in s1s2 | < |M in s1 |, and so on. Clearly, the process will stop after at most |M in| steps yielding a word s = s 1 s 2 • • • s k (with k ≤ |M in| and |s i | ≤ n -1 for each i = 1, . . . , k) such that |Rs| = 1. Since |M in| ≤ (nr + 1)/2, we have |s| ≤ (nr + 1)(n -1)/2 as required.✷ If the transition graph Γ of an aperiodic DFA A with n states is strongly connected, then A has a synchronizing word of length at most (n -1)n/2.

Acknowledgments

I am very grateful to M. V. Volkov for helpful and detailed comments that proved to be highly useful in improving the presentation and style of the paper.

Corollary 11

The Černý conjecture holds for aperiodic automata.