Timothy Ng
email: ng@cs.queensu.ca

David Rappaport

Kai Salomaa
email: ksalomaa@cs.queensu.ca

State Complexity of Prefix Distance of Subregular Languages

The neighbourhood of a regular language of constant radius with respect to the prefix distance is always regular. We give upper bounds and matching lower bounds for the size of the minimal deterministic finite automaton (DFA) needed for the radius k prefix distance neighbourhood of an n state DFA that recognizes, respectively, a finite, a prefix-closed and a prefix-free language. For prefix-closed languages the lower bound automata are defined over a binary alphabet. For finite and prefix-free regular languages the lower bound constructions use an alphabet that depends on the size of the DFA and it is shown that the size of the alphabet is optimal.

Introduction

The neighbourhood of radius r of a language L consists of all strings that are within distance at most r from some string of L. A distance measure d is said to be regularity preserving if the neighbourhood of any regular language with respect to d is regular. Calude et al. [START_REF] Calude | Additive distances and quasi-distances between words[END_REF] have shown that additive distances are regularity preserving. Additivity requires, roughly speaking, that the distance is compatible with concatenation of words in a certain sense and best known examples of additive distances include the Levenshtein distance and the Hamming distance [START_REF] Calude | Additive distances and quasi-distances between words[END_REF][START_REF] Deza | Encyclopedia of Distances[END_REF].

The prefix distance of two words u and v is the sum of the lengths of the suffixes of u and v that begin after the longest common prefix of u and v. The suffix distance and the factor distance are defined analogously in terms of the longest common suffix (respectively, factor) of two words. It is known that the prefix, suffix and factor distance preserve regularity [START_REF] Choffrut | Distances between languages and reflexivity of relations[END_REF].

By the state complexity of a regularity preserving distance we mean the worst-case size of the minimal deterministic finite automaton (DFA) needed to recognize radius r neighbourhood of an n state DFA language (as a function of n and r). Tight bounds for the state complexity of prefix distance were recently obtained by the authors [START_REF] Ng | State Complexity of Prefix Distance[END_REF].

Worst-case state complexity bounds for general regular languages typically cannot be matched by finite languages, as first observed by Câmpeanu et al. [START_REF] Câmpeanu | State complexity of basic operations on finite languages[END_REF], and the same holds for other proper sub-families of the regular languages. Relations between different sub-regular language families have been investigated recently by Holzer and Truthe [START_REF] Holzer | On relations between some subregular language families[END_REF]. Bordihn, Holzer and Kutrib [START_REF] Bordihn | Determination of finite automata accepting subregular languages[END_REF] have studied the state complexity of determinization of automata for the different sub-regular language families and further recent work on the state complexity of sub-regular language families has been done by Holzer et al. [START_REF] Holzer | The Magic Number Problem for Subregular Language Families[END_REF][START_REF] Holzer | Nondeterministic state complexity of star-free fanguages[END_REF].

Here we study the state complexity of prefix distance for finite languages. Additionally, we concentrate on the classes of prefix-closed and prefix-free regular languages because their corresponding restricting properties can be viewed to be related to the definition of the prefix distance measure. We give tight state complexity bounds for the prefix distance of finite, prefix-closed and prefix-free regular languages. In the case of finite languages and prefix-free languages the lower bound construction uses an alphabet that depends linearly on the size of the DFA. We establish that the general upper bound cannot be matched by languages defined over an alphabet of smaller size.

Preliminaries

We briefly recall some definitions and notation used in the paper. For all unexplained notions on finite automata and regular languages the reader may consult the textbook by Shallit [START_REF] Shallit | A second course in formal languages and automata theory[END_REF] or the survey by Yu [START_REF] Yu | Regular languages[END_REF]. A survey of distances is given by Deza and Deza [START_REF] Deza | Encyclopedia of Distances[END_REF]. Recent surveys on descriptional complexity of regular languages include [START_REF] Gao | A review on state complexity of individual operations[END_REF][START_REF] Holzer | Descriptional and computational complexity of finite automata -A survey[END_REF][START_REF] Kutrib | Recent trends in descriptional complexity of formal languages[END_REF].

In the following Σ is always a finite alphabet, the set of strings over Σ is Σ * and ε is the empty string. The reversal of a string x ∈ Σ * is x R . The set of nonnegative integers is N 0 . The cardinality of a finite set S is denoted |S| and the powerset of S is 2 S . A string w ∈ Σ * is a substring or factor of x if there exist strings u, v ∈ Σ * such that x = uwv.

If u = ε, then w is a prefix of x. If v = ε, then w is a suffix of x. A nondeterministic finite automaton (NFA) is a 5-tuple A = (Q, Σ, δ, Q 0 , F ) where Q is a finite set of states, Σ is an alphabet, δ is a multi-valued transition function δ : Q × Σ → 2 Q , Q 0 ⊆ Q is a set of initial
states, and F ⊆ Q is a set of final states. We extend the transition function δ to a function Q×Σ * → 2 Q in the usual way. A string w ∈ Σ * is accepted by A if, for some q 0 ∈ Q 0 , δ(q 0 , w)∩F = ∅ and the language recognized by A consists of all strings accepted by A. An ε-NFA is an extension of an NFA where transitions can be labeled by the empty string ε [START_REF] Shallit | A second course in formal languages and automata theory[END_REF][START_REF] Yu | Regular languages[END_REF], i.e., δ is a function Q × (Σ ∪ {ε}) → 2 Q . It is known that every ε-NFA A has an equivalent NFA without ε-transitions and with the same number of states as A.

An NFA A = (Q, Σ, δ, Q 0 , F ) is a deterministic finite automaton (DFA) if |Q 0 | = 1 and
, for all q ∈ Q and a ∈ Σ, δ(q, a) either consists of one state or is undefined. Two states p and q of a DFA A are equivalent if δ(p, w) ∈ F if and only if δ(q, w) ∈ F for every string w ∈ Σ * . A DFA A is minimal if each state q ∈ Q is reachable from the initial state, a final state is reachable from each state q, and no two states are equivalent.

Note that our definition of a DFA allows some transitions to be undefined, that is, by a DFA we mean an incomplete DFA. It is well known that, for a regular language L, the sizes of the minimal incomplete and complete DFAs differ by at most one. The constructions used in this paper are more convenient to formulate using incomplete DFAs but our results would not change in any significant way if we were to require that all DFAs are complete. The (incomplete deterministic) state complexity of a regular language L, sc(L), is the size of the minimal DFA recognizing L.

We define pref(L) to be the language of all prefixes of words belonging to L,

pref(L) = {u ∈ Σ * | (∃v ∈ Σ * ) uv ∈ L}.
A language L is prefix-closed if L = pref(L). A language L is prefix-free if no word u ∈ L is a proper prefix of any other word in L. A DFA A is non-exiting if a final state of A has no outgoing transitions. The minimal DFAs recognizing a prefix-free language have always the following property.

Lemma 1 ([7]

). If A is minimal and L(A) is prefix-free, then A is non-exiting.

To conclude this section, we recall definitions of the distance measures used in the following. Generally, a function d :

Σ * × Σ * → [0, ∞) is a distance if it
satisfies for all x, y, z ∈ Σ * , the conditions d(x, y) = 0 if and only if x = y, d(x, y) = d(y, x), and d(x, z) ≤ d(x, y)+d(y, z). The neighbourhood of a language L of radius k with respect to a distance d is the set

E(L, d, k) = {w ∈ Σ * | (∃x ∈ L) d(w, x) ≤ k}.
Let x, y ∈ Σ * . The prefix distance of x and y counts the number of symbols which do not belong to the longest common prefix of x and y [START_REF] Choffrut | Distances between languages and reflexivity of relations[END_REF]. Formally, it is defined by

d p (x, y) = |x| + |y| -2 • max z∈Σ * {|z| | x, y ∈ zΣ * }.
The state complexity of prefix distance was established in [START_REF] Ng | State Complexity of Prefix Distance[END_REF].

Theorem 1 ([14]). For n > k ≥ 0, if sc(L) = n then sc(E(L, d p , k)) ≤ n • (k + 1) - k(k + 1) 2
and this bound can be reached in the worst case.

To conclude this section we recall from [START_REF] Ng | State Complexity of Prefix Distance[END_REF] the construction of a DFA that recognizes the prefix-distance neighbourhood of a regular language.

Let A = (Q, Σ, δ, q 0 , F ) be a DFA and ϕ A : Q → N 0 be a function defined by

ϕ A (q) = min w∈Σ * {|w| | δ(q, w) ∈ F }
The function ϕ A (q) gives the length of the shortest path from a state q to the closest reachable final state. Note that if q ∈ F , then ϕ A (q) = 0. We construct a DFA A = (Q , Σ, δ , q 0 , F ) for the neighbourhood E(L(A), d p , k), k ∈ N, as follows. We define the state set

Q = ((Q -F ) × {1, . . . , k + 1}) ∪ F ∪ {p 1 , . . . , p k }. (1)
The initial state q 0 is defined by

q 0 =      q 0 , if q 0 ∈ F ; (q 0 , ϕ A (q 0 )) if q 0 ∈ F and ϕ A (q 0 ) ≤ k; (q 0 , k + 1) if q 0 ∈ F and ϕ A (q 0 ) > k.
The set of final states is given by

F = ((Q -F ) × {1, . . . , k}) ∪ F ∪ {p 1 , . . . , p k }. Let q i,a = δ(i, a) for i ∈ Q and a ∈ Σ, if δ(i, a) is defined.
Then for all a ∈ Σ, the transition function δ is defined for states i ∈ F by

δ (i, a) =      (q i,a , 1), if q i,a ∈ Q -F ; q i,a , if q i,a ∈ F ; p 1 , if δ(i, a) is undefined. For states (i, j) ∈ Q -F × {1, . . . , k + 1}, δ is defined δ ((i, j), a) =          q i,a , if q i,a ∈ F ; (q i,a , min{j + 1, ϕ A (q i,a )}), if ϕ A (q i,a ) or j + 1 ≤ k; (q i,a , k + 1), if ϕ A (q i,a ) and j + 1 > k; p j+1 , if δ(i, a) is undefined.
Finally, we define δ for states p for = 1, . . . , k -1 by δ (p , a) = p +1 .

The following Proposition 1 follows from the proof of Proposition 2 of [START_REF] Ng | State Complexity of Prefix Distance[END_REF]. Note that Proposition 2 of [START_REF] Ng | State Complexity of Prefix Distance[END_REF] establishes a stronger claim and the statement of the below proposition includes only the parts that we need in the later sections.

Proposition 1 ([14]). (a)

The DFA A recognizes the neighbourhood E(L(A), d p , k). (b) The elements of the set S ur = {(q, j) | q ∈ Q -F, 1 ≤ j ≤ k + 1, j > ϕ A (q)} are all unreachable as states of the DFA A .

Neighbourhoods of Finite Languages

We first consider the state complexity of neighbourhoods of finite languages with respect to the prefix distance.

Proposition 2. Let L be a finite language recognized by a minimal DFA A = (Q, Σ, δ, q 0 , F ) with n states. Then

sc(E(L, d p , k)) ≤ (n -2) • (k + 1) -k 2 + 2.
Proof. We know that the neighbourhood of L of radius k with respect to the prefix distance is recognized by a DFA A = (Q , Σ, δ , q 0 .F ) obtained from A as in Proposition 1 where, furthermore, all elements of the set S ur are unreachable. We show that there are more unreachable states in the case of finite languages.

Since A is acyclic, the number and length of words that reach each state q ∈ Q is bounded. For q ∈ Q, let w q denote the longest word that reaches q from the initial state q 0 without passing through a final state. Then for all states q with |w q | ≤ k, the states (q, j) ∈ Q with j > |w q | are unreachable as states of A (where the set of states of A is as in [START_REF] Bordihn | Determination of finite automata accepting subregular languages[END_REF]. That is, all states in the set

R ur = {(q, j) | q ∈ Q -F, 1 ≤ j ≤ k + 1, j > |w q |} are unreachable in A . By Proposition 1 (b) all elements of the set S ur = {(q, j) | q ∈ Q -F, 1 ≤ j ≤ k + 1, j > ϕ A (q)}
are also unreachable in A . We note that increasing the number of final states of A by one decreases the cardinality of Q by k and decreases the cardinality of S ur and R ur by at most k. However, we observe that A must have at least two final states to reach the bound. The last state of A, with no outgoing transitions, must be a final state since, otherwise, there are useless states. But this cannot be the only final state, since otherwise, for every state q ∈ Q with ϕ A (q) > k, only (q, k + 1) is reachable. Thus, the initial state q 0 must also be a final state.

As in [START_REF] Ng | State Complexity of Prefix Distance[END_REF], we note that the cardinality of S ur is minimized when exactly one non-final state has a shortest path of length i that reaches q f . From the above it then follows that reaching the upper bound requires exactly two final states, one of which must be the initial state and the other which must have no outgoing transitions. Since A is acyclic, the initial state cannot have any incoming transitions, so the states in S ur consist of those that can reach the noninitial final state, giving k(k+1) 2 unreachable states. Similarly, the cardinality of R ur is minimized when exactly one non-final state has a longest word of length i which reaches it from q 0 , giving k(k+1) 2 unreachable states. Thus, the number of states of the minimal DFA for E(L, d p , k) is upper bounded by

(n -2)(k + 1) + 2 + k -2 • k(k + 1) 2 = (n -2)(k + 1) -k 2 + 2.
Next we give a lower bound construction that matches the upper bound of Proposition 2.

Lemma 2. There exists a finite language recognized by a DFA with n states such that

E(L(A), d p , k) requires at least (n -2)(k + 1) -k 2 + 2 states. Proof. Let A n = (Q n , Σ n , δ n , q 0 , F n ) where Q n = {0, . . . , n-1}, Σ n = {a 1 , . . . , a n-3 }, q 0 = 0, F n = {0, n -1},
and the transition function is defined by

-δ n (0, a i ) = i for 1 < j ≤ n -3, -δ n (i, a i+1 ) = i + 1 for 0 ≤ i < n -3, -δ n (i, a 1 ) = i + 1 for i = n -3, n -2.
The DFA A n is depicted in Figure 1.

0 start 1 2 • • • n -3 n -2 n -1 a1 a2 an-3 a2 a3 an-3 a1 a1
Fig. 1. The DFA An.

Let A n = (Q n , Σ n , δ n , q 0 , F n ) be the DFA constructed from A n as in Proposition 1. First, we show that (n -2)(k + 1) -k 2 + 2 states are reachable. States of the form p i with 1 ≤ i ≤ k are reachable from states 0 ≤ i ≤ k on symbols a j with j = i + 1. For states of the form (i, j) ∈ (Q n -F n ) × {1, . . . , k + 1}, with ϕ An (i) > k and j ≤ i, each (i, j) is reachable on the word a i-j a i-j+1 • • • a i . However, states (i, j) with j > ϕ An (i) are unreachable by definition of A n and states (i, j) with i < j ≤ k are unreachable. Thus the number of unreachable states in

(Q n -F n ) × {1, . . . , k + 1} is n-1 i=n-k |{i} × {ϕ An (i) + 1, . . . , k + 1}| + k i=1 |{i + 1, . . . , k + 1}| = 2 • k i=1 |{i = 1, . . . , k + 1}| = 2 • k i=1 i = 2 • k(k + 1) 2 .
Thus the number of reachable states is

(n -2)(k + 1) -2 + k -2 • k(k + 1) 2 = (n -2)(k + 1) -k 2 + 2.
Now, we show that all reachable states are pairwise inequivalent.

-For states of the form p i and p j , i < j, the word a k-i 1 takes the machine from state p i to p k and is accepted. However, from state p j , the word a k-i 1 reaches state p k on the prefix a k-j 1 with no further transitions to read a j-i 1 and thus, the word is not accepted.

-For states of the form (i, j) and p with < k, we consider the word z = w i a k

2 with w i = a n-i+1 a n-i+2 • • • a n-3 a 1 a 1 .
The prefix w i takes the machine from state (i, j) to state n -1 and on the rest of the word a k 2 , the machine moves from n -1 to p k and is accepted. However, from state p , the computation on z reaches p k before all of z is read, since |z| = n -i + k > k -and it is rejected.

-For states of the form (i, j) and (i , j ) with i < i the states can be distinguished by z = w i a k 2 as above. For i = i and j < j , let z = a i a k-j

1

. From (i, j), the machine reads a i and is taken to p j , while from (i, j ), the machine is taken to p j . From above, p j and p j are distinguishable by a k-j 1 .

Thus, we have shown that there are (n -2)(k + 1) -k 2 + 2 reachable states and that all reachable states are pairwise inequivalent.

Proposition 2 and Lemma 2 now yield a tight state complexity bound for the prefix distance neighbourhoods of regular languages.

Theorem 2. Let L be a finite language. For n > 2k ≥ 0, if sc(L) = n, then

sc(E(L, d p , k)) ≤ (n -2) • (k + 1) -k 2 + 2,
and this bound can be reached in the worst case.

The lower bound construction of Lemma 2 uses, for a DFA with n states, an alphabet of cardinality n -3. To conclude this section we show that the construction is optimal in the sense that the upper bound of Theorem 2 cannot be reached with an alphabet of cardinality less than n -3. Proposition 3. Let A be a DFA recognizing a finite language with n states. If the state complexity of E(L(A), d p , k) equals (n -2)(k + 1) -k 2 + 2, then the alphabet of A needs at least n -3 letters.

Proof. Let A = (Q, Σ, δ, q 0 , F ) with |Q| = n. Let A = (Q , Σ, δ , q 0 F ) be the DFA recognizing E(L(A), d p , k) constructed in Proposition 1. Recall from the proof of Proposition 2 that in order for A to have the maximal number of states (n -2)(k + 1) -k 2 + 2, a necessary condition is that F = {q 0 , q f } and that there can be only one state q 1 with ϕ A (q 1 ) = 1. Now for all q ∈ Q -{q 0 , q f , q 1 }, ϕ A (q) ≥ 2. By definition of the transition function δ , if ϕ A (q) ≥ 2, the state (q, 1) can only be reached by a direct transition from a final state. Since q f does not have any outgoing transitions, q 0 must have n -3 outgoing transitions-one for each state q.

Furthermore, since A contains a final state q f with no outgoing transitions, no additional symbols are required to reach p 1 , as it can be reached from q f via a direct transition on any symbol.

Since A is a DFA and q 0 has at least n-3 outgoing transitions, the cardinality of the alphabet must be at least n -3.

Neighbourhoods of Prefix-Closed and Prefix-Free Languages

Next, we consider the state complexity of neighbourhoods of prefix-closed and prefix-free regular languages with respect to the prefix distance.

Theorem 3. Let L be a prefix-closed regular language recognized by an n-state DFA A. Then there is a DFA A that recognizes the neighbourhood E(L, d p , k) with at most n + k states and this bound is reachable.

Proof. Since L is prefix-closed, every state of A must be an accepting state [START_REF] Kao | On NFAs where all states are final, initial, or both[END_REF].

If A has n states, this means that the DFA A constructed in Proposition 1 for the radius k neighbourhood has n + k states.

We now define a prefix-closed regular language L n such that a DFA recognizing E(L n , d p , k) requires at least n + k states. Let L n = {a i | 0 ≤ i ≤ n}. Then we define A n = (Q n , {a, b}, δ n , q 0 , F n ) where Q n = F n = {0, . . . , n -1}, q 0 = 0, and the transition function δ n is defined by δ n (i, a) = i + 1 for 0 ≤ i ≤ n -1.

Then we define the DFA recognizing

E(L n , d p , k) by A = (Q n , {a, b}, δ n , q 0 , F n ) where Q n = F n = Q n ∪ {p 1 , . .

. , p k } and the transition function defined by

-δ n (i, a) = i + 1 for 0 ≤ i < n -1, -δ n (n -1, a) = p 1 , -δ n (i, b) = p 1 for 0 ≤ i < n -1, -δ n (p i , a) = δ n (p i , b) = p i+1 for 1 ≤ i < k.
Every state i, 0 ≤ i ≤ n -1, is reachable on the word a i and every state p i , 1 ≤ i ≤ k is reachable on the word b i . The states 0 ≤ i, i ≤ n-1 are distinguished by the word b k-i and the states p i , p i , 1 ≤ i, i ≤ k are also distinguished by the word b k-i . The states i, 0 ≤ i ≤ n -1 and p j , 1 ≤ j ≤ k are distinguished by the word a n-j b k . Thus, there are n + k reachable states and they are all pairwise distinguishable. Proposition 4. Let L be a prefix-free regular language recognized by a minimal n-state DFA A = (Q, Σ, δ, q 0 , F ). Then there is a DFA B with at most (n -

1)k + 2 -k(k-1)

2

states that recognizes the neighbourhood E(L, d p , k).

Proof. Let A = (Q , Σ, δ, q 0 , F ) be the DFA constructed for the neighbourhood E(L, d p , k) as in Proposition 1. Since L is prefix-free, A must be non-exiting. That is, A has a single final state with no outgoing transitions. This property creates additional unreachable states in the DFA A for E(L, d p , k).

For all non-final states q ∈ Q -F , the state (q, 1) is reachable only if either ϕ A (q) = 1 or there is a transition from a final state to q. However, since A is non-exiting, no final states may have any outgoing transitions, so the only states q where (q, 1) is reachable are those with ϕ A (q) = 1. However, for all such states q, the states (q, i) with 2 ≤ i ≤ k + 1 are unreachable. Thus, to reach the upper bound on the number of states, the number of states q with ϕ A (q) = 1 must be minimized if k ≥ 2. If k = 1, then for each state q ∈ Q -F , either (q, 1) is reachable or (q, k + 1) is reachable, so the number of states with ϕ A (q) = 1 need not be minimized.

By Proposition 1 (b) elements of the set S ur = {(q, j)

| q ∈ Q -F, 2 ≤ j ≤ k + 1, j > ϕ A (q)}
are unreachable as states of A (even without assuming that L(A) is prefix-free. Let q f be the sole final state of A. The set S ur is minimized when exactly one non-final state q i in the DFA A for each 1 ≤ i ≤ k has a shortest path of length i that reaches q f . In this case, we have

|S ur | = k(k-1) 2 .
Thus, in order to maximize the number of reachable states of A , the DFA A has a single final state and a single state q 1 with ϕ

A (q 1 ) = 1 if k ≥ 2, giving us at most (n -2)k + k + 2 -k(k-1) 2 = (n -1)k + 2 -k(k-1) 2 states of A which are reachable.
Next we present a lower bound construction that matches the bound of Proposition 4. Lemma 3. There exists a DFA A with n states recognizing a prefix-free regular language such that a DFA recognizing the neighbourhood E(L(A), d p , k) requires at least (n -1)k + 2 -k(k-1) 2 states.

Proof. We define a DFA A n = (Q n , Σ n , δ n , q 0 , F ) by choosing

Q n = {0, . . . , n -1}, Σ n = {a 1 , .
. . , a n-3 , b}, q 0 = 0, F = {n -1}, and the transition function δ n is given by We transform A n into the DFA A n = (Q n , Σ n , δ n , q 0 , F ) via the construction from Proposition 1. To determine the reachable states of Q n , we first note that the state (0, 1) is reachable as it is the initial state. Note that the initial state is (0, 1) since ϕ An (0) = 1. The final state n -1 is reachable on the word b. Now consider states p 1 , . . . , p k . The state p is reachable on the word b +1 by first reading b to reach the final state and b to reach the state p . Now consider states of the form (i, j) ∈ (Q n -{0, n -1}) × {2, . . . , k + 1}. Recall that states (i, 1) are unreachable for any state i ∈ Q n with ϕ An > 1. Then for states i ∈ Q n with ϕ An > k and each 2 ≤ j ≤ k + 1, we can reach state (i, j) from (0, 1) via the word a j-1 i . For states i ∈ Q n with ϕ An ≤ k, we can reach state (i, j) via the word a j-1 i for j = 2, . . . , ϕ An (i) and states (i, j) with j > ϕ An (i) are unreachable by definition of A n .

-δ n (0, a i ) = i for i = 1, . . . , n -3, -δ n (i, a i ) = i for i = 1, . . . , n -3, -δ n (i, a i+1 ) = i + 1 for i = 1, . . . , n -4, -δ n (n -3, b) = n -2, δ n (n -2, b) = 0, δ n (0, b) = n -1. 0 start 1 2 • • • n -3 n -2 n -1 . . .
Finally, we can reach state (n -2, 2) via the word a n-3 b and states (n -2, j) are unreachable for j > 2 since ϕ An (n -2) = 2. Thus the number of unreachable states in

(Q n -{0, n -1}) × {2, . . . , k + 1} is n-2 i=n-k |{i} × {ϕ An (i) + 1, . . . , k + 1}| = k i=1 |{i + 1, . . . , k + 1}| = k i=1 i = k(k -1) 2 .
Thus, the number of reachable states is

(n -2) • k + 2 - k(k -1) 2 + k = (n -1) • k + 2 - k(k -1) 2 .
Now, we show that all reachable states are pairwise inequivalent. First, note that as a final state of A, n-1 is not equivalent to a state of the form (i, j) in A . Next, we distinguish states of the form (i, j) from states of the form p . For each 1 ≤ i ≤ n -3, reading the word a k i from state (i, j) takes the machine to state (i, min{ϕ A (i), k + 1}). Then subsequently reading a i+1 a i+2 • • • a n-3 bbb takes the machine to the final state n -1. However, for every state p , reading a k i forces the machine beyond state p k , after which there are no transitions defined. The state (n -2, 2) is distinguished from all p by the word b 2+k , (0, 1) by b 1+k , and n -1 by b k .

Next, without loss of generality, let < and consider states p and p . Choose z = b k-. The string z takes state p to the state p k , where it is accepted. However, the computation on string z from state p is undefined since +k-> k.

Finally, we consider states of the form (i, j). Let i < i and consider states (i, j) and (i , j ). Let z = a i+1 a i+2 • • • a n-3 bbbb k . From state (i, j), the word z goes to state n -1 on a i+1 • • • a n-3 bbb. Then by reading b k from state n -1, we reach state p k , an accepting state. However, when reading z from state (i , j ), we immediately reach state p j +1 on a i+1 , since the transition on a i+1 is defined only for states (0, 1) and (i, j). Since the rest of the word z is of length greater than k, reading it takes us to state p k with no further defined transitions for the rest of the word.

Next, consider the state (i, j) and (i, j ), where j < j . First, consider the case when ϕ An (i) > k. Then let z = a k-j i . Reading z from (i, j) takes us to state (i, k), which is a final state. However, from (i, j ), reading z brings us to state (i, k + 1) and so the computation is rejected. Now, consider the case when ϕ An (i) ≤ k. Let z = bb k-j-1 . From state (i, j), reading b takes the machine to state p j+1 and reading b k-j-1 puts the machine in the accepting state p k . However, reading z from (i, j ) takes us to state p k with b j -j still unread since j + k -j -1 > k and thus, with no further transitions available, the computation is rejected.

Thus, we have shown that there are (n -1)

• k + 2 -k(k-1)
2 reachable states and that all reachable states are pairwise inequivalent.

Combining Proposition 4 and Lemma 3 we have: Theorem 4. Let L be a prefix-free regular language. For n

> k ≥ 0, if sc(L) = n, then sc(E(L, d p , k)) ≤ (n -1) • k + 2 - k(k -1) 2 ,
and this bound can be reached in the worst case.

The construction of Lemma 3 that establishes the lower bound for Theorem 4 uses an alphabet of size n -2, where n is the number of states of the DFA. The below result establishes that the size of the alphabet cannot be reduced. Proposition 5. Let A be a DFA recognizing a prefix-free regular language with n states. If the state complexity of

E(L(A), d p , k) equals (n -1)k + 2 -k(k-1) 2 , then the alphabet of A needs at least n -2 letters. Proof. Let A = (Q, Σ, δ, q 0 , F ) with |Q| = n. Let A = (Q , Σ, δ , q 0 F ) be the DFA recognizing E(L(A), d p , k) constructed in Proposition 1.
Recall that as an automaton recognizing a prefix-free regular language A must be non-exiting. That is, A has a single final state q f and it cannot have any outgoing transitions. Recall also from the proof of Proposition 4 that in order for A to have the maximal number of states (n -1)k + 2 -k(k-1)

2

, a necessary condition is that there can be only one state q 1 with ϕ A (q 1 ) = 1 and one state q 2 with ϕ A (q 2 ) = 2. Now for all q ∈ Q -{q f , q 1 , q 2 }, ϕ A (q) ≥ 3. Recall that since the sole final state q f has no outgoing transitions, states (q, 1) are reachable only if ϕ A (q) = 1. Then by definition of the transition function δ , if ϕ A (q) ≥ 3, the state (q, 2) can only be reached by a direct transition from a state q with ϕ A (q) = 1. Thus, q 1 must have n -2 outgoing transitions-one for each state q with ϕ A (q) ≥ 3 and one additional transition to the final state q f . Note that q 2 requires no direct transition from q 1 since ϕ A (q 2 ) = 2 and thus (q 2 , 2) is the only reachable state of the form (q 2 , j).

Furthermore, since A contains a final state q f with no outgoing transitions, no additional symbols are required to reach p 1 , as it can be reached from q f via a direct transition on any symbol.

Since A is a DFA and q 1 has at least n-2 outgoing transitions, the cardinality of the alphabet must be at least n -2.

Conclusion

We have given tight state complexity bounds for the prefix-distance neighbourhood of, respectively, finite, prefix-closed, and prefix-free languages. As can, perhaps, be expected the bound for prefix-closed languages is relatively easier to obtain and the matching lower bound construction uses a binary alphabet. The upper bound constructions for the finite and the prefix-free languages are more involved and the lower bound constructions use a variable size alphabet. Furthermore, we have shown that, in both cases, the alphabet size is optimal.

Since the reversal of a DFA is not, in general, deterministic, the state complexity bounds for suffix-distance (or factor-distance) neighbourhoods differ significantly from the corresponding bounds for prefix-distance neighbourhoods. Tight lower bounds are not known for suffix-distance neighbourhoods of general regular languages [START_REF] Ng | State Complexity of Prefix Distance[END_REF] or for various sub-regular language families. Such questions can be a topic for further research.

Fig. 2 .

 2 Fig. 2. The DFA An.


E A Bondar
email: bondareug@gmail.com

M V Volkov

Completely Reachable Automata ⋆

Keywords: Deterministic finite automaton, Complete reachability, Transition monoid, Syntactic complexity, PSPACE-completeness 1

We present a few results and several open problems concerning complete deterministic finite automata in which every non-empty subset of the state set occurs as the image of the whole state set under the action of a suitable input word.

Whenever we deal with a fixed DFA, we simplify our notation by suppressing the sign of the transition function; this means that we may introduce the DFA as the pair Q, Σ rather than the triple Q, Σ, δ and may write q . w for δ(q, w) and P . w for δ(P, w).

Given a DFA A = Q, Σ , we say that a non-empty subset P ⊆ Q is reachable in A if P = Q . w for some word w ∈ Σ * . A DFA is called completely reachable if every non-empty subset of its state set is reachable.

Let us start with an example that served as a first spark which ignited our interest in completely reachable automata. A DFA A = Q, Σ is called synchronizing if it has a reachable singleton, that is, Q . w is a singleton for some word w ∈ Σ * . Any such word w is said to be a reset word for the DFA. The minimum length of reset words for A is called the reset threshold of A . In 1964 Černý [START_REF] Černý | Poznámka k homogénnym eksperimentom s konečnými automatami. Matematicko-fyzikalny Časopis Slovensk[END_REF] constructed for each n > 1 a synchronizing automaton C n with n states, 2 input letters, and reset threshold (n -1) 2 . Recall the definition of C n . If we denote the states of C n by 1, 2, . . . , n and the input letters by a and b, the actions of the letters are as follows:

i . a := i if i < n, 1 if i = n; i . b := i + 1 if i < n, 1 if i = n.
The automaton C n is shown in Fig. 1. The automata in the Černý series are well-known in the connection with the famous Černý conjecture about the maximum reset threshold for synchronizing automata with n states, see [START_REF] Volkov | Synchronizing automata and the Černý conjecture[END_REF]. The automata C n provide the lower bound (n -1) 2 for this maximum, and the conjecture claims that these automata represent the worst possible case since it has been conjectured that every synchronizing automaton with n states can be reset by a word of length (n -1) 2 . The automata C n also have other interesting properties, including the one registered here:

Example 1. Each automaton C n , n > 1, is completely reachable.

The result of Example 1 was first observed by Maslennikova [15, Proposition 2], see also [START_REF] Maslennikova | Reset complexity of ideal languages[END_REF], in the course of her study of the so-called reset complexity of regular ideal languages. Later, Don [9, Theorem 1] found a sufficient condition for complete reachability that applies to the automata C n . In Section 2 we present another sufficient condition that both simplifies and generalizes Don's one. We provide an example showing that our condition is not necessary but we conjecture that it may be necessary for a stronger version of complete reachability.

In Section 3 we discuss the problem of recognizing completely reachable automata. We show PSPACE-completeness of the following decision problem: given a DFA A = Q, Σ and a subset P ⊆ Q, decide whether or not P is reachable in A . We also outline a polynomial algorithm that recognizes completely reachable automata with 2 input letters modulo the conjecture from Section 2.

Given a DFA A = Q, Σ , its transition monoid M (A ) is the monoid of all transformations of the set Q induced by the words in Σ * . By the syntactic complexity of A we mean the size of M (A ). Clearly, the syntactic complexity of a completely reachable automaton A with n states cannot be less than 2 n -1 since, for each non-empty subset P of the state set, the transition monoid of A must contain a transformation whose image is P . In Section 4 we address the question of the existence and classification of minimal completely reachable automata, i.e., completely reachable automata with minimum possible syntactic complexity. This question has been recently investigated in the realm of transformation monoids by the first author [START_REF] Bondar | L-cross-sections of the finite symmetric semigroup[END_REF][START_REF] Bondar | Classification of L-cross-sections of Tn[END_REF]; here we translate her results into the language of automata theory and augment them by determining the input alphabet size of minimal completely reachable automata.

The present paper is in fact a work-in-progress report, and therefore, each of Sections 2-4 includes some open questions. Several additional open questions form Section 5; they mostly deal with synchronization properties of completely reachable automata.

We assume the reader's acquaintance with some basic concepts of graph theory, monoid theory, and computational complexity.

If Q is a finite set, we denote by T (Q) the full transformation monoid on Q, i.e., the monoid consisting of all transformations ϕ : Q → Q. For ϕ ∈ T (Q), its defect is defined as the size of the set Q \ Qϕ. Observe that the defect of a product of transformations is greater than or equal to the defect of any of the factors and is equal to the defect of a factor whenever the other factors are permutations of Q. In particular, if a product of transformations has defect 1, then one of the factors must have defect 1.

Let A = Q, Σ be a DFA. The defect of a word w ∈ Σ * with respect to A is the defect of transformation induced by w. Consider a word w of defect 1. For such a word, the set Q\Q . w consists of a unique state, which is called the excluded state for w and is denoted by excl(w). Further, the set Q . w contains a unique state p such that p = q 1 . w = q 2 . w for some q 1 = q 2 ; this state p is called the duplicate state for w and is denoted by dupl(w). Let D 1 (A ) stand for the set of all words of defect 1 with respect to A , and let Γ 1 (A ) denote the directed graph having Q as the vertex set and the set

E 1 := {(excl(w), dupl(w)) | w ∈ D 1 (A )}
as the edge set. Since we consider only directed graphs in this paper, we call them just graphs in the sequel. Recall that a graph is strongly connected if for every pair of its vertices, there exists a directed path from the first vertex to the second.

Theorem 1. If a DFA A = Q, Σ is such that the graph Γ 1 (A ) is strongly connected, then A is completely reachable.
Proof. Take an arbitrary non-empty subset P ⊆ Q. We prove that P is reachable in A by induction on k := |Q \ P |. If k = 0, then P = Q and nothing is to prove as Q is reachable via the empty word. Now let k > 0 so that P is a proper subset of Q. Since the graph Γ 1 (A ) is strongly connected, there exists an edge (q, p) ∈ E 1 that connects Q \ P and P in the sense that q ∈ Q \ P while p ∈ P . By the definition of E 1 , there exists a word w of defect 1 with respect to A for which q is the excluded state and p is the duplicate state. By the definition of the duplicate state, p = q 1 . w = q 2 . w for some q 1 = q 2 , and since the excluded state q for w does not belong to P , for each state r ∈ P \{p}, there exists a unique state r ′ ∈ Q such that r = r ′ . w. Now letting R := {q 1 , q 2 } ∪ r ′ | r ∈ P \ {p} , we conclude that P = R . w and |R| = |P | + 1. Then |Q \ R| = k -1, and the induction assumption applies to the subset R whence R = Q . v for some word v ∈ Σ * . Then P = Q . vw so that P is reachable as required.

Don [START_REF] Don | The Černý conjecture and 1-contracting automata[END_REF] has formulated a sufficient condition for complete reachability in the terms of what he called a state map. Consider a DFA A = Q, Σ with n states in which every subset of size n -1 is reachable. Let W be a set of n words of defect 1 with respect to A such that for every subset P ⊂ Q with |P | = n -1 there is a unique word w ∈ W with P = Q . w. (Such a set is termed a 1-contracting collection in [START_REF] Don | The Černý conjecture and 1-contracting automata[END_REF]). The state map σ W : Q → Q induced by W is defined by qσ W := dupl(w) for w ∈ W such that q = excl(w).

The following is one of the main results in [START_REF] Don | The Černý conjecture and 1-contracting automata[END_REF]: Theorem 2. A DFA A is completely reachable if it admits a 1-contracting collection such that the induced state map is a cyclic permutation of the state set of A .

Even though Theorem 2 is stated in different terms, it is easily seen to constitute a special case of Theorem 1. Indeed, if W is a 1-contracting collection and σ W is the corresponding state map, then each pair (q, qσ W ) can be treated as an edge in E 1 . Therefore, if σ W is a cyclic permutation of Q, then the set of edges {(q, qσ W ) | q ∈ Q} forms a directed Hamiltonian cycle in the graph Γ 1 (A ) whence the latter is strongly connected.

We believe that Theorem 1 may have strongly wider application range than Theorem 2 even though at the moment we do not have any example confirming this conjecture. If the conditions of the two theorems were equivalent, every strongly connected graph of the form Γ 1 (A ) would possess a directed Hamiltonian cycle, and this does not seem to be likely. Now we demonstrate that the condition of Theorem 1 is not necessary.

Example 2. Consider the DFA E 3 with the state set {1, 2, 3} and the input letters a [START_REF] Adler | Equivalence of topological Markov shifts[END_REF] , a [START_REF] Ananichev | Primitive digraphs with large exponents and slowly synchronizing automata[END_REF] , a [START_REF] Bondar | L-cross-sections of the finite symmetric semigroup[END_REF] , a [START_REF] Adler | Equivalence of topological Markov shifts[END_REF][START_REF] Ananichev | Primitive digraphs with large exponents and slowly synchronizing automata[END_REF] that act as follows:

i . a [1] := 2 if i = 1, 2, 3 if i = 3; i . a [2] := 1 if i = 1, 2, 3 if i = 3; i . a [3] := 1 if i = 1, 2, 2 if i = 3; i . a [1,2] := 3 for all i = 1, 2, 3.
The automaton E 3 is shown in Fig. 2 on the left. The graph Γ 1 (E 3 ) is shown in Fig. 2 on the right; it is not strongly connected. However, it can be checked by a straightforward computation that the automaton E 3 is completely reachable.

1 2 3 a [1]
a [START_REF] Ananichev | Primitive digraphs with large exponents and slowly synchronizing automata[END_REF] , a [START_REF] Bondar | L-cross-sections of the finite symmetric semigroup[END_REF] a [START_REF] Bondar | L-cross-sections of the finite symmetric semigroup[END_REF] a The reason of why the converse of Theorem 1 fails becomes obvious if one analyzes the above proof. In fact, we have proved more than we have formulated, namely, our proof shows that if a DFA A is such that the graph Γ 1 (A ) is strongly connected, then every proper non-empty subset of the state set of A is reachable via a product of words of defect 1. Of course, this stronger property has no reason to hold in an arbitrary completely reachable automaton. For instance, in the automaton E 3 of Example 2 the singleton {3} is not an image of any product of words of defect 1. On the other hand, for the stronger property italicized above, the condition of Theorem 1 may be not only sufficient but also necessary. We formulate this guess as a conjecture.

[1,2] a [1,2] a [1] a [2] , a [3] a [2] , a [1] , a [1,2]
Conjecture 1. If for every proper non-empty subset P of the state set of a DFA A there is a product w of words of defect 1 with respect to A such that P = Q . w, the graph Γ 1 (A ) is strongly connected.

One can formulate further sufficient conditions for complete reachability in terms of strong connectivity of certain hypergraphs related to words of defect 2.

Complexity of Deciding Reachability

Given a DFA, one can easily decide whether or not it is completely reachable considering its powerset automaton: a DFA A = Q, Σ is completely reachable if and only if Q is connected with every its non-empty subset by a directed path in the powerset automaton P(A ), and the latter property can be recognized by breadth-first search on P(A ) starting at Q. This algorithm is however exponential with respect to the size of A , and it is natural to ask whether or not complete reachability can be decided in polynomial time. First, consider the following decision problem:

Reachable Subset: Given a DFA A = Q, Σ, δ and a non-empty subset P ⊆ Q, is it true that P is reachable in A ?

Theorem 3. The problem Reachable Subset is PSPACE-complete.
Proof. The fact that Reachable Subset is in the class PSPACE is easy and known, see, e.g., [5, Lemma 6, item 1].

To prove PSPACE-hardness of Reachable Subset, we reduce to it in logarithmic space the well-known PSPACE-complete problem FAI (Finite Automata Intersection, see [START_REF] Kozen | Lower bounds for natural proof systems[END_REF]). Recall that an instance of FAI consists of k DFAs A j = Q j , Σ, δ j , j = 1, . . . , k, with disjoint state sets and a common input alphabet. In each DFA A j an initial state s j ∈ Q j and a final state t j ∈ Q j are specified; a word w ∈ Σ * is said to be accepted by A j if δ j (s j , w) = t j . The question of FAI asks whether or not there exists a word w ∈ Σ * which is simultaneously accepted by all automata A 1 , . . . , A k . Now, given an instance of FAI as above, we construct the following instance (A , P ) of Reachable Subset. The state set of the DFA A is

Q := k j=1 Q j ; the input alphabet of A is Σ with one extra letter ρ added. The transition function δ : Q × (Σ ∪ {ρ}) → Q is defined by the rule δ(q, a) := δ j (q, a) if a ∈ Σ and q ∈ Q j , s j if a = ρ and q ∈ Q j . (1)
Expressing this rule less formally, it says that, given a state q ∈ Q, one first should find the index j ∈ {1, . . . , k} such that q belongs to Q j ; then every letter a ∈ Σ acts on q in the same way as it does in the automaton A j while the added letter ρ sends q to the initial state s j of A j (so ρ artificially 'initializes' each A j ). Observe that each set Q j is closed under the action of each letter in Σ ∪ {ρ}. Finally, we set P := {t 1 , . . . , t k }, that is, P consists of the final states of A 1 , . . . , A k . We claim that the subset P is reachable in A if and only if there exists a word w ∈ Σ * which is simultaneously accepted by all automata A 1 , . . . , A k . Indeed, if such a word w exists, then δ(Q, ρw) = P since we have δ(Q, ρ) = {s 1 , . . . , s k } by (1) and δ(s j , w) = δ j (s j , w) = t j for each j = 1, . . . , k by the choice of w. Conversely, suppose that P is reachable in A , that is, δ(Q, u) = P for some word u ∈ (Σ ∪{ρ}) * . Then we must have δ j (Q j , u) = {t j } for each j = 1, . . . , k. If the word u has no occurrence of the letter ρ, then u ∈ Σ * and δ j (s j , u) = {t j } for each j = 1, . . . , k so that u is simultaneously accepted by all automata A 1 , . . . , A k . Otherwise we fix the rightmost occurrence of ρ in u and denote by w the suffix of u following this occurrence so that w ∈ Σ * and u = vρw for some v ∈ (Σ ∪ {ρ}) * . Then δ j (Q j , vρ) = {s j } and δ j (s, w) = δ(Q j , vρw) = {t j } for each j = 1, . . . , k. We conclude that w is simultaneously accepted by all automata A 1 , . . . , A k . This completes the proof of our claim and establishes the reduction which obviously can be implemented in logarithmic space.

The reduction used in the above proof is an adaptation of a slightly more involved log-space reduction used by Brandl and Simon [5, Section 3] to show PSPACE-hardness of a natural problem about transformation monoids presented by a bunch of generating transformations.

In connection with Theorem 3, an interesting result by Goralčík and Koubek [13, Theorem 1] is worth being mentioned. If stated in the language adopted in the present paper, their result says that, given a DFA A = Q, Σ with |Q| = n, |Σ| = m and a subset P ⊆ Q with |P | = k, one can decide in O (k + 1)n k+1 m time whether or not there exists a word w ∈ Σ * such that P = Q . w = P . w. (The difference from our definition of reachability is that here one looks for a word not only having the subset P as its image but also acting on P as a permutation.) Thus, if the size of the target set P is treated as a parameter, the algorithm from [START_REF] Goralčík | Rank problems for composite transformations[END_REF] becomes polynomial. One can ask if a similar result holds for the parameterized version of Reachable Subset formulated as follows:

Reachable Subset k : Given a DFA A = Q, Σ, δ and a non-empty subset P ⊆ Q of size k, is it true that P is reachable in A ?

For k = 1, the cited result by Goralčík and Koubek applies since, for P being a singleton, any word w ∈ Σ * such that P = Q . w automatically satisfies the additional condition P . w = P . For k > 1, the question about the complexity of Reachable Subset k is open. The reduction from the proof of Theorem 3 cannot help here because the size k of the subset P in this reduction is equal to the number of DFAs in the instance of FAI from which we depart, and for each fixed k, there is a polynomial algorithm that decides on all instances of FAI with k automata. Now we return to the question of whether or not complete reachability can be decided in polynomial time. It should be noted that Theorem 3 does not imply any hardness conclusion here: while checking reachability of individual subsets is PSPACE-complete, checking reachability of all non-empty subsets may still be polynomial even though the latter problem consists of exponentially many individual problems! One can illustrate this phenomenon of 'simplification due to collectivization' with the following example. If is known [START_REF] Kozen | Lower bounds for natural proof systems[END_REF] that the following membership problem for transition monoids of DFAs is PSPACE-complete: given a DFA A = Q, Σ and a transformation ϕ : Q → Q, does ϕ belongs to the transition monoid M (A ), i.e., is there a word w ∈ Σ * such that qϕ = q . w for all q ∈ Q? On the other hand, one can decide in polynomial time whether or not every transformation of the state set belongs to the transition monoid of a given DFA. Indeed, given a DFA A = Q, Σ , we partition the alphabet Σ as Σ = Π ∪ ∆, where Π consists of all letters that act on Q as permutations and ∆ contains all letters with non-zero defect. First we inspect ∆: if no letter in ∆ has defect 1, then it is clear that the monoid M (A ) contains no transformation of defect 1 (see the observation registered at the beginning of Section 2). Further, we invoke twice the polynomial algorithm by Furst, Hopcroft and Luks [START_REF] Furst | Polynomial-time algorithms for permutation groups[END_REF] for the membership problem in permutation groups: we fix a cyclic permutation and a transposition of Q and check if they belong to the permutation group on Q generated by the permutations induced by the letters in Π.

If the answers to all these queries are affirmative, then M (A ) contains a cyclic permutation, a transposition, and a transformation of defect 1, and it is well-known that any such trio of transformations generates the full transformation monoid T (Q), see, e.g., [START_REF] Ganyushkin | Classical Finite Transformation Semigroups: An Introduction[END_REF]Theorem 3.1.3].

Thus, the complexity of deciding complete reachability for a given DFA remains unknown so far. We expect this problem to be computationally hard for automata over unrestricted alphabets while for automata with a fixed number of letters a polynomial algorithm may exist. For instance, if Conjecture 1 holds true, there exists a polynomial algorithm that recognizes completely reachable automata among DFAs with 2 input letters. Indeed, let A = Q, {a, b} be a DFA with n states, n > 1. Every subset of the form Q . w, where w is a non-empty word over {a, b}, is contained in either Q . a or Q . b. At least one of the letters must have defect 1 since no subset of size n -1 is reachable otherwise, and if the other letter has defect greater than 1, only one subset of size n -1 is reachable. Hence, if A is a completely reachable automaton, one of its letters has defect 1 while the other has defect at most 1. Therefore for each proper reachable subset P ⊂ Q, there is a product w of words of defect 1 with respect to A such that P = Q . w. In view of Theorem 1, if Conjecture 1 holds true, then complete reachability of A is equivalent to strong connectivity of the graph Γ 1 (A ). It remains to show that for automata with 2 input letters, the latter condition can be verified in polynomial time.

Once the graph Γ 1 (A ) is constructed, checking its strong connectivity in polynomial time makes no difficulty. However, it is far from being obvious that Γ 1 (A ), even though it definitely has polynomial size, can always be constructed in polynomial time. Indeed, by the definition, the edges of Γ 1 (A ) arise from transformations of defect 1 in the transition monoid of A , and for an automaton with n states, the number of transformations of defect 1 in M (A ) may reach n! n 2 . Our algorithm depends on some peculiarities of automata with 2 input letters. It incrementally appends edges to a spanning subgraph of Γ 1 (A ) in a way such that one can reach a conclusion about strong connectivity of Γ 1 (A ) by examining only polynomially many transformations of defect 1. In the following brief description of the algorithm, we use the notation introduced in Section 2 in the course of defining the graph Γ 1 (A ).

Thus, again, let A = Q, {a, b} be a DFA with n states, n > 1. For certainty, let a stand for the letter of defect 1. If b also has defect 1, then at most two subsets of size n -1 are reachable (namely, Q . a and Q . b), and A can only be completely reachable provided that n = 2. The automaton A is then nothing but the classical flip-flop, see Fig. 3. of the states at which edges of Γ 1 (A ) may originate is easily seen to coincide with the set {excl(a), excl(ab), . . . , excl(ab n-1 )}. For Γ 1 (A ) to be strongly connected, it is necessary that every vertex is an origin of an edge whence the latter set must be equal to Q. Taking into account that excl(ab k ) = excl(a) . b k for each k = 1, . . . , n -1, we conclude that b must be a cyclic permutation of Q. It is easy to show that excl(w) . b = excl(wb) and dupl(w) . b = dupl(wb) for every word w of defect 1, and therefore, b acts as a permutation on the edge set E 1 of Γ 1 (A ).

The set E 1 contains the edges (excl(a), dupl(a)), . . . , (excl(ab n-1 ), dupl(ab n-1 )).

(

) 2
Since dupl(ab k ) = dupl(a) . b k for each k = 1, . . . , n -1, the edges in (2) are the 'translates' of the edge (excl(a), dupl(a)). Any two edges in (2) start at different vertices and end at at different vertices, whence for some d such that d < n and d divides n, the edges in (2) form d directed cycles, each of size n d . If d = 1, we can already conclude that the graph Γ 1 (A ) is strongly connected. If d > 1, denote the cycles by C 1 , . . . , C d and consider the words a 2 , aba, . . . , ab n-1 a. It can be easily shown that exactly two of them have defect 1; let us denote these two words by w 1 and w 2 . Since w 1 and w 2 end with a, we have Q . w 1 = Q . w 2 = Q . a whence excl(w 1 ) = excl(w 2 ) = excl(a). Thus, the edges (excl(w 1 ), dupl(w 1 )) and (excl(w 2 ), dupl(w 2 )) start at the vertex excl(a) which can be assumed to belong to the cycle C 1 . If also the ends of these edges lie in C 1 , one can show that no further edge in E 1 can connect C 1 with another cycle whence C 1 forms a strongly connected component of Γ 1 (A ). We then conclude that Γ 1 (A ) is not strongly connected. Now suppose that the edge (excl(w i ), dupl(w i )) where i = 1 or i = 2 connects the vertex excl(a) with a vertex from the cycle C j where j > 1. Then we append the edge and all its translates (excl(w i b k ), dupl(w i b k )), k = 1, . . . , n-1, to C 1 , . . . , C d ; in the case where both (excl(w 1 ), dupl(w 1 )) and (excl(w 2 ), dupl(w 2 )) leave C 1 , we append both these edges and all their translates. After that, we get larger strongly connected subgraphs D 1 , . . . , D ℓ isomorphic to each other, where ℓ < d and ℓ divides d. If ℓ = 1, then the graph Γ 1 (A ) is strongly connected. If ℓ > 1, we iterate by considering the words w i a, w i ba, . . . , w i b n-1 a. Eventually, either we reach a strongly connected spanning subgraph of Γ 1 (A ), and then the graph Γ 1 (A ) is strongly connected as well, or on some step the process gets stacked, which means that Γ 1 (A ) has a proper strongly connected component, and therefore, is not strongly connected.

The described process branches, and in the worst case the number of words of defect 1 to be analyzed doubles at each step. On the other hand, since the steps are indexed by a chain of divisors of n, the number of steps does not exceed log 2 n + 1. Thus, executing the algorithm, we have to analyze at most

1 + 2 + 4 + • • • + 2 ⌈log 2 n⌉+1 = O(n)
words of maximum length O(n log 2 n), and therefore, the algorithm can be implemented in polynomial time.

Minimal Completely Reachable Automata

Syntactic complexity of a regular language is a well established concept that has attracted much attention lately, see, e.g., [START_REF] Brzozowski | Syntactic complexity of R and J-trivial regular languages[END_REF][START_REF] Brzozowski | Upper bound on syntactic complexity of suffix-free languages[END_REF]. It can be defined as the size of the transition monoid of the minimal DFA recognizing the language. It appears to be worthwhile to extend this concept to automata by defining the syntactic complexity of an arbitrary DFA A as the size of its transition monoid M (A ). In fact, if one thinks of a DFA as a computational device rather than acceptor, its transition monoid can be thought of as the device's 'software library' since the monoid contains exactly all programs (transformations) that the automaton can execute. From this viewpoint, measuring the complexity of an automaton by the size of its 'software library' is fairly natural.

As already mentioned in Section 1, the syntactic complexity of a completely reachable automaton with n states cannot be less than 2 n -1. It turns out that this lower bound is tight if one considers automata over unrestricted alphabet. We present now a construction for completely reachable automata with n states and syntactic complexity 2 n -1; for short, we call them minimal completely reachable automata.

Our construction produces minimal completely reachable automata from full binary trees satisfying certain subordination conditions. Recall that a binary tree is said to be full if each its vertex v either is a leaf or has exactly two children that we refer to as the left child or the son of v and the right child or the daughter of v. (Thus, all vertices except the root have a gender.) It is well known (and easy to verify) that a full binary tree with n leaves has 2n -1 vertices. As full binary trees are the only trees occurring in this paper, we call them just trees in the sequel.

If Γ is a tree and v is a vertex in Γ , we denote by Γ v the subtree of Γ rooted at v. The span of v, denoted span(v), is the number of leaves in the subtree Γ v . Fig. 4 shows a tree with vertices labelled by their spans. By a homomorphism between two trees Γ 1 and Γ 2 we mean a map from the vertex set of Γ 1 into the vertex set of Γ 2 that sends the root of Γ 1 to the root of Γ 2 and preserves the parent-child relation. Given two trees Γ 1 and Γ 2 , we say that Γ 1 subordinates Γ 2 if there exists a 1-1 homomorphism ξ : Γ 1 → Γ 2 such that for span(v) ≤ span(vξ) for every vertex v of Γ 1 . If u and v are two vertices of the same tree Γ , we say that u subordinates v if the subtree Γ u subordinates the subtree Γ v . A tree is said to be respectful if it satisfies two conditions:

(S1) if a male vertex has a nephew, the nephew subordinates his uncle; (S2) if a female vertex has a niece, the niece subordinates her aunt.

For an illustration, the tree shown in Fig. 4 satisfies (S1) but fails to satisfy (S2): the daughter of the root has a niece but this niece does not subordinates her aunt. On the other hand, the tree shown in Fig. 5 is respectful. (In order to ease the inspection of this claim, we have shown the uncle-nephew and the aunt-niece relations in this tree with dotted and dashed arrows respectively.) It is easy to show that there exist respectful trees with any number of leaves. In the following table (borrowed from [START_REF] Bondar | Classification of L-cross-sections of Tn[END_REF]) we present the numbers of respectful trees with up to 10 leaves. We are not aware of any closed formula for the number of respectful trees with a given number of leaves.

In our construction, we use certain markings of trees by intervals of the set N of positive integers considered as a chain under the usual order:

1 < 2 < • • • < n < . . . . If i, j ∈ N and i ≤ j, the interval [i, j] is the set {k ∈ X n | i ≤ k ≤ j}. We write [i] instead of [i, i].
By the span of an interval we mean the number of its elements. Now, a faithful interval marking of a tree Γ is a map µ from the vertex set of Γ into the set of all intervals in N such that for each vertex v, -the span of the interval vµ is equal to span(v); -if vµ = [i, j] and s and d are respectively the son and the daughter of v, then sµ = [i, k] and dµ = [k + 1, j] for some k such that i ≤ k < j.

It easy to see that every tree Γ admits a faithful interval marking which is unique up to an additive translation: given any two markings µ, µ ′ of Γ , there is an integer m such that vµ = vµ ′ + m for every vertex v. Observe that if µ is a faithful interval marking of a tree Γ and v is a vertex of Γ , then the restriction of µ to the subtree Γ v is a faithful interval marking of the latter. Fig. 6 demonstrates a faithful interval marking of the tree from Fig. 5.

the interval rµ, where r stands for the root of Γ , and the input alphabet of A µ (Γ ) consists of 2n -2 letters a v , one for each non-root vertex v of Γ . To define the action of the letters, we proceed by induction on n.

For n = 1, that is, for the trivial tree Γ with one vertex r and no edges, A µ (Γ ) is the trivial automaton with one state and no transitions, so that nothing has to be defined. Now suppose that n > 1. Take any non-root vertex v of Γ ; we have to define the action of the letter a v on the elements of the interval rµ. If s and d are respectively the son and the daughter of r, the interval rµ is the disjoint union of sµ and dµ. If v = s and v = d, then v is a non-root vertex in one of the subtrees Γ s or Γ d . These two cases are symmetric, so that we may assume that v belongs to Γ s . By the induction assumption applied to Γ s and its marking induced by µ, the action of a v is already defined on the states from the interval sµ; we extend this action to the whole interval rµ by setting y . a v := y for each y ∈ dµ.

It remains to define the action of the letters a s and a d . Again, by symmetry, it suffices to handle one of these cases, so that we define that action of a s . If s has no nephew in Γ , then d is a leaf and dµ = [m] for some m ∈ N. Then we let x . a s := m for each x ∈ rµ. Otherwise let t be the nephew of s. The subordination condition (S1) implies that span(t) ≤ span(s). Let sµ = [i, j], tµ = [k, ℓ]. Then h = (j-i)-(ℓ-k) ≥ 0, and we define the action of a s on sµ as follows: By the induction assumption applied to the subtree Γ d and its marking induced by µ, the action of the letter a t is already defined on the states from the interval dµ; now we define the action of a s on dµ by setting y . a s := y . a t for all y ∈ dµ. This completes our construction.

The reader may find it instructive to work out Construction T2A on a concrete example. For the tree from Fig. 5 and 6 used for illustrations above, computing all 12 input letters of the corresponding automaton would be rather cumbersome but one can check, for instance, that the letters a s and a d act on the set [START_REF] Adler | Equivalence of topological Markov shifts[END_REF][START_REF] Brzozowski | Upper bound on syntactic complexity of suffix-free languages[END_REF] as follows: Those who prefer a complete example can look at the DFA E 3 from Example 2: the automaton was in fact derived by Construction T2A from the respectful tree with 3 leaves shown in Fig. 7. In particular, this explains our choice of notation for the input letters of E 3 that perhaps had slightly puzzled the reader when she or he encountered this automaton in Section 2. By the way, the flip-flop in Fig. 3 also can be obtained by Construction T2A (from the unique tree with 2 leaves).

[1] [2] [1, 2] [3] [1, 3]
Observe that all automata constructed from different markings of the same respectful tree are isomorphic since passing to another marking only results in a change of the state names. Taking this into account, we omit the reference to µ in the notation and denote the automaton derived from any marking of a given respectful tree Γ simply by A (Γ ).

We say that two DFAs A = Q, Σ, δ and B = Q, ∆, ζ are syntactically equivalent if their transition monoids coincide. Now we are ready for the main result of this section. Theorem 4. 1. For each respectful tree Γ , the automaton A (Γ ) is a minimal completely reachable automaton.

2. Every minimal completely reachable automaton is syntactically equivalent to an automaton of the form A (Γ ) for a suitable respectful tree Γ .

3. Every minimal completely reachable automaton with n states has at least 2n -2 input letters.

Claims 1 and 2 in Theorem 4 are essentially equivalent to the main results of the papers [START_REF] Bondar | L-cross-sections of the finite symmetric semigroup[END_REF][START_REF] Bondar | Classification of L-cross-sections of Tn[END_REF] by the first author who has used a slightly different construction expressed in the language of transformation monoids: given a marking of a respectful tree Γ she constructs the transition monoid of A (Γ ) rather than the automaton itself. Claim 3 is new but we have not included its proof here due to the space limitations because the only proof we have at the moment requires reproducing several concepts and results from [START_REF] Bondar | L-cross-sections of the finite symmetric semigroup[END_REF][START_REF] Bondar | Classification of L-cross-sections of Tn[END_REF] and restating them in the language adopted in the present paper. It is very tempting to invent a direct proof of this claim that would bypass rather bulky considerations from [START_REF] Bondar | L-cross-sections of the finite symmetric semigroup[END_REF][START_REF] Bondar | Classification of L-cross-sections of Tn[END_REF]. Theorem 4 leaves widely open the question about lower bounds for syntactic complexity of completely reachable automata with restricted alphabet. In particular, the case of completely reachable automata with 2 input letters both is of interest and seems to be tractable. The latter conclusion follows from our analysis of completely reachable automata with 2 input letters at the end of Section 3 which demonstrates that such DFAs have rather a specific structure.

We say that a DFA A = Q, Σ, δ induces a DFA B = Q, ∆, ζ on the same state set if the transition monoid of A contains that of B. Equivalently, this means that for every letter b ∈ ∆, there exists a word w ∈ Σ * such that ζ(q, b) = δ(q, w) for every q ∈ Q. This relation between automata plays an essential role in the theory of synchronizing automata, see, e.g., [START_REF] Ananichev | Primitive digraphs with large exponents and slowly synchronizing automata[END_REF]. With respect to completely reachable automata, the following question is of interest: is it true that every completely reachable automaton induces a minimal completely reachable automaton? In other words, is it true that an automaton of the form A (Γ ) 'hides' within every completely reachable automaton?

5 More Open Questions Since completely reachable automata are synchronizing, it is natural to ask what is the maximum reset threshold for completely reachable automata with n states. In view of Example 1, the lower bound (n -1) 2 for this maximum is provided by the Černý automata C n . For completely reachable automata with 2 input letters this bound is tight because, except for the flip-flop, such automata have a letter that acts as a cyclic permutation of the state set, and therefore, Dubuc's result [START_REF] Dubuc | Sur les automates circulaires et la conjecture de Černý[END_REF] applies to them. Some partial results about synchronization of completely reachable automata can be found in [START_REF] Don | The Černý conjecture and 1-contracting automata[END_REF], but the general problem of finding the maximum reset threshold for completely reachable automata with n states and unrestricted alphabet remains open.

The problem discussed in the previous paragraph basically asks what is the minimum length of a word that reaches a singleton. For completely reachable automata, a similar question makes sense for an arbitrary nonempty subset. Thus, we suggest to investigate the minimum length of a word that reaches a subset with m element in a completely reachable automaton with n states as a function of n and m. Don [9, Conjecture 2] has formulated a very strong conjecture that implies the upper bound n(nm) on this length. Observe that if this upper bound indeed holds, then completely reachable automata satisfy the Černý conjecture. To see Fig. 8. A graph and two of its colorings this, take a completely reachable automaton A = Q, Σ with n states; it should possess a letter a ∈ Σ such that q . a = q ′ . a for two different states q, q ′ ∈ Q. If a word w ∈ Σ * of length at most n(n -2) is such that Q . w = {q, q ′ }, the word wa is a reset word for A and has length at most n(n -2) + 1 = (n -1) 2 .

Another intriguing problem about completely reachable automata suggested by the theory of synchronizing automata is a variant of the Road Coloring Problem. We recall notions involved there. A road coloring of a finite graph Γ consists in assigning non-empty sets of labels (colors) from some alphabet Σ to edges of Γ such that the label sets assigned to the outgoing edges of each vertex form a partition of Σ. Colored this way, Γ becomes a DFA over Σ; every such DFA is called a coloring of Γ . Fig. 8 shows a graph and two of its colorings by Σ = {a, b}, one of which is the Černý automaton C 4 . The Road Coloring Problem, recently solved by Trahtman [START_REF] Trahtman | The road coloring problem[END_REF], had asked which strongly connected graphs admit synchronizing colorings, i.e., colorings that are synchronizing automata. It turns out that, as it was conjectured in [START_REF] Adler | Equivalence of topological Markov shifts[END_REF], the necessary and sufficient condition for a scn to possess a synchronizing coloring is that the greatest common divisor of lengths of all directed cycles in the graph should be equal to 1. The latter property is called aperiodicity or primitivity.

An analogous question makes sense for completely reachable automata. Namely, call a coloring of a graph completely reachable if it yields a completely reachable automaton. Our problem then consists in characterising graphs that admit completely reachable colorings. Such graphs must be strongly connected and primitive since every completely reachable automaton is strongly connected and synchronizing. However, it is easy to produce an example of a strongly connected primitive graph that has no completely reachable coloring; such a graph is shown in Fig. 9 on the left. Moreover, there are interesting phenomena that have no parallel in the theory of synchronizing automata; for instance, there exist graphs that have no completely reachable coloring with 2 letters but admit such a coloring with 3 letters; an example of such a graph is presented in the center of Fig. 9 while the corresponding coloring is shown on the right.

Fig. 1 .

 1 Fig. 1. The automaton Cn

1 2 3 Fig. 2 .

 32 Fig. 2. The automaton E3 and the graph Γ1(E3)

Fig. 3 .

 3 Fig. 3. Filp-flop

Fig. 4 .

 4 Fig. 4. An example of a tree with spans of its vertices shown

Fig. 5 .

 5 Fig. 5. An example of a respectful tree

  i . a s = (i + 1) . a s = • • • = (i + h) . a s := k, (i + h + 1) . a s := k + 1, . . . , j . a s := ℓ.

Fig. 7 .

 7 Fig. 7. The tree behind the automaton E3

Fig. 9 .

 9 Fig. 9. The left graph has no completely reachable coloring; the central graph has no completely reachable coloring with 2 letters but has a completely reachable coloring with 3 letters shown in the right

⋆ Supported by the Russian Foundation for Basic Research, grant no. 16-01-00795, the Ministry of Education and Science of the Russian Federation, project no. 1.1999.2014/K, and the Competitiveness Program of Ural Federal University. The paper was written during the second author's stay at Hunter College of the City University of New York as Ada Peluso Visiting Professor of Mathematics and Statistics with a generous support from the Ada Peluso Endowment.