Timothy Ng
email: ng@cs.queensu.ca

David Rappaport

Kai Salomaa
email: ksalomaa@cs.queensu.ca

State Complexity of Suffix Distance

The neighbourhood of a regular language with respect to the prefix, suffix and subword distance is always regular and a tight bound for the state complexity of prefix distance neighbourhoods is known. We give upper bounds for the state complexity of the neighbourhood of radius k of an n state DFA (deterministic finite automaton) language with respect to the suffix distance and the subword distance, respectively. For restricted values of k and n we give a matching lower bound for the state complexity of suffix distance neighbourhoods.

Introduction

Distances between strings and languages are used in many applications [START_REF] Deza | Encyclopedia of Distances[END_REF][START_REF] Han | The edit distance between a regular language and a context-free language[END_REF][START_REF] Konstantinidis | Computing the edit distance of a regular language[END_REF][START_REF] Kari | An efficient algorithm for computing the edit distance of a regular language via input-altering transducers[END_REF]. Perhaps the most commonly used distance, the Levenshtein distance (a.k.a. the edit distance), is defined in terms of the number of substitution, insertion and deletion operations needed to transform one string into another. The prefix distance [START_REF] Choffrut | Distances between languages and reflexivity of relations[END_REF][START_REF] Kutrib | Parameterized Prefix Distance between Regular Languages[END_REF] of strings x and y is the sum of the lengths of the suffixes of x and y after their longest common prefix. The suffix distance (respectively, the subword distance) of two strings is defined analogously in terms of the longest common suffix (respectively, subword) of the strings.

Calude et al. [START_REF] Calude | Additive Distances and Quasi-Distances Between Words[END_REF] have shown that additive quasi-distances preserve regularity in the sense that a neighbourhood of a regular language is always regular. The edit distance is the best known example of additive distances. However, not all regularity preserving distances are additive. The prefix, suffix, and subword distances are not additive, but are known to preserve regularity [START_REF] Choffrut | Distances between languages and reflexivity of relations[END_REF].

In general, since the 90's there has been much work on the state complexity of regular languages. Recent surveys on the descriptional complexity of regular languages include [START_REF] Gao | A survey on operational state complexity[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]. For regularity preserving distances an important question is to determine the state complexity of the distance, that is, what is the optimal size of a DFA (deterministic finite automaton) recognizing a neighbourhood of radius k of an n state DFA language. In the context of error correction this can be viewed also as the descriptional complexity of error detection [START_REF] Ng | State complexity of neighbourhoods and approximate pattern matching[END_REF]. The descriptional complexity of error systems has been considered from a different point of view by Kari and Konstantinidis [START_REF] Kari | Descriptional complexity of error/edit systems[END_REF]. They establish upper and lower bounds for the size of DFAs needed to recognize a given error system.

A neighbourhood of a language recognized by a DFA A with respect to the prefix distance, roughly speaking, can be recognized by simulating the computation of A and, for each non-final state, keeping track of the shortest path (up to the radius of the neighbourhood) to a final state of A. Additionally, we just need a number of error states equal to the radius of the neighbourhood. This means that prefix distance is an "inexpensive" operation in terms of state complexity. A tight lower bound for the state complexity of prefix distance neighbourhoods is known both for general regular languages and for finite languages [START_REF] Ng | State complexity of prefix distance. In: Implementation and Application of Automata, CIAA 2015[END_REF][START_REF] Ng | State complexity of prefix distance of subregular languages[END_REF].

On the other hand, suffix distance (and subword distance) neighbourhoods are considerably more "difficult", that is, more expensive in terms of state complexity, to recognize by a DFA because the computation has no way of knowing where the longest common suffix begins. This means that the computation has to be inherently nondeterministic and as can, perhaps, be expected the state complexity of the neighbourhood depends exponentially on the size of the original DFA and the radius of the neighbourhood.

This paper shows that the suffix distance neighbourhood of radius k of an n state DFA language over an alphabet of size ≥ 2 can be recognized by a DFA with k -1 -1 + 2 n -1 states when k < n. If A recognizes a finite language, the upper bound for the state complexity of the neighbourhood is

k -1 -1 + k • 2 n 2 .
We give matching lower bound constructions both for general regular languages and for finite languages using a binary alphabet in the case when n is roughly equal to 2 • k. For k > n, we show that the suffix distance neighbourhood can be recognized by a DFA with (k -n) + 2 n+1 -2 states and give matching lower bound constructions for both general regular languages and finite languages over an alphabet of size n+1. We show also that for the class of suffix-closed languages, the neighbourhood is recognized by a DFA with at most n + k + 1 states and that this bound is tight for all k ∈ N. Finally, we derive an upper bound for the state complexity of subword distance neighbourhoods but it remains open whether the bound is tight.

Preliminaries

We recall some basic definitions on regular languages and distance measures. 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].

In the following Σ is always a finite alphabet, the set of strings over Σ is Σ * and ε is the empty string. 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 subword 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 deterministic finite automaton (DFA) is a tuple A = (Q, Σ, δ, q 0 , F ) where Q is a finite set of states, Σ is an alphabet, δ is a partial function δ : Q × Σ → Q, q 0 ∈ Q is the initial state, and F ⊆ Q is a set of final states. We extend the transition function δ to a partial Q × Σ * → Q in the usual way. A DFA A is complete if δ is defined for all q ∈ Q and a ∈ Σ.

A string w ∈ Σ * is accepted by A if δ(q 0 , w) ∈ F . The language recognized by A is L(A) = {w ∈ Σ * | δ(q 0 , w) ∈ F }. Two states p and q of 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 and no two states are equivalent.

A nondeterministic finite automaton (NFA) is an extension of a DFA where the transition function is allowed to be multivalued, that is, δ is a function

Q × Σ → 2 Q .
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 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.

Distances and neighbourhoods of regular languages

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]. It is defined by

d p (x, y) = |x| + |y| -2 • max z∈Σ * {|z| | x, y ∈ zΣ * }.
Similarly, the suffix distance of x and y counts the number of symbols which do not belong to the longest common suffix of x and y and is defined

d s (x, y) = |x| + |y| -2 • max z∈Σ * {|z| | x, y ∈ Σ * z}.
The subword distance measures the similarity of x and y based on their longest common continuous subword and is defined

d f (x, y) = |x| + |y| -2 • max z∈Σ * {|z| | x, y ∈ Σ * zΣ * }.
The term "subword distance" is taken from Choffrut and Pighizzini [START_REF] Choffrut | Distances between languages and reflexivity of relations[END_REF]. However, "subword distance" has also been used for a distance defined in terms of the longest common noncontinuous subword [START_REF] Lothaire | Applied Combinatorics on Words, Ch. 1 Algorithms on Words. Encyclopedia of Mathematics and It's Applications 105[END_REF].

It is known that neighbourhoods of regular languages with respect to the prefix, suffix and subword distance are always regular [START_REF] Choffrut | Distances between languages and reflexivity of relations[END_REF][START_REF] Ng | State complexity of prefix distance. In: Implementation and Application of Automata, CIAA 2015[END_REF]. We refer to the size of the minimal DFA recognizing the radius k neighbourhood of an n state DFA language with respect to a distance X simply as the state complexity of distance X. Tight bounds for the state complexity of the prefix distance are known [START_REF] Ng | State complexity of prefix distance. In: Implementation and Application of Automata, CIAA 2015[END_REF]. Optimal bounds for the size of an NFA recognizing a suffix distance, or subword distance, neighbourhood of a regular language are also known [START_REF] Ng | State complexity of prefix distance. In: Implementation and Application of Automata, CIAA 2015[END_REF]. The bounds on the size of the NFAs imply the following upper bounds for deterministic state complexity of suffix distance and subword distance, respectively. Proposition 1. Suppose L is a regular language recognized by a DFA with n states and k ∈ N. Then

sc(E(L, d s , k)) ≤ 2 n+k -1 and sc(E(L, d f , k)) ≤ 2 (k+1)n+2k -1.
Finally, we define the function ψ A : Q → N 0 to give the length of the shortest path from the initial state q 0 to the state q. Formally, ψ A is defined by

ψ A (q) = min w∈Σ * {|w| | δ(q 0 , w) = q}.
Note that under this definition, ψ A (q 0 ) = 0 for the initial state q 0 .

State Complexity of Suffix Neighbourhoods

In this section, we consider the deterministic state complexity of suffix distance neighbourhoods. First, we construct a DFA for the neighbourhood of an n-state DFA of radius k with respect to the suffix distance d s , when k < n and then give a matching lower bound when k = n 2 for an n state DFA. Proposition 2. Let n > k ≥ 0 and L be a regular language recognized by a DFA with n states over an alphabet Σ, with |Σ| ≥ 2. Then there is a DFA recognizing

E(L, d s , k) with at most |Σ| k -1 |Σ|-1 + 2 n -1 states.
Proof. Let L be recognized by the DFA A = (Q, Σ, δ, q 0 , F ) with |Q| = n. We construct a DFA A = (Q , Σ, δ , q 0 , F ) that recognizes the neighbourhood

E(L, d s , k). First, let us consider what it means if w ∈ E(L(A), d s , k).
If w is in the neighbourhood, then this means that there exists a word x recognized by A such that d(w, x) ≤ k. In other words, we can write w = w z and x = x z for words w , x , z ∈ Σ * such that |w | + |x | ≤ k. However, when A reads w, it is not known when such a common suffix z might begin. A common suffix may begin in each of the first k symbols of w, so A must keep track of and compute all possible common suffixes that begin on each of the first k symbols of w. We define the state set

Q = {0, . . . , k} × 2 Q
and we define the initial state by q 0 = (0, {q ∈ Q | ψ A (q) ≤ k}) the set of final states is given by

F = {0, . . . , k} × {P ⊆ Q | P ∩ F = ∅}.
In other words, a state (i, P ) of A is final if and only if P contains a final state of A.

The state set consists of subsets of the original state set with a counter component. The operation of the machine begins by counting the first k steps of computation. On the ith step of the initial k steps, the machine reaches a state containing those states reachable from direct transitions from the set of states from the (i -1)th computation step and adds every state reachable from q 0 within k -i steps and the counter component is incremented. After the kth computation step, no further steps need to be counted and the counter is no longer incremented since states are no longer added to the existing state sets.

The transition function δ is defined for a ∈ Σ by

-δ ((i, P ), a) = (i + 1, X) for 0 ≤ i ≤ k -1
, where X is defined as

X = {δ(p, a) | p ∈ P } ∪ {q ∈ Q | ψ A (q) ≤ k -(i + 1)}, -δ ((k, P ), a) = (k, {δ(p, a) | p ∈ P }).
We now show that reading a word w ∈ Σ * reaches the state (i, P ) if and only if there exists a word x ∈ Σ * such that w = w z and x = x z where |w | ≤ i, |x | ≤ k -i and δ(q 0 , x) ∈ Q.

First, suppose that δ (q 0 , w) = (i, P ). We write w = w z with w , z ∈ Σ * which may possibly be empty. By definition, δ (q 0 , w ) = (|w |, P ) if |w | ≤ k and P contains all states q such that ψ A (q) ≤ k -|w |. In other words, these are states δ(q 0 , x ) where x ∈ Σ * is of length ≤ k -|w |. Choose q to be one of these states and consider the state δ(q , z) = q. Since q ∈ P and δ (q 0 , w) = δ ((|w |, P ), z) = (i, P ), we have q ∈ P . Thus, there exists a word x = x z such that |x | ≤ k -i and δ(q 0 , x) ∈ P . Now, conversely, suppose that for an input word w = w z with |w | ≤ i, there exists a word x = x z with |x | ≤ k -i such that q = δ(q 0 , x) ∈ P . Since |x | ≤ k -i, let q = δ(q 0 , x ) and we have ψ A (q ) ≤ k -i. Then this means we have δ (q 0 , w ) = (|w |, P ) with q ∈ P . Since δ(q , z) = q, we have δ ((|w |, P ), z) = (i, P ) with q ∈ P as desired.

Thus, δ(q 0 , w) ∈ F if and only if there exists x ∈ L such that |w | + |x | ≤ k for w = w z and x = x z.

However, not all (k + 1) • 2 n in {0, . . . , k} × 2 Q are reachable. Note that for i < k, the only words that can be read to reach a state (i, P ) are those of length exactly i. However, there are only |Σ| i words of length exactly i. Thus, the maximum number of reachable states for 0

≤ i < k is k-1 i=0 |Σ| i = |Σ| k -1 |Σ| -1 . Furthermore, the state ∅ ⊆ Q is unreachable. Thus, A has at most |Σ| k -1 |Σ|-1 +2 n -1 reachable states.
The statement of Proposition 2 assumes that the cardinality of the alphabet is at least two. For suffix distance neighbourhoods of unary languages we have the following bounds. We note that in the unary case the suffix distance coincides with the prefix distance and leave the easy proof for the reader. Lemma 1. Let A be an n state DFA over a unary alphabet and k ∈ N. Then

sc(E(L(A), d s , k)) ≤      n if L(A) is infinite and n > 2k, max{1, n -k} if L(A) is infinite and n ≤ 2k, n + k if L(A) is finite.
For every n, k ∈ N there exists an n state unary DFA A recognizing a finite language such that sc(E(L(A), d s , k)) = n + k. For values n, k ∈ N where n > 2k there exists a unary DFA A with n states recognizing an infinite language such that sc(E(L(A), d s , k)) = n.

For a constant size alphabet, the bound of Proposition 2 is significantly better than the bound implied by known results on nondeterministic state complexity in Proposition 1. Next we show that, at least for some values of the radius k, the bound of Proposition 2 is tight.

Lemma 2. Let k = n 2 .
Then there exists a DFA A n with n states over a binary alphabet such that

sc(E(L(A n ), d s , k)) ≥ 2 k + 2 n -2.
Proof. Let A n = (Q n , {a, b}, δ n , 0, {0}), shown in Figure 1. The following theorem then follows from Proposition 2 and Lemma 2. Now we will consider the case when the distance k is greater than the number of states n of the given DFA and give a matching lower bound. Proposition 3. Let k > n > 0 and L be a regular language recognized by a DFA with n states over an alphabet Σ with |Σ| ≥ 2. Then there is a DFA recognizing E(L, d s , k) with at most (k -n) + 2 n+1 -2 states.

0 start 1 • • • k k + 1 • • • n -1 a,
Proof. Let A = (Q, Σ, δ, q 0 , F ) with |Q| = n. Then we follow the construction given in the proof of Proposition 2 to obtain the DFA A = (Q , Σ, δ , q 0 , F ) that recognizes the neighbourhood E(L(A), d s , k) with k > n. We note that ψ A (q) ≤ n for all q ∈ Q and thus by the definition of the transition function, we have for 0 ≤ i ≤ k -n and all words w of length i, δ(q 0 , w) = (i, Q). This gives us k -n states. Then on the following n steps, we proceed as in the rest of Proposition 2. This suggests that there are at most |Σ| n -1

|Σ|-1 states. However, in this case, there are far fewer states than this.

To consider how many states there are, we observe that the above bound requires that each word of length i > k -n reaches a different state (i, P ), giving us a total of |Σ| i-(k-n) states for each i. Then we must consider how many different subsets P ⊆ Q are reachable. Recall that by definition, all states q with ψ A (q) ≤ k -i are contained in P for (i, P ). Thus, on step i, two states (i, P ) and (i, P ) both P and P contain the subset {q ∈ Q | ψ A (q) ≤ k -i}. Then if P and P are different, they must contain different subsets of the set

{q ∈ Q | ψ A (q) > k -i}.
Let j be the size of the set {q ∈ Q | ψ A (q) > k -i}. Then in order for each word of length i to reach a different state, we must have |Σ| i-(k-n) ≤ 2 j different subsets. This means that we must have at least (i -(k -n)) • log 2 |Σ| states q with ψ A (q) > k -i on step i of a computation on A . In other words, for each 1 ≤ i ≤ max q∈Q ψ A (q), there are at least log 2 |Σ| states q with ψ A (q) = i. However, since k > n, the number of states of A are further restricted by this condition. Let = max q∈Q ψ A (q). Then there are at most k -

n log 2 |Σ| + |Σ| n log 2 |Σ| -1 |Σ|-1
reachable states for words of length up to k. We observe that this is maximized when |Σ| = 2. That is, for any alphabet of size at least 2, the maximum is achieved when we have for each i exactly one state q such that ψ A (q) = i. This gives us a maximum of 2 n -1 reachable states of the form (i, P ) for i < k.

After the kth step of computation, there are 2 n -1 reachable states of the form (k, P ) as usual. This gives us a total of at most (k -n)+2 n+1 -2 states.

We will show that the bound from Proposition 3 is reachable for a family of n state DFAs over an alphabet of size n + 1. Lemma 3. Let k > n > 0. Then there exists a DFA B n with n states over an alphabet of size n + 1 such that 2, with Σ n = {a 0 , a 1 , . . . , a n } and the transition function is defined by δ(i, a j ) = i + 1 mod n for all 0 ≤ i ≤ n -1, 0 ≤ j ≤ n, and i = j.

sc(E(L(A n ), d s , k)) ≥ (k -n) + 2 n+1 -2. Proof. Let B n = (Q n , Σ n , δ n , 0, {0}), shown in Figure
0 start 1 2 • • • n -1 Σn -a0 Σn -a1 Σn -a2 Σn -an-2
Σn -an-1 Fig. 2. The DFA Bn.

Proposition 3 and Lemma 3 can then be summarized in the following theorem.

Theorem 2. Let k > n and let L be a regular language recognized by an nstate DFA over an alphabet Σ with |Σ| ≥ 2. Then a DFA recognizing E(L, d s , k) requires at most (k -n) + 2 n+1 -2 states. There is a family of DFAs with n states over an alphabet of size n + 1 which reaches this bound.

State Complexity of Subword Distance

Now, we give an upper bound on the deterministic state complexity of subword neighbourhoods by giving a construction for a DFA for the neighbourhood of radius k with respect to the subword distance d f . In the construction we again assume that the cardinality of the alphabet is at least two. For unary alphabets, the subword distance coincides with the suffix distance and a tight bound is obtained from Lemma 1. Proposition 4. Let n > k ≥ 0 and L be a regular language recognized by a DFA with n states over the alphabet Σ with |Σ| ≥ 2. Then there is a DFA recognizing

E(L, d f , k) with at most |Σ| k -1 |Σ|-1 + (k + 2) • 2 n•(k+1) states.
The bound of Proposition 4 is significantly better than the bound implied by nondeterministic state complexity [START_REF] Ng | State complexity of neighbourhoods and approximate pattern matching[END_REF] (in Proposition 1) for a fixed alphabet Σ. However, we do not know whether the bound is the best possible. Languages Here, we consider the state complexity of neighbourhoods with respect to the suffix distance of languages which belong to subregular language classes. First, we consider neighbourhoods of finite languages. Proposition 5. Let n > k ≥ 0 and L be a finite language recognized by a DFA with n states over a binary alphabet. Then there is a DFA recognizing E(L, d s , k) with at most

2 k + k • 2 n 2 -1 states.
Proof. We use the construction for A from the proof of Proposition 2. Observe that, as is the case for general regular languages, not all (k + 1) • 2 n states that are defined are reachable. Recall that the states of A are pairs (i, P ) where i is a counter from 0 to k and P is a subset of states of A and that a word w reaches a state (i, P ) if and only if there exists a word x ∈ Σ * such that w = w z and x = x z where |w | ≤ i, |x | ≤ k -i and δ(q 0 , x) ∈ Q. We also note that for i < k, any state (i, P ) with P ⊆ Q is reachable on a word of length exactly i. This gives us at most i<k 2 i = 2 k -1 reachable states of the form (i, P ) for i < k.

It remains to show how many states of the form (k, P ) with P ⊆ Q are reachable. Since P is a subset of the set of states of A, we would like to know how many different subsets P exist such that (k, P ) is reachable. Since A recognizes a finite language, there exists at least one state q of A with ψ A (q) = i that is reachable on some string of length i and is not reachable on any string of length j > i.

Recall that A recognizes a finite language and in each state (k, P ) of A , the set P is a subset of states of A. First, we observe that the above property does not hold for subsets P ⊆ Q in states of the form (i, P ) with i < k. To see this, we consider some i and observe that every state q ∈ Q with ψ A (q) ≤ k -i is in some subset P with (i, P ) reachable for all i < k by definition. Hence, why we can narrow our focus only to those states of the form (k, P ).

Let (k, T ) be a state that is reached on a word w of length k. Since A is deterministic, there are up to 2 k possible such states.

Let R i ⊆ Q denote the set of states of A that are not contained in any state P ⊆ Q, where (k, P ) is reachable on a word of length greater than k + i. In other words, R i is the set of states of A which become unreachable in A on a word of length i. We note that R i must contain at least one element, since A recognizes a finite language.

We write T = R ∪ S, where R ⊆ 0≤i≤k R i and S ⊆ Q \ R. We have |Q \ R| ≤ n -k, since k < n. From this, we can see that to maximize the number of states that are reachable, each R i must contain at most one element. This gives us a total of 2 n-k possible subsets S.

Then for each set T = R ∪ S that is reachable on a word of length k, there is a state

T i = (R \ i j=0 R j ) ∪ S that is reachable on a word of length k + i for 1 ≤ i ≤ k. Since each R i has one element, each subset S is contained in up to k different subsets of Q that are reachable in A . This gives k • 2 n 2
possible subsets that can be reached on each string of length greater than k.

Thus, A can have up to

|Σ| k -1 |Σ|-1 + k • 2 n 2 -1 states in total.
The statement of Proposition 5 assumes that the alphabet is binary. A tight bound is known from Lemma 1 also for finite languages.

Lemma 4. Let k = n 2 .
Then there exists a DFA C n with n states over a binary alphabet recognizing a finite language such that

sc(E(L(C n ), d s , k)) ≥ 2 k + k • 2 n 2 -1.
Proof. Let C n = (Q n , {a, b}, δ n , 0, {n -1}), shown in Figure 3. We construct the DFA C n recognizing the neighbourhood by using the construction from Proposition 2.

0 start 1 • • • k k + 1 • • • n -1 a, b a, b a, b b a, b a, b
Fig. 3. The DFA Cn.

We can summarize the results of Proposition 5 and Lemma 4 as follows:

Theorem 3. Let L be a finite language recognized by an n-state DFA over an alphabet Σ with |Σ| ≥ 2 and k ≤ n. Then a DFA recognizing E(L, d s , k) requires at most

|Σ| k -1 |Σ|-1 + k • 2 n 2 -1 states.
There is a family of DFAs with n states over a binary alphabet which reaches this bound when k = n 2 . Now, we show that if k > n, the lower bound coincides with the upper bound for regular languages. Proof. Let D n = (Q n , Σ n , δ n , 0, {0}), shown in Figure 4, with Σ n = {a 0 , a 1 , . . . , a n-1 } and the transition function is defined by δ(i, a j ) = i + 1 for all 0 ≤ i < n -1, 0 ≤ j ≤ n -1, and i = j. Next, we consider the class of suffix-closed languages [START_REF] Brzozowski | Quotient Complexity of Closed Languages[END_REF]. A language L is suffix-closed if wx ∈ L implies x ∈ L. It is well known that the class of suffixclosed languages is a subclass of the regular languages. We will give a tight bound on the size of the DFA for neighbourhoods of suffix-closed languages with respect to the suffix distance.

Theorem 5. Let L be a suffix-closed language recognized by an n-state DFA. Then a DFA recognizing E(L, d s , k) requires at most n + k + 1 states. For each n ∈ N there exists an n-state DFA E n recognizing a suffix-closed language such that the state complexity of E(L(E n ), d s , k) is n + k + 1 for all k ∈ N.

The DFA E n is shown in Figure 5.

Conclusion

The state complexity of radius k prefix distance neighbourhoods of an n state DFA language depends linearly on n and on k [START_REF] Ng | State complexity of prefix distance. In: Implementation and Application of Automata, CIAA 2015[END_REF]. As we have seen, the corresponding bounds for the suffix and the subword distance neighbourhoods depend exponentially on n and k and, furthermore, coming up with matching lower bounds is considerably more involved.

For suffix distance neighbourhoods where the radius k equals, roughly, half of the number of states n, we have given a matching lower bound construction based on a binary alphabet. However (and perhaps curiously), the construction does not seem to extend, at least not directly, for other values of the radius when k < n.

Fig. 1 .

 1 Fig. 1. The DFA An.

Theorem 1 .

 1 Let n > k and let L be a regular language recognized by an nstate DFA over an alphabet Σ with |Σ| ≥ 2. Then a DFA recognizing E(L, d s , k)requires at most |Σ| k -1 |Σ|-1 + 2 n -1 states.There is a family of DFAs with n states over a binary alphabet which reaches this bound when k = n 2 .

Theorem 4 .

 4 Let L be a finite language recognized by an n-state DFA over an alphabet Σ with |Σ| ≥ 2 and k > n. Then a DFA recognizing E(L, d s , k) requires at most (k -n) + 2 n+1 -2 states. There is a family of DFAs with n states over an alphabet of size n which reaches this bound.

2 Fig. 4 .

 24 Fig. 4. The DFA Dn.

Fig. 5 .

 5 Fig. 5. The DFA En.

The precise state complexity of subword distance neighbourhoods remains open. We do not have a lower bound construction matching the upper bound of Proposition 4 for the state complexity of subword distance neighbourhoods.


Marina Maslennikova
email: maslennikova.marina@gmail.com

Reset Complexity of Ideal Languages Over a Binary Alphabet

Keywords: ideal language, synchronizing automaton, reset word, reset complexity, PSPACE-completeness

We prove PSPACE-completeness of checking whether a given ideal language serves as the language of reset words for some automaton with at most four states over a binary alphabet.

Introduction

Regular languages admit compact representations by different tools: deterministic and nondeterministic finite automata, syntactic monoids, regular expressions, etc. Each of these tools gives rise to the corresponding complexity measure of regular languages. Along with these general tools, there are more specific devices for representing regular languages from some special classes. One of such classes is formed by ideal regular languages. A language I ⊆ Σ * is called a two-sided ideal (or simply an ideal ) if I is non-empty and Σ * IΣ * ⊆ I. In what follows we consider only languages which are regular, thus we drop the adjective "regular". Thus, the expression "ideal language" (or simply "ideal") always means a regular two-sided ideal language.

Let A = Q, Σ, δ be a deterministic finite automaton (DFA), where Q is the state set, Σ stands for the input alphabet, and δ : Q×Σ → Q is the totally defined transition function defining the action of the letters in Σ on Q. The function δ is extended uniquely to a function Q × Σ * → Q, where Σ * stands for the free monoid over Σ. The latter function is still denoted by δ. In the theory of formal languages the definition of a DFA usually includes the initial state q 0 ∈ Q and the set F ⊆ Q of terminal states. We use these ingredients when dealing with automata as devices for recognizing languages. A language L ⊆ Σ * is recognized by an automaton A = Q, Σ, δ, q 0 , F if L = {w ∈ Σ * | δ(q 0 , w) ∈ F }. We denote by L[A ] the language recognized by the automaton A .

A DFA A = Q, Σ, δ is called synchronizing if there exists a word w ∈ Σ * whose action leaves the automaton in one particular state no matter at which state in Q it is applied: δ(q, w) = δ(q ′ , w) for all q, q ′ ∈ Q. Any word w with this property is said to be reset for the DFA A . For the last 50 years synchronizing automata have received a great deal of attention. For a brief introduction to the theory of synchronizing automata we refer the reader to the surveys [START_REF] Sandberg | Homing and synchronizing sequences[END_REF][START_REF] Volkov | Synchronizing automata and the Černý conjecture[END_REF].

In the present paper we focus on some complexity aspects of the theory of synchronizing automata. We denote by Syn(A ) the language of reset words for a given automaton A . It is well known that Syn(A ) is regular [START_REF] Volkov | Synchronizing automata and the Černý conjecture[END_REF]. Furthermore, it is an ideal in Σ * . On the other hand, every regular ideal language I serves as the language of reset words for some automaton. For instance, the minimal automaton recognizing I is synchronized exactly by I [START_REF] Maslennikova | Reset Complexity of Ideal Languages[END_REF]. Thus synchronizing automata can be considered as a special representation of ideal languages. Effectiveness of such a representation was addressed in [START_REF] Maslennikova | Reset Complexity of Ideal Languages[END_REF]. The reset complexity rc(I) of an ideal language I is the minimal possible number of states in a synchronizing automaton A such that Syn(A ) = I. Every such automaton A is called a minimal synchronizing automaton (for brevity, MSA). Let sc(I) be the number of states in the minimal automaton recognizing I. For every ideal language I, we have rc(I) ≤ sc(I) [START_REF] Maslennikova | Reset Complexity of Ideal Languages[END_REF]. Moreover, for each n ≥ 3, there exists a language I n such that rc(I n ) = n and sc(I n ) = 2 n -n [START_REF] Maslennikova | Reset Complexity of Ideal Languages[END_REF]. Thus the representation of an ideal language by means of a synchronizing automaton can be exponentially more succinct than the "traditional" representation via the minimal automaton. This resembles the well-known property of nondeterministic finite automata (for brevity, NFAs): for each n ≥ 3, there is an n-state NFA N such that every DFA recognizing the same language as N has at least 2 n -1 states [6, 7].

The following question arises: how hard is it to check that a given synchronizing DFA B is an MSA for a given ideal I (I is assumed to be given by a synchronizing DFA A with Syn(A ) = I)? Another question related to the previous one is the following: how hard is it to verify the inequality rc(I) ≤ ℓ for a given ideal I and a given ℓ ∈ N? The inequality rc(I) ≤ ℓ means that there exists a synchronizing DFA B with at most ℓ states such that Syn(B) = I. The aforementioned questions are trivial for automata over a unary alphabet, thus in what follows we deal with alphabets that have at least two letters. The problem of checking the equality Syn(B) = I is equivalent to the problem of checking the equality Syn(A ) = Syn(B) for two given synchronizing automata A and B. The complexity of the latter problem has been studied in [START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF]. It is well known that the equality of the languages recognized by two given DFAs can be checked in time polynomial of the size of automata. However, the problem of checking the equality of the languages of reset words of two synchronizing DFAs turns out to be PSPACE-complete [START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF]. Recall that the problem of checking the equality of languages recognized by two given NFAs is PSPACE-complete as well [START_REF] Stockmeyer | Word problems requiring exponential time[END_REF]. In this context we again find that synchronizing automata share some properties of nondeterministic finite automata.

We state formally the SYN-EQUALITY problem:

-Input: synchronizing automata A and B.

-Question: is Syn(A ) = Syn(B)?

In [START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF] SYN-EQUALITY has been proved to be PSPACE-complete. In the present paper we provide a more transparent proof of PSPACE-hardness of this problem. In particular, it allows us to strengthen the result of [START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF] concerning the problem of evaluating the reset complexity of a given ideal language.

We state formally the RESET-INEQUALITY problem:

-Input: synchronizing DFA A over Σ, ℓ ∈ N.

-Question: is rc(Syn(A )) ≤ ℓ?

In [START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF] RESET-EQUALITY has been shown to be PSPACE-complete for ℓ = 3 and enough large input alphabet (with at least five letters). In the present paper we significantly strengthen this result and prove that RESET-INEQUALITY, restricted to a binary alphabet, remains PSPACE-complete even for ℓ = 4. Note that RESET-INEQUALITY is trivial for DFAs over a unary alphabet and, furthermore, RESET-INEQUALITY can be solved in polynomial of the size of A time for ℓ = 1 and ℓ = 2 in the general case [START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF]. Thus the only question that remains open concerns the complexity of RESET-INEQUALITY for ℓ = 3 in the case of a binary alphabet.

The paper is organized as follows. In Section 1 we introduce some definitions and preliminary results. In Section 2 we provide a modified proof of PSPACE-hardness of SYN-EQUALITY. Section 3 contains the main result about PSPACE-completeness of the problem RESET-INEQUALITY in the case of a binary alphabet.

Preliminaries

A state s of a DFA A = Q, Σ, δ is said to be a sink if δ(s, a) = s for all a ∈ Σ. If the transition function δ is clear from the context, we write q . w instead of δ(q, w) for q ∈ Q and w ∈ Σ * . This notation extends naturally to any subset H ⊆ Q by putting H . w = {δ(q, w) | q ∈ H}.

Recall that a word u ∈ Σ * is a prefix (suffix or factor, respectively) of a word w if w = us (w = tu or w = tus, respectively) for some t, s ∈ Σ * . A reset word for a DFA A is called minimal if none of its proper prefixes nor suffixes is reset.

Due to [5, Corollary 1] we have the following proposition.

Proposition 1. SYN-EQUALITY is in PSPACE.

To prove that SYN-EQUALITY is a PSPACE-complete problem we reduce the following well-known PSPACE-complete problem to the complement of SYN-EQUALITY. This problem deals with checking emptiness of the intersection of languages recognized by DFAs from a given collection [START_REF] Kozen | Lower bounds for natural proof systems[END_REF].

FINITE AUTOMATA INTERSECTION -Input: given n DFAs M i = Q i , Σ, δ i , q i , F i , for i = 1, . . . , n. -Question: is i L[M i ] = ∅?
Since FINITE AUTOMATA INTERSECTION is known to be PSPACEcomplete even in the case of a binary alphabet, we may assume that |Σ| = 2, in particular, let Σ be {a, b}.

PSPACE-hardness of SYN-EQUALITY

The proof of PSPACE-hardness of SYN-EQUALITY is based on the same idea as the proof from [START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF]. However, our modified construction allows us to reduce the number of letters from 5 to 4. We provide a sketch of the proof of PSPACEhardness for the sake of completeness.

Given an instance of FINITE AUTOMATA INTERSECTION, we can assume without loss of generality that each initial state q i has no incoming edges and q i / ∈ F i . Indeed, excluding the case for which the empty word ε is in

L[M i ] we can always build a DFA M ′ i = Q ′ i , Σ, δ ′ i , q ′ i , F i ,
which recognizes the same language as M i , such that the initial state q ′ i has no incoming edges. This can easily be achieved by adding a new initial state q ′ i to the state set Q i and defining the transition function δ ′ i by the rule:

δ ′ i (q ′ i , c) = δ i (q i , c) for all c ∈ Σ and δ ′ i (q, c) = δ i (q, c) for all c ∈ Σ, q ∈ Q i .
Furthermore, we may assume that the sets Q i , for i = 1, . . . , n, are pairwise disjoint. Also we can suppose that any letter from Σ does not belong to i L[M i ]. Otherwise, we add a new initial state q ′′ i to each M ′ i and put δ i (q ′′ i , c) = q ′ i for all c ∈ Σ. This assumption will be of use in Section 3.

To build an instance of SYN-EQUALITY from the DFAs M i , i = 1, . . . , n, we construct a DFA A = Q, ∆, ϕ with Q = n i=1 Q i ∪ {s, h}, where s and h are new states not belonging to any Q i . We add two new letters x and z to the alphabet Σ and let ∆ = Σ ∪ {x, z}. The transition function ϕ of the DFA A is defined by the following rules:

ϕ(q, c) = δ i (q, c)
for all i = 1, . . . , n, q ∈ Q i and c ∈ Σ; ϕ(q, x) = q i for all i = 1, . . . , n, q ∈ Q i ; ϕ(q, z) = s for all i = 1, . . . , n, q ∈ F i ; ϕ(q, z) = h for all i = 1, . . . , n, q

∈ Q i \ F i ; ϕ(h, c) = s for all c ∈ ∆; ϕ(s, c) = s for all c ∈ ∆.
The resulting automaton A is shown schematically in Fig. 1. The action of letters from Σ on the states p ∈ Q i is not shown. Denote by G i the set Q i \ (F i ∪ {q i }). All the states from the set G i are shown as the node labeled by G i . All the states from the set F i are shown as the node labeled by F i .

The constructed automaton is synchronizing, for example, by the word zz. It can be easily seen that by the definition of the transition function ϕ we get ϕ(Q, w) ∩ Q i = ∅ if and only if w ∈ (Σ ∪ {x}) * . Consider the language

I = (Σ ∪ {x}) * z∆ + .
From the observations above and the definition of ϕ we obtain Lemma 1.

Lemma 1. n i=1 L[M i ] = ∅ if and only if Syn(A ) = I.
We omit the proof of Lemma 1 because of space constraints. Now we build a 3-state automaton B = P, ∆, τ (see Fig. 2). Its state set is P = {p 1 , p 2 , s ′ }, where s ′ is a unique sink state. It is easy to verify that I serves as the language of reset words for B. Furthermore, I does not serve as the language of reset words for a synchronizing automaton of size at most two over the same alphabet ∆. So B is an MSA for I and rc(Syn(B)) = 3. In order to construct C = C, {µ, λ}, ϕ 2 and D = D, {µ, λ}, τ 2 we apply a recoding technique which has been used in [START_REF] Ananichev | Slowly Synchronizing Automata and Digraphs[END_REF]3,[START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF]. Namely, we define morphisms

PSPACE-completeness of RESET-INEQUALITY

s ′ p1 p2
x, Σ ∆ ∆ z Fig. 2. Automaton B h : {λ, µ} * λ → ∆ * and h : ∆ * → {λ, µ} * λ preserving the property of being a reset word for the corresponding automaton. Since the definitions of morphisms differ from those described in [START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF], we present them here. Let d 1 = z, d 2 = a, d 3 = b and d 4 = x. We put h(µ k λ) = d k+1 for k = 0, . . . , 3 and h(µ k λ) = d 4 = x for k ≥ 4. Every word from the set {λ, µ} * λ can be uniquely factorized by words µ k λ, k = 0, 1, 2, . . . , whence the mapping h is totally defined. We also consider the morphism h : ∆ * → {λ, µ} * λ defined by the rule h(d k ) = µ k-1 λ. Now we take the constructed above DFA B = P, ∆, τ with the state set P = {p 1 , p 2 , s ′ }. We build D = D, {µ, λ}, τ 2 with a unique sink state ζ 2 .

We associate each state p i of the automaton B with a 4-element set of states P i = {p i,1 , . . . , p i,4 } of the automaton D. Namely, the states p i,2 , p i,3 , p i,4 are copies of the state p i associated with p i,1 . The action of the letter µ is defined in the following way: τ 2 (p i,k , µ) = p i,k+1 for k ≤ 3, and τ 2 (p i,4 , µ) = p i,4 . We put D = P 1 ∪ P 2 ∪ {ζ 2 }, where ζ 2 is a unique sink state. The action of the letter λ is defined by the rules:

-if τ (p i , d k ) = s ′ , then τ 2 (p i,k , λ) = ζ 2 ; -if τ (p i , d k ) = p j , then τ 2 (p i,k , λ) = p j,1 .
The latter rule means that if there is a transition from p i to p j labeled by the letter d k , then there is a transition from p i,1 to p j,1 labeled by the word µ k-1 λ.

The DFA C is constructed in an analogous way. Fig. 3 illustrates the automata D (left) and C (right). The actions of µ and λ are shown by solid and dotted arrows, respectively. For compactness, we do not show some transitions labeled by λ in C . Nevertheless, the action of λ is defined on each state in C . The resulting automata C and D have 4(|Q| -1) + 1 and 9 states respectively, where |Q| is the cardinality of the state set of A .

Lemma 4. Syn(A ) = Syn(B) if and only if Syn(C ) = Syn(D).

Proof. It is convenient to organize the DFA D as a table. The set P i is called the i-th column of the set D. For each k = 1, . . . , 4, the set R k = {p 1,k , p 2,k } is called the k-th row of the set D. The k-th row contains copies of all states corresponding to the k-th letter from ∆. The i-th column contains the state p i,1 corresponding to the state p i and its copies p i,2 , p i,3 , p i,4 . Each state from the i-th column maps under the action of µ to a state from the same column. For k ≤ 3, the row R k maps under the action of µ to the next row R k+1 . The 4-th row is fixed by µ, that is, τ 2 (R 4 , µ) = R 4 . The state set D maps under the action of λ to a subset of R 1 ∪ {ζ 2 }. The DFA C has the same properties.

Assume that Syn(A ) = Syn(B). From the proof of Lemma 1 it follows that the word w = xw ′ z with w ′ ∈ i L[M i ] is reset for A and it is not reset for B. Thus h(w) ∈ Syn(C ) and h(w) ∈ Syn(D). So Syn(C ) = Syn(D).

Assume now that Syn(A ) = Syn(B). We show that every minimal reset word of C is reset for D and every minimal reset word of D is reset for C . Let u be a minimal reset word of C . Any word u ∈ {µ} * is not in Syn(C ) since µ brings each column to its subset. Thus u contains some factor from {λ} and λ. Thus if u does not end up with λ, then it is not a minimal reset word. We have u ∈ {λ, µ} * λ, i.e., u = u ′ λ for some u ′ ∈ {λ, µ} * . Let us note that λ 2 appears in u as a factor (otherwise, u / ∈ Syn(C )). If the last letter of u ′ is λ and λ 2 is not a factor of u ′ , then Theorem 1 (Theorem 4, [START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF]). SYN-EQUALITY restricted to a binary alphabet case is PSPACE-complete.

As a corollary, we immediately obtain the following statement.

R({p 2,1 }) = R({p 2,2 }) = R({p 2,3 }) = R({p 2,4 }); R({p 1,2 }) = R({p 1,3 }) = R({p 1,4 }).
These equalities imply that the language of reset words of D ′ coincides with the language of reset words of D (see Fig. 4). Indeed, due to the equalities above we can merge states p 2,1 , p 2,2 , p 2,3 , p 2,4 into a unique state p 2 and merge states p A standard tool for finding the language of reset words of a given DFA K = Q, δ, Σ is the power automaton P(K ). Its state set is the set Q of all nonempty subsets of Q, and the transition function is defined as a natural extension of δ to the set Q × Σ (the resulting function is also denoted by δ), namely, δ(S, c) = {δ(q, c) | q ∈ S} for S ⊆ Q and c ∈ Σ. If we take the set Q as the initial state and singletons as final states in P(K ), then we obtain an automaton recognizing Syn(K ). It is easy to see that if all singletons are merged into a unique sink state s, the resulting automaton still recognizes Syn(K ). Throughout the paper the term power automaton and the notation P(K ) refer to this modified version. L[M i ] = ∅. We are going to show that rc(J) > 4 in this case. Let u be a minimal reset word for C . By the arguments from the proof of Lemma 4 and by the construction of C , one may note that u can be factorized as u = u ′ λ for some u ′ ∈ {µ, λ} + . Also λ 2 is necessarily a factor of u. Moreover, by the definition of the transition function of C we have λ 3 ∈ J while λ, λ 2 / ∈ J. From the arguments above it follows that every MSA for J has at least 4 states. Arguing by contradiction, let us assume that there exists a 4state automaton E = P, {λ, µ}, γ with Syn(E ) = J. Without loss of generality suppose that P = {0, 1, 2, 3}. We define the action of λ on the state set P . Since λ 3 ∈ Syn(E ) and λ, λ 2 ∈ Syn(E ), there is a unique up to isomorphism way to define the action of λ on the states from the state set P (see Fig. 5). The word λ 2 µλ is in Syn(C ), i.e., λ 2 µλ ∈ J. By the definition of the action of λ in E we get that γ(P, λ 2 ) = {2, 3}. On the other hand, λ 2 µ ∈ Syn(C ), thus λ 2 µ ∈ Syn(E ). Hence {2, 3} under the action of µ maps to a two-element subset which is translated by λ into {3}. So we need to guarantee the equality γ({2, 3}, µ) = {2, 3}. The action of µ at states 2 and 3 can be defined in two possible ways such that the last equality is true (see Fig. 6). Note that λµλ ∈ Syn(C ). Therefore, λµλ is not a reset word for E . Since we have γ({1, 2, 3}, λµλ) = {3} for each variant from Fig. 6, the word λµλ should map the state 0 to a state different from 3. However γ(0, λ) = 1, thus 1 under the action of µ maps to either 0 or 1. All in all, for each variant from Fig. 6, we get two ways to define the image of 1 under the action of µ (see Fig. 7).

It remains to define the image of 0 under the action of µ. Let us note that µ 2 λ 2 ∈ Syn(C ). Since γ({2, 3}, µ 2 λ 2 ) = {3}, one of the equalities, γ(0, µ) = 0 or

Fig. 1 .

 1 Fig. 1. Automaton A

Lemma 2 .

 2 Syn(B) = I. Finally, by Lemmas 1 and 2, we have the following claim. Lemma 3. n i=1 L[M i ] = ∅ if and only if Syn(A ) = Syn(B).

  We have reduced the problem FINITE AUTOMATA INTERSECTION to the complement of SYN-EQUALITY. By construction of DFAs A and B, we have ∆ = {z, a, b, x}. Now we are going to study the complexity of checking the inequality rc(I) ≤ ℓ in the case of a binary alphabet. First we build DFAs C = C, {µ, λ}, ϕ 2 and D = D, {µ, λ}, τ 2 over a binary alphabet {µ, λ} with unique sink states ζ 1 and ζ 2 respectively. It turns out that the constructions of C and D preserve the equality of reset languages. More precisely, Syn(A ) = Syn(B) if and only if Syn(C ) = Syn(D). Let J = Syn(C ). We will prove that rc(J) > 4 if and only if n i=1 L[M i ] = ∅. It allows to obtain the desired result about PSPACEcompleteness of RESET-INEQUALITY for a binary case alphabet.

Fig. 3 .

 3 Fig. 3. The automata D (left) and C (right)

  u / ∈ Syn(C ). If λ 2 is a factor of u ′ , then by the definition of the transition functions of C and D we have u ∈ Syn(C ) and u ∈ Syn(D). So the inclusion Syn(C ) ⊆ Syn(D) takes place. The opposite inclusion Syn(D) ⊆ Syn(C ) is verified analogously. ⊓ ⊔ Lemma 4 implies PSPACE-completeness of the problem SYN-EQUALITY restricted to a binary alphabet.

Proposition 2 (

 2 [START_REF] Maslennikova | Complexity of checking whether two automata are synchronized by the same language[END_REF]). Let ℓ be a positive integer number and A a synchronizing DFA. The problem of checking the inequality rc(Syn(A )) ≤ ℓ is in PSPACE. So we reduced FINITE AUTOMATA INTERSECTION to the complement of SYN-EQUALITY restricted to a binary case alphabet as follows. For an arbitrary instance of FINITE AUTOMATA INTERSECTION one may build the corresponding automata C and D over a binary alphabet {λ, µ} such that n i=1 L[M i ] = ∅ if and only if Syn(C ) = Syn(D). The set of all words synchronizing a fixed subset H ⊆ D of the state set of D is defined as follows: R(H) = {v ∈ {λ, µ} * | H . v = {ζ 2 }}. Since ζ 2 is a unique sink state in D, any reset word for D maps any subset of D to {ζ 2 }. Let us note that

Fig. 4 .

 4 Fig. 4. The automaton D ′

Lemma 5 .

 5 Let J = Syn(C ). The equality n i=1 L[M i ] = ∅ takes place if and only if rc(J) ≤ 4.Proof. Let E = P, {λ, µ}, γ be an MSA for J. Assume thatn i=1 L[M i ] = ∅.By Lemma 1 we get that Syn(A ) = Syn(B) = I with I = (Σ ∪ {x}) * z∆ + . By Lemma 4 we have J = Syn(C ) = Syn(D ′ ). Let us note that λ 3 ∈ Syn(D ′ ). Furthermore, λ, λ 2 ∈ Syn(D ′ ). It means that P . λ 3 P . λ 2 P . λ P . Hence |P | ≥ 4. Therefore, rc(J) ≥ 4. On the other hand, Syn(D ′ ) = J. Thus D ′ is an MSA for J = Syn(C ), i.e., rc(J) = 4.Let us assume now that n i=1

Fig. 5 .

 5 Fig. 5. The action of λ in E

Fig. 6 .

 6 Fig. 6. The action of µ at states 2 and 3 in the DFA E

support 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.3253.2017, and the Competitiveness Enhancement Program of Ural Federal University.

γ(0, µ) = 1, is required to take place. Furthermore, we have γ({1, 2, 3}, µ 2 λ 2 ) = {3} in the third and forth variants from Fig. 7. It means that there exists the only possibility to put γ(0, µ) = 0 for these variants. So we have six automata over the alphabet {λ, µ} shown in Fig. 8. It remains to check whether J could coincide with the set of reset words for one of these DFAs. Lemmas 1 and 4 we have J = Syn(C ) = Syn(D). Therefore, E 1 is not an MSA for J. For E 1 and E 2 the equality Syn(E 1 ) = Syn(E 2 ) takes place. It can be easily checked by the construction of power automata P(E 1 ) and P(E 2 ) (see Fig. 9). It implies that E 2 cannot be an MSA for J.

By the assumption

or, equivalently, δ j (q j , b) ∈ Q j \ F j for some index j. Take the word xbz. By the definition of the transition function ϕ of A we have ϕ(Q, xbz) = {h, s}, so xbz ∈ Syn(A ). By the definition of the morphism h : ∆ * → {λ, µ} * λ we have h(xbz) = µ 3 λµ 2 λλ. By the definition of the transition function ϕ 2 of C we get ϕ 2 (q j,1 , µ 3 λµ 2 λ) = ϕ 2 (q j,1 , µ 2 λ) = p t,1 , where p t = δ j (q j , b) and p t ∈ F j . Hence ϕ 2 (q j,1 , µ 3 λµ 2 λλ) = ϕ 2 (p t,1 , λ) = h 1 . So we obtain that µ 3 λµ 2 λλ ∈ Syn(C ). Therefore, µ 3 λµ 2 λλ ∈ J, but it is easy to see that µ 3 λµ 2 λλ ∈ Syn(E 3 ). Hence E 3 can not be an MSA for J. Analogously, E 4 can not be an MSA for J as well.

Note that (µλ) 3 ∈ Syn(E 5 ) and (µλ) 3 ∈ Syn(E 6 ). By the definition of the morphism h : {λ, µ} * λ → ∆ * , we have h((µλ) 3 ) = (h(µλ)) 3 = a 3 . But the word a 3 is not reset for A (see Fig. 1). By the definition of the transition function of C it implies that h(a 3 ) ∈ Syn(C ), that is (µλ) 3 ∈ J. In this way neither E 5 , nor E 6 can be an MSA for J. We have considered all possible candidates for a 4-state MSA for J. Each automaton E i cannot be chosen as an MSA for J. Also it is known that rc(J) ≥ 4. Finally, we have rc(J) > 4.

⊓ ⊔

Now we are in position to state the main result of the paper. Lemma 5 and Proposition 2 imply the following theorem.


Janusz A Brzozowski

Sylvie Davies
email: sldavies@uwaterloo.ca

David R Cheriton

Most Complex Non-Returning Regular Languages ⋆

Keywords: atom, boolean operation, concatenation, different alphabets, most complex, non-returning, reversal, regular, star, state complexity, syntactic semigroup, transition semigroup, unrestricted complexity

A regular language L is non-returning if in the minimal deterministic finite automaton accepting it there are no transitions into the initial state. Eom, Han and Jirásková derived upper bounds on the state complexity of boolean operations and Kleene star, and proved that these bounds are tight using two different binary witnesses. They derived upper bounds for concatenation and reversal using three different ternary witnesses. These five witnesses use a total of six different transformations. We show that for each n 4 there exists a ternary witness of state complexity n that meets the bound for reversal and that at least three letters are needed to meet this bound. Moreover, the restrictions of this witness to binary alphabets meet the bounds for product, star, and boolean operations. We also derive tight upper bounds on the state complexity of binary operations that take arguments with different alphabets. We prove that the maximal syntactic semigroup of a non-returning language has (n -1) n elements and requires at least n 2 generators. We find the maximal state complexities of atoms of non-returning languages. Finally, we show that there exists a most complex non-returning language that meets the bounds for all these complexity measures.

Introduction

Formal definitions are postponed until Section 2; we assume the reader is familiar with basic properties of regular languages and finite automata as described in [START_REF] Perrin | Finite automata[END_REF][START_REF] Yu | Regular languages[END_REF], for example.

A deterministic finite automaton (DFA) is non-returning if there are no transitions into its initial state. A regular language is non-returning if its minimal DFA has that property. The state complexity of a regular language L, denoted by κ(L), is the number of states in the minimal DFA accepting L. The state complexity of an operation on regular languages is the maximal state complexity of the result of the operation, expressed as a function of the state complexities of the operands.

The state complexities of common operations (union, intersection, difference, symmetric difference, Kleene star, reverse and product/concatenation) were studied by Eom, Han and Jirásková [START_REF] Eom | State complexity of basic operations on nonreturning regular languages[END_REF]. They pointed out that several interesting subclasses of regular languages have the non-returning property; these subclasses include the class of suffix-free languages (suffix codes) and its subclasses (for example, bifix-free languages), and finite languages.

A regular language L n (a, b, c) of state complexity n is defined for all n 3 in Figure 1. It was shown in [START_REF] Brzozowski | In search of the most complex regular languages[END_REF] that the sequence (L 3 (a, b, c), . . . , L n (a, b, c), . . . ) of these languages meets the upper bounds (for regular languages) on the complexities of all the basic operations on regular languages as follows: If L(b, a) is L(a, b) with the roles of a and b interchanged, then L m (a, b) • L n (b, a) meets the bound mn for all binary boolean operations • that depend on both arguments; if m = n, L m (a, b) • L n (a, b) meets the bound mn; (L n (a, b)) * meets the bound 2 n-1 + 2 n-2 for star; (L n (a, b, c)) R meets the bound 2 n for reversal; and L m (a, b, c)L n (a, b, c) meets the bound (m -1)2 n + 2 n-1 for product. It was proposed in [START_REF] Brzozowski | In search of the most complex regular languages[END_REF] that the size of the syntactic semigroup of a regular language is another worthwhile measure of the complexity of the language. The syntactic semigroup is isomorphic to the transition semigroup of the minimal DFA of L, that is, the semigroup of transformations of the state set of the DFA induced by non-empty words.

Another complexity measure suggested in [START_REF] Brzozowski | In search of the most complex regular languages[END_REF] is the number and state complexities of the atoms of the language, where an atom is a certain kind of intersection of complemented and uncomplemented quotients of L.

It was shown in [START_REF] Brzozowski | In search of the most complex regular languages[END_REF] that the languages L n (a, b, c) not only meet the bounds on the state complexities of operations, but also have the largest syntactic semigroups (of size n n ), and the largest number of atoms (2 n ), all of which have the maximal possible state complexities. In this sense these are most complex regular languages.

In this paper we show that there also exist most complex non-returning languages. For each n 4, we define a language of state complexity n. We prove that the syntactic semigroup of this language has (n -1) n elements (the maxi-mal possible for non-returning languages), that it is generated by n 2 elements, and that the number of generators cannot be reduced. We also show that this language has 2 n atoms, all of which have maximal state complexity. We demonstrate that the upper bound on the state complexity of reversal is met by a single ternary language, and that no binary language meets this bound. Moreover, restrictions of this language to binary alphabets meet the bounds for star, product and boolean operations. This is in contrast to [START_REF] Eom | State complexity of basic operations on nonreturning regular languages[END_REF] where several types of witnesses are used to meet the various bounds. We correct an error in [7, Table 1], where it is stated that the upper bound on the complexity of product cannot be reached with binary witnesses. Additionally, we consider both restricted and unrestricted state complexity [START_REF] Brzozowski | Unrestricted state complexity of binary operations on regular languages[END_REF] of binary operations on non-returning languages. When computing restricted state complexity, one assumes the operation takes in two languages over the same alphabet; for unrestricted state complexity we allow the inputs to be languages over different alphabets.

Omitted proofs can be found at http://arxiv.org/abs/1701.03944.

Preliminaries

A deterministic finite automaton (DFA) is a quintuple D = (Q, Σ, δ, q 0 , F ), where Q is a finite non-empty set of states, Σ is a finite non-empty alphabet,

δ : Q × Σ → Q is the transition function, q 0 ∈ Q is the initial state, and F ⊆ Q is the set of final states. We extend δ to a function δ : Q × Σ * → Q as usual.
A DFA D accepts a word w ∈ Σ * if δ(q 0 , w) ∈ F . The language accepted by D is denoted by L(D). If q is a state of D, then the language L q (D) of q is the language accepted by the DFA (Q, Σ, δ, q, F ). A state is empty if its language is empty. Two states p and q of D are equivalent if L p (D) = L q (D). A state q is reachable if there exists w ∈ Σ * such that δ(q 0 , w) = q. A DFA is minimal if all of its states are reachable and no two states are equivalent. We use Q n = {0, . . . , n-1} as our basic set with n elements. A transformation of Q n is a mapping t : Q n → Q n . The image of q ∈ Q n under t is denoted by qt, and this notation is extended to subsets of Q n : if P ⊆ Q n , then P t = {qt : q ∈ P }. The rank of a transformation t is the cardinality of Q n t. If s and t are transformations of Q n , their composition is denoted (qs)t when applied to q ∈ Q n . Let T Qn be the set of all n n transformations of Q n ; then T Qn is a monoid under composition.

For k 2, a transformation t of a set P = {q 0 , q 1 , . . . , q k-1 } ⊆ Q n is a k-cycle if q 0 t = q 1 , q 1 t = q 2 , . . . , q k-2 t = q k-1 , q k-1 t = q 0 . This k-cycle is denoted by (q 0 , q 1 , . . . , q k-1 ), and leaves the states in Q n \ P unchanged. A 2-cycle (q 0 , q 1 ) is called a transposition. A transformation that sends state p to q and acts as the identity on the remaining states is denoted by (p → q). If a transformation of Q n has rank n -1, then there is exactly one pair of distinct elements i, j ∈ Q n such that it = jt. We say a transformation t of Q n is of type {i, j} if t has rank n -1 and it = jt for i < j.

The syntactic congruence of a language L ⊆ Σ * is defined on Σ + as follows: For x, y ∈ Σ + , x ≈ L y if and only if wxz ∈ L ⇔ wyz ∈ L for all w, z ∈ Σ * . The quotient set Σ + /≈ L of equivalence classes of ≈ L is a semigroup, the syntactic semigroup T L of L.

Let D = (Q n , Σ, δ, 0, F ) be a DFA. For each word w ∈ Σ * , the transition function induces a transformation δ w of Q n by w: for all q ∈ Q n , qδ w = δ(q, w). The set T D of all such transformations by non-empty words is the transition semigroup of D under composition [START_REF] Pin | Syntactic semigroups[END_REF]. Often we use the word w to denote the transformation t it induces; thus we write qw instead of qδ w . We also write w : t to mean that w induces the transformation t.

If D is a minimal DFA of L, then T D is isomorphic to the syntactic semigroup T L of L [START_REF] Pin | Syntactic semigroups[END_REF], and we represent elements of T L by transformations in T D . The size of this semigroup has been used as a measure of complexity [START_REF] Brzozowski | In search of the most complex regular languages[END_REF][START_REF] Brzozowski | Syntactic complexity of ideal and closed languages[END_REF][START_REF] Holzer | On deterministic finite automata and syntactic monoid size[END_REF][START_REF] Krawetz | State complexity and the monoid of transformations of a finite set[END_REF].

The (left) quotient of L ⊆ Σ * by a word w ∈ Σ * is the language w -1 L = {x : wx ∈ L}. It is well known that the number of quotients of a regular language is finite and equal to the state complexity of the language.

Atoms are defined by a left congruence, where two words x and y are congruent whenever ux ∈ L if and only if uy ∈ L for all u ∈ Σ * . Thus x and y are congruent whenever x ∈ u -1 L if and only if y ∈ u -1 L for all u ∈ Σ * . An equivalence class of this relation is an atom of L [START_REF] Brzozowski | Theory of átomata[END_REF]. Atoms can be expressed as non-empty intersections of complemented and uncomplemented quotients of L (see Section 5). The number of atoms and their state complexities were suggested as measures of complexity of regular languages [START_REF] Brzozowski | In search of the most complex regular languages[END_REF] because all quotients of a language and all quotients of its atoms are unions of atoms [START_REF] Brzozowski | Complexity of atoms of regular languages[END_REF][START_REF] Brzozowski | Theory of átomata[END_REF][START_REF] Iván | Complexity of atoms, combinatorially[END_REF]. Suppose • is a unary operation on languages, and f (n) is an upper bound on the state complexity of this operation. If the state complexity of (L n ) • is f (n), then L n is called a witness to the state complexity of • for that n. In general, we need a sequence (L k , L k+1 , . . . , ) of such languages; this sequence is called a stream. Often a stream does not start at 1 because the bound may not hold for small values of n. For a binary operation we need two streams. The languages in a stream usually have the same form and differ only in the parameter n.

Sometimes the same stream can be used for both operands of a binary operation, but this is not always possible. For example, for boolean operations when m = n, the state complexity of L n ∪ L n = L n is n, whereas the upper bound is mn = n 2 . However, in many cases the second language is a "dialect" of the first, that is, it "differs only slightly" from the first. A dialect of L n (Σ) is a language obtained from L n (Σ) by deleting some letters of Σ in the words of L n (Σ) -by this we mean that words containing these letters are deleted -or replacing them by letters of another alphabet Σ ′ . Here we encounter only two types of dialects: 1. A dialect in which some letters were deleted; for example,

L n (a, b) is a dialect of L n (a, b, c) with c deleted, and L n (a, -, c) is a dialect with b deleted. 2.
A dialect in which the roles of two letters are exchanged; for example,

L n (b, a) is such a dialect of L n (a, b).
These two types of dialects can be combined, for example, in L n (a, -, b) the letter c is deleted, and b plays the role that c played originally. The notion of dialects also extends to DFAs; for example, if

D n (a, b, c) recognizes L n (a, b, c) then D n (a, -, b) recognizes the dialect L n (a, -, b).

Main Results

From now on by complexity we mean state complexity.

Let Γ = {a i,j : 0 i < j n -1}, where a i,j is a letter that induces any transformation of type {i, j} and does not map any state to 0.

Let Γ ′ = Γ \ {a 0,n-1 , a 0,1 , a 1,n-1 , a 0,2 }. Let Σ = {a, b, c, d} ∪ Γ ′ , where a : (1, . . . , n -1)(0 → 1), b : (1, 2)(0 → 2), c : (2, . . . , n -1)(1 → 2)(0 → 1)
, and d : (0 → 2). Note that a, b, c and d are transformations of types {0, n -1}, {0, 1}, {1, n -1} and {0, 2}, respectively. Note also that a, b and c restricted to Q n \ {0} generate all the transformations of {1, . . . , n -1}. This follows from the well-known fact that the full transformation semigroup on a set X can be generated by the symmetric group on X together with a transformation of X with rank |X| -1. For X = {1, . . . , n -1}, we see that {(1, . . . , n -1), (1, 2)} (the restrictions of a and b) generate the symmetric group, and (2, . . . , n -1)(1→2) (the restriction of c) is a transformation of rank |X| -1 = n -2.

We are now ready to define a most complex non-returning DFA and language.

Definition 1. For n 4, let D n = D n (Σ) = (Q n , Σ, δ n , 0, {n -1})
, where Σ = {a, b, c, d} ∪ Γ ′ , and δ n is defined in accordance with the transformations described above. See Figure 2 for D n (Σ) restricted to {a, b, c, d}. Let L n = L n (Σ) be the language accepted by D n (Σ). Theorem 1 (Most Complex Non-Returning Languages). For each n 4, the DFA of Definition 1 is minimal and non-returning. The stream (L n (Σ) : n 4) with some dialect streams is most complex in the class of regular non-returning languages in the following sense:

1. The syntactic semigroup of L n (Σ) has cardinality (n -1) n , and at least n 4. For each atom A S of L n (Σ), the complexity κ(A S ) satisfies:

κ(A S ) = 2 n-1 , if S ∈ {∅, Q n }; 2 + |S| x=1 |S| y=1 n-1 x n-1-x y , if ∅ S Q n .
Moreover, at least n 2 letters are required to meet these bounds. 5. The star of L n (a, b) has complexity 2 n-1 . 6. Let m, n 4.

(a) Restricted product:

κ(L m (a, b)L n (a, -, b)) = (m -1)2 n-1 + 1. (b) Unrestricted product: κ(L m (a, b)L n (a, -, b, d)) = m2 n-1 + 1. 7. Let m, n 4.
(a) Restricted boolean operations:

κ(L m (a, b) • L n (b, a)) = mn -(m + n -2).
(b) Additionally, when m = n, we can use the same witness for both arguments:

κ(L m (a, b) • L n (a, b)) = mn -(m + n -2). (c) Unrestricted boolean operations: The complexity of L m (a, b, c)•L n (b, a, d) is mn + 1 if • ∈ {∪, ⊕}, that of L m (a, b, c) \ L n (b, a) is mn -n + 2, and that of L m (a, b) ∩ L n (b, a) is mn -(m + n -2).
All of these bounds are maximal for non-returning languages.

Proof. From the definition of the letters of Σ it is obvious that the DFA D n is non-returning, and that any pair (p, q) of states can be distinguished by the shortest word in a * accepted by p but not by q.

1. This follows from Propositions 1 and 2 below. In particular, note that the syntactic semigroup of L n (Σ) contains the symmetric group on Q n \ {0}, so the conditions of Proposition 2 are met. 2. Observe that for i > 0, the quotient (a i ) -1 L n (a) has complexity n -1; for i = 0, the quotient (a 0 ) -1 L n (a) = L n (a) has complexity n. 3. By Proposition 3 the number of atoms of L n (a, b, c) is 2 n . By [START_REF] Brzozowski | Theory of átomata[END_REF] the complexity of the reverse is the same as the number of atoms. By Proposition 4 at least three letters are required to meet this bound on the number of atoms and the complexity of reverse. 4. See Propositions 5, 6, and 7. 5. See Proposition 8. 6. See Propositions 9 and 10. 7. See Propositions 11 and 12.

We prove Propositions 1-4 and 11 below.

⊓ ⊔

Syntactic Semigroup

For all basic operations on non-returning languages, the complexity bounds can be met with either binary or ternary witnesses [START_REF] Eom | State complexity of basic operations on nonreturning regular languages[END_REF]. However, to meet the bound for the size of the syntactic semigroup, our most complex stream is forced to use an alphabet that grows quadratically in size.

For n 2, let N n denote the semigroup of transformations of Q n such that it = 0 for all i ∈ Q n . We call N n the full non-returning semigroup on Q n . We give a necessary condition and a sufficient condition for a set G to generate N n .

Proposition 1. If G is a generating set for N n , then G contains a transformation of type {i, j} for each {i, j} ⊆ Q n . Thus a minimal generating set has exactly one element of type {i, j} for each of the n 2 sets {i, j} ⊆ Q n . Proof. Suppose t is a transformation of type {i, j}, and let t ′ be an arbitrary transformation. If tt ′ has rank n-1, then tt ′ has type {i, j}. Indeed, since it = jt, it follows that itt ′ = jtt ′ . Thus composing a transformation of type {i, j} with an arbitrary transformation either preserves the type, or lowers the rank.

Suppose G generates N n . Observe that N n does not contain transformations of rank n (since these map some element to 0). Since composition with a transformation of type {i, j} either preserves type or lowers rank, the semigroup generated by G contains only transformations that either have the same type as some element of G, or have rank less than n -1 and so are typeless. But N n contains a transformation of type {i, j} for each {i, j} ⊆ Q n . So if G generates N n , then G must contain an element of type {i, j} for each {i, j} ⊆ Q n .

⊓ ⊔ Proposition 2. Let G be a subset of N n that contains a transformation of type {i, j} for each set {i, j} ⊆ Q n , i < j. Let G ′ be obtained by restricting every transformation in

G to Q n \{0}. If G ′ generates the symmetric group on Q n \{0}, then G generates N n .
Proof. First, we show that G ′ in fact generates the full transformation semigroup on Q n \ {0}. Recall that the full transformation semigroup on X is generated by the symmetric group on X together with a transformation of X of rank |X| -1. By assumption, G ′ contains generators of the symmetric group on Q n \ {0}. Transformations in G of type {i, j} with 0 < i < j have rank n -1, and furthermore their restrictions to Q n \ {0} are of rank n -2.

Thus G ′ contains generators of the symmetric group on Q n \ {0}, as well as a transformation of rank |Q n \ {0}| -1 = n -2; it follows that G ′ generates the full transformation semigroup on Q n \ {0}. Now, we prove that G generates every transformation in N n . Let t be an element of N n ; we want to show that t is in the semigroup generated by G. Since N n does not contain any transformations of rank n, the transformation t has rank less than n, and thus there exist distinct i, j ∈ Q n such that it = jt. Select a transformation s of type {i, j} in G. Then for distinct q, q ′ ∈ Q n , we have qs = q ′ s if and only if {q, q ′ } = {i, j}.

Hence there is a well-defined transformation r ′ of Q n \{0} given by (qs)r ′ = qt for all q ∈ Q; it is well-defined since if we have qs = q ′ s, then {q, q ′ } = {i, j} and is and js get mapped to a common element it = jt. The transformation r ′ lies in the full transformation semigroup on Q n \ {0}, and so it is in the semigroup generated by G ′ . Hence there is some transformation r of Q n in the semigroup generated by G such that r is equal to r ′ when restricted to Q n \ {0}.

Since qs ∈ Q n \ {0} for all q ∈ Q n , it follows that (qs)r = (qs)r ′ = qt for all q ∈ Q n , and thus sr and t are equal as transformations. Since s is in G and r is in the semigroup generated by G, it follows sr = t is in the semigroup generated by G. Thus the semigroup generated by G contains all elements of N n ; but G is a subset of N n , so G generates N n .

⊓ ⊔

Number and Complexities of Atoms

Denote the complement of a language L by L = Σ * \ L. Let Q n = {0, . . . , n -1} and let L n be a non-empty regular language with quotients K = {K 0 , . . . , K n-1 }.

Each subset S of Q n defines an atomic intersection

A S = i∈S K i ∩ i∈S K i , where S = Q n \ S.
An atom of L is a non-empty atomic intersection; this definition is equivalent to that given in Section 2 in terms of a left congruence. Note that if S = T , then A S ∩ A T = ∅; that is, atoms corresponding to distinct subsets of Q n are disjoint. A language of complexity n can have at most 2 n atoms, since there are 2 n subsets of Q. We show that this bound can be met by nonreturning languages. Additionally, we derive upper bounds on the complexities of atoms of non-returning languages, and show that our most complex stream meets these bounds.

We now describe a construction due to Iván [START_REF] Iván | Complexity of atoms, combinatorially[END_REF]. Let L be a regular language with DFA D = (Q, Σ, δ, q 0 , F ). For each S ⊆ Q, we define a DFA D S = (Q S , Σ, ∆, (S, S), F S ) as follows.

-Q S = {(X, Y ) : X, Y ⊆ Q, X ∩ Y = ∅} ∪ {⊥}. State ⊥ is the sink state. -∆((X, Y ), a) = (Xa, Y a) if Xa ∩ Y a = ∅, and otherwise ∆((X, Y ), a) = ⊥; also ∆(⊥, a) = ⊥. -F S = {(X, Y ) : X ⊆ F, Y ⊆ F }.
The DFA D S recognizes the atomic intersection A S of L; if it recognizes a nonempty language, then A S is an atom. We can determine the complexity of A S by counting reachable and distinguishable states in D S . Proposition 3. The language L n = L n (a, b, c) has 2 n atoms.

Proof. We want to show that A S is an atom of L n for all S ⊆ Q n . It suffices to show for each S that the DFA D S recognizes at least one word. Then since atoms corresponding to different subsets of Q n are disjoint, this proves there are 2 n distinct atoms.

First, we show that from the initial state (S, S), we can reach some state of the form (X, Y ) where 0 ∈ X and 0 ∈ Y . Consider the set {0, 1, n -1}. Notice that for each subset {i, j} of {0, 1, n -1}, we have a transformation of type {i, j}: a has type {0, n -1}, b has type {0, 1}, and c has type {1, n -1}. Additionally, by the pigeonhole principle, either S contains two distinct elements from {0, 1, n -1}, or S contains two distinct elements from {0, 1, n -1}.

Suppose without loss of generality it is S which contains two distinct elements from {0, 1, n -1}. Let {i, j} ⊆ S for some {i, j} ⊆ {0, 1, n -1} with i = j. Let σ ∈ Σ be the letter inducing the transformation of type {i, j}. Then we claim (S, S)σ = ⊥. Indeed, suppose that q ∈ Sσ ∩Sσ. Then since σ is a transformation of type {i, j}, we must have iσ = jσ = q, and no other element is mapped to q. But {i, j} ⊆ S, so we cannot have q ∈ Sσ.

Hence Sσ ∩ Sσ = ∅. Furthermore, since σ is a non-returning transformation, we have 0 ∈ Sσ and 0 ∈ Sσ. Thus starting from the initial state (S, S), we can apply σ to reach a state of the form (X, Y ) with 0 ∈ X and 0 ∈ Y . Now, recall that the three transformations {a, b, c}, when restricted to Q n \ {0}, generate all transformations of Q n \ {0}. Since X ⊆ Q n \ {0}, there exists a transformation of Q n \ {0} that maps every element of X to n -1 and every element of (Q n \ {0}) \ X to 1. Let w ∈ {a, b, c} * be a word that induces this transformation when restricted to

Q n \ {0}. Since Y ⊆ Q n \ {0} and Y is disjoint from X, it follows that w maps every element of Y to 1. Since F n = {n -1} is the final state set of D n , we see that Xw ⊆ F n and Y w ⊆ F n . Thus (Xw, Y w) = ({n -1}, {1}) is a final state of D S .
This shows that there exists a word σw ∈ {a, b, c} * that maps the initial state (S, S) of D S to a final state. Thus A S is an atom.

⊓ ⊔

Next, we prove that the bound on number of atoms cannot be met by a binary witness. From [START_REF] Brzozowski | Theory of átomata[END_REF] we know that the number of atoms of a regular language is equal to the state complexity of the reverse of the Hence this also proves a conjecture from [START_REF] Eom | State complexity of basic operations on nonreturning regular languages[END_REF], that a ternary witness is necessary to meet the bound for reversal of non-returning languages. Proposition 4. Let L be a non-returning language of complexity n over Σ = {a, b}. Then the number of atoms of L is strictly less than 2 n .

Proof. Let D be the minimal DFA of L, with state set Q n . We introduce some special terminology for this proof, which generalizes the notion of transformations of type {i, j}. We say that a transformation t unifies i and j, or unifies the set {i, j}, if it = jt. For example, transformations of type {i, j} unify {i, j}. But furthermore, every transformation of Q n of rank n -1 or less unifies at least one pair of elements of Q n . The transition semigroup of D cannot have transformations of rank n, since L is non-returning; thus all the transformations in the transition semigroup must unify some pair of states.

Suppose that in D, the letter a induces a transformation that unifies {i, j}, and b induces a transformation that unifies {k, ℓ}. Assume also that i = j and k = ℓ. We will show that at least one atomic intersection A S of L is empty, and thus is not an atom.

Suppose {i, j} = {k, ℓ}. Let S = {i} and consider the atomic intersection A S . The initial state of the DFA for A S is ({i}, S). Note that j ∈ S, so ja ∈ Sa. But a unifies i and j, so ja = ia ∈ {i}a. Thus since {i}a ∩ Sa = ∅, the letter a sends the initial state ({i}, S) to the sink state. Since b also unifies i and j, the letter b also sends ({i}, S) to the sink state. Thus A S is non-empty if and only if ({i}, S) is a final state. In fact, either A S is non-empty or A S = {ε}, since every non-empty word sends the initial state ({i}, S) to the sink state. If we let T = {j}, the same argument shows that A T is either empty or A T = {ε}. But A S ∩ A T = ∅, so one of A S or A T must be empty. Now, suppose {i, j} ∩ {k, ℓ} = ∅. Let S = {i, k} and consider the atomic intersection A S . The initial state of the DFA for A S is ({i, k}, S) with j, ℓ ∈ S. Thus as before, the transformation a which unifies {i, j} and the transformation b which unifies {k, ℓ} both send A S to the sink state. So either A S is empty or A S = {ε}. For T = {j, ℓ}, the same argument shows that either A T is empty or A T = {ε}. Hence as before, one of A S or A T is empty.

Finally, suppose {i, j} ∩ {k, ℓ} has exactly one element. Then either k ∈ {i, j} or ℓ ∈ {i, j}. Assume without loss of generality that ℓ ∈ {i, j} and ℓ = i; otherwise rename the elements so this is the case. Then a unifies {i, j}, and b unifies {i, k}. Let S = {i} and consider A S . As before, the initial state of the DFA for A S is sent to the sink state by both a and b. Thus either A S is empty or A S = {ε}. For T = {j, k}, the same argument shows that either A T is empty or A T = {ε}. Hence one of A S or A T is empty.

⊓ ⊔ Proposition 5. Let L be a non-returning language of complexity n, and let Q n be the state set of its minimal DFA. Let S ⊆ Q n ; then we have

κ(A S ) 2 n-1 , if S ∈ {∅, Q n }; 2 + |S| x=1 |S| y=1 n-1 x n-1-x y , if ∅ S Q n .
Proposition 6. The atoms of the language L n = L n (Σ) meet the complexity bounds of Proposition 5.

Proposition 7. Let L be a non-returning language over Σ of complexity n. If the atoms of L meet the bounds of Proposition 5, then Σ has size at least n 2 .

6 Other Operations When dealing with binary operations, to avoid confusion between the sets of states {0, . . . , m -1} and {0, . . . , n -1} we use

D ′ m (Σ) = (Q ′ m , Σ, δ ′ m , 0 ′ , {(m - 1) ′ }), and D n (Σ) = (Q n , Σ, δ n , 0, {n -1}), where Q ′ m = {0 ′ , .
. . , (m -1) ′ }. We write L ′ m (Σ) for the language of D ′ m (Σ). Proposition 9 (Restricted Product). Let D n (a, b, c) be the DFA of Definition 1 and let L n (a, b, c) be its language. Then for m, n 4 the complexity of

L ′ m (a, b)L n (a, -, b) is (m -1)2 n-1 + 1.
Proposition 10 (Unrestricted Product). For m, n 4, let L ′ m (respectively, L n ) be a non-returning language of complexity m (respectively, n) over an alphabet Σ ′ , (respectively, Σ). Then the complexity of product is at most m2 n+1 + 1, and this bound is met by L ′ m (a, b) and L n (a, -, b, d). A binary boolean operation is proper if it is not a constant function or a function of only one argument.

′ m (a, b) • L n (b, a) is mn -(m + n -2). If m = n then κ(L ′ m (a, b) • L n (a, b)) = mn -(m + n -2).
Proof. The upper bound was established in [START_REF] Eom | State complexity of basic operations on nonreturning regular languages[END_REF]. For the lower bound, Figure 3 restricted to the alphabet {a, b} shows the two argument DFAs. As usual we construct their direct product. State (0 ′ , 0) is initial and can never be reached again.

If we apply a, we reach state (1 ′ , 2), and the states reachable from this state form the direct product of DFA E Finally, note also that (0 ′ , 0) is distinguishable from all other states. Since (0 ′ , 0)a = (1 ′ , 2) and the preimage of (1 ′ , 2) under a is {(0 ′ , 0), ((m -1) ′ , 1)}, we see that (0 ′ , 0) is distinguishable from (p ′ , q) = ((m -1) ′ , 1) by first applying a, then applying a word that distinguishes (0 ′ , 0)a = (1 ′ , 2) from (p ′ , q)a. It is distinguishable from ((m -1) ′ , 1) by first applying b, then applying a word that distinguishes (0 ′ , 0)b = (2 ′ , 1) from ((m -1) ′ , 1)b = ((m -1) ′ , 2).

⊓ ⊔ Proposition 12. For m, n 4, let L ′ m (Σ ′ ) (respectively, L n (Σ)) be a nonreturning language of complexity m (respectively, n) over an alphabet Σ ′ , (respectively, Σ). Then the complexity of union and symmetric difference is mn + 1 and this bound is met by L ′ m (a, b, c) and L n (b, a, d); the complexity of difference is mn-n+1, and this bound is met by L ′ m (a, b, c) and L n (b, a); the complexity of intersection is mn -(m + n -2) and this bound is met by L ′ m (a, b) and L n (b, a).

Conclusions

We have shown that there exists a most complex non-returning language stream (L 4 (Σ), . . . , L n (Σ), . . . ). The cardinality of the syntactic semigroup of L n (Σ) is (n -1) n and its atoms have the highest state complexity possible for nonreturning languages; both of these bounds can be reached only if Σ has at least

Fig. 1 .

 1 Fig. 1. Most complex regular language Ln(a, b, c).

Fig. 2 .

 2 Fig. 2. Most complex non-returning language Ln(Σ) of Definition 1. The letters in Γ ′ = Σ \ {a, b, c, d} are omitted.

2

  letters are required to reach this bound. 2. Each quotient of L n (a) has complexity n -1, except L itself, which has complexity n. 3. The reverse of L n (a, b, c) has complexity 2 n , and at least three letters are needed to meet this bound. Moreover, L n (a, b, c) has 2 n atoms.

Proposition 8 (

 8 Star). Let D n (a, b) be the DFA of Definition 1 and let L n (a, b) be its language. Then the complexity of (L n (a, b)) * is 2 n-1 .

Proposition 11 (

 11 Restricted Boolean Operations). Let D n (a, b) be the DFA of Definition 1 and let L n (a, b) be its language. Then for m, n 4 and for any proper binary boolean operation • the complexity of L

′ m- 1

 1 (a, b) = ({1, . . . , (m -1) ′ }, {a, b}, δ ′ , 1 ′ , {(m -1) ′ }) and DFA E n-1 (b, a) = ({1, . . . , n -1}, {a, b}, δ, 2, {n -1}), where δ ′ and δ are δ m ′ and δ n restricted to Q ′ m \ {0 ′ } and Q n \ {0}. Since the transition semigroups of E ′ m and E n are the symmetric groups S m and S n , respectively, the result from [1, Theorem 1] applies, except in the cases where (m, n) is in {(4, 5), (5, 4), (5, 5)}, which have been verified by computation. Our first claim follows for the remaining cases by [1, Theorem 1]. If m = n, [1, Theorem 1] applies to D ′ m (a, b) and D n (a, b), and the second claim follows. In both cases the direct product of E ′ m and E n has (m -1)(n -1) states; hence in the direct product of D ′ m and D n there are (m -1)(n -1) + 1 = mn -(m + n -2) states. By [1, Theorem 1] all these states are reachable and pairwise distinguishable for every proper binary boolean operation •.

n 2

 2 letters. The bounds for the common restricted operations, however, can be met by streams over {a, b, c} or {a, b}:κ(L m (a, b) • L n (b, a) = mn -(m + n -2) for all proper boolean operations •; κ(L n (a, b)) * = 2 n-1 ; κ(L n (a, b, c) R ) = 2 n ; and κ(L ′ m (a, b)L n (a, -, b)) = (m -1)2 n-1 + 1.The bounds for unrestricted boolean operations can be met by L ′ m (a, b, c) and L n (b, a, d), whereas those for the unrestricted product, by L ′ m (a, b) and L n (a, -, b, d).

Fig. 3 .

 3 Fig. 3. DFAs D ′ m (a, b, c) and Dn(b, a, d) for unrestricted boolean operations.

Acknowledgments We are very grateful to Corwin Sinnamon and an anonymous reviewer for careful proofreading and constructive comments.

⋆ This work was supported by the Natural Sciences and Engineering Research Council of Canada grant No. OGP0000871.