Štěpán Holub
email: holub@karlin.mff.cuni.cz

Tomáš Masopust
email: masopust@math.cas.cz

Michaël Thomazo
email: michael.thomazo@inria.fr

On the Height of Towers of Subsequences and Prefixes $

Keywords: Automata, languages, alternating towers, subsequences, prefixes, upper and lower bounds 2010 MSC: 68R05, 68Q45

A tower is a sequence of words alternating between two languages in such a way that every word is a subsequence of the following word. The height of the tower is the number of words in the sequence. If there is no infinite tower (a tower of infinite height), then the height of all towers between the languages is bounded. We study upper and lower bounds on the height of maximal finite towers between two regular languages with respect to the size of the NFA (respectively the DFA) representation. Our motivation to study the bounds on maximal finite towers comes from a method to compute a piecewise testable separator of two regular languages. We show that the upper bound is polynomial in the number of states and exponential in the size of the alphabet, and that it is asymptotically tight if the size of the alphabet is fixed. If the alphabet may grow, then, using an alphabet of size approximately the number of states of the automata, the lower bound on the height of towers is exponential with respect to that number. In this case, there is a gap between the lower and upper bound, and the asymptotically optimal bound remains an open problem. Since, in many cases, the constructed towers are sequences of prefixes, we also study towers of prefixes.

Introduction

A tower between two languages is a sequence of words alternating between the languages in such a way that every word is a subsequence of the following word. The number of words in a tower is the height of the tower. As a consequence of a more general result [START_REF] Czerwiński | Efficient separability of regular languages by subsequences and suffixes[END_REF]Lemma 6], the existence of towers of arbitrary height implies the existence of an infinite tower. Therefore, if there is no infinite tower, the height of all towers is bounded.

Although we believe that the maximal height of towers between two regular languages is an interesting topic on its own, our motivation comes from the construction of a piecewise testable separator of two regular languages [START_REF] Czerwiński | Efficient separability of regular languages by subsequences and suffixes[END_REF][START_REF] Holub | On upper and lower bounds on the length of alternating towers[END_REF][START_REF] Place | Separating regular languages by piecewise testable and unambiguous languages[END_REF]. It was independently shown by Czerwiński et al. [START_REF] Czerwiński | Efficient separability of regular languages by subsequences and suffixes[END_REF] and Place et al. [START_REF] Place | Separating regular languages by piecewise testable and unambiguous languages[END_REF] that the non-separability by piecewise testable languages is equivalent to the existence of a common pattern in the two automata (called an (u, B)-path in Place et al. [START_REF] Place | Separating regular languages by piecewise testable and unambiguous languages[END_REF] and synchronized languages in Czerwiński et al. [START_REF] Czerwiński | Efficient separability of regular languages by subsequences and suffixes[END_REF]). This pattern is further equivalent to the existence of an infinite tower between the languages [START_REF] Czerwiński | Efficient separability of regular languages by subsequences and suffixes[END_REF], and its existence can be detected in polynomial time. Deciding piecewise testable separability is thus in PTime. The problem is also hard for PTime [START_REF] Masopust | Separability by piecewise testable languages is PTime-complete[END_REF]. A similar pattern has recently been identified for general word languages [START_REF] Czerwiński | A characterization for decidable separability by piecewise testable languages[END_REF].

To actually construct a separator is a more difficult problem. Place et al. [START_REF] Place | Separating regular languages by piecewise testable and unambiguous languages[END_REF] construct the separator as a union of ∼ κ -equivalence classes, where u ∼ κ v if and only if the words u and v have the same set of subsequences of length up to Upper bound Lower bound Table 1: Upper and lower bounds on the height of towers of subsequences and prefixes for automata with n and m states κ. The difficult part is to find a suitable κ. Place et al. [START_REF] Place | Separating regular languages by piecewise testable and unambiguous languages[END_REF] find such a κ that is exponential in the size of the automaton and doubly exponential in the size of the alphabet. The separator is then κ-piecewise testable and it can be constructed as the union of ∼ κ classes that cover one of the languages. Our present research is motivated by a different approach, which we briefly describe in Subsection 2.1. The relation between the maximal height of towers and the number κ of Place et al. is an interesting question. The number of classes of the equivalence relation ∼ κ indeed depends on κ and was investigated by Karandikar et al. [START_REF] Karandikar | On the index of Simon's congruence for piecewise testability[END_REF]. In Subsection 2.2, we show that, in some sense, κ provides an upper bound on the maximal height of towers, and that κ can be arbitrarily larger than the maximal height of towers.

|Σ| = k |Σ| ≥ n + m NFAs µ |Σ|+1 -1 µ -1 Θ µ k Ω (2 n+m ) DFAs
Not much is known about the upper bound on the height of towers between two regular languages if no infinite tower exists. The only result we are aware of is a result by Stern [START_REF] Stern | Characterizations of some classes of regular events[END_REF] giving an exponential upper bound 2 |Σ| 2 n on the height of towers between a piecewise testable language over an alphabet Σ represented by an n-state minimal DFA and its complement. In this paper, we give a better bound that holds in a general setting of two arbitrary regular languages (having no infinite tower) represented by NFAs. We show in Theorem 1 that the upper bound on the height of towers between two regular languages represented by NFAs is polynomial with respect to the depth of the NFAs and exponential with respect to the size of the alphabet.

Considering the lower bound, in Theorem 2 we first improve an existing bound for binary regular languages [START_REF] Holub | On upper and lower bounds on the length of alternating towers[END_REF]. Theorems 4 and 5 and Corollary 6 then show that the upper bound is asymptotically tight if the alphabet is fixed, for both NFAs and DFAs. If the alphabet may grow with the depth of the automata, Theorem 4 shows that we can achieve an exponential lower bound for NFAs with respect to the number of states. The same is shown for DFAs in Theorem 7. Notice that it does not contradict the polynomiality of the upper bound with respect to the number of states because the automata require an alphabet of size approximately the number of states. These lower bounds are not asymptotically equal to the upper bound and it is not known what the (asymptotically) tight bound is, cf. Open Problem 1. Specifically, we do not know whether an alphabet of size greater than the number of states may help to build higher towers. In Theorems 8 and 9, we show how to transform general NFAs to DFAs preserving the height of towers.

Surprisingly, it turns out that the towers we construct to demonstrate lower bounds are mostly sequences of prefixes. Therefore, we also investigate towers of prefixes. We provide a pattern that characterizes the existence of an infinite tower of prefixes in Theorem 10. We further prove tight bounds on the height of towers of prefixes in Theorem [START_REF] Stern | Characterizations of some classes of regular events[END_REF] for DFAs and in Theorem 16 for NFAs. We then discuss towers of prefixes between two binary NFAs in Corollary 17.

Our main results are summarized in Table 1. We also formulate the following two open problems:

Preliminaries

The cardinality of a set Σ is denoted by |Σ| and its power set by 2 Σ . The free monoid generated by Σ is denoted by Σ * . An element of Σ * is called a word; the empty word is denoted by ε. For a word w ∈ Σ * , alph(w) ⊆ Σ denotes the set of all letters occurring in w, and |w| a denotes the number of occurrences of letter a in w.

A nondeterministic finite automaton (NFA) is a quintuple A = (Q, Σ, δ, I, F), where Q is the finite nonempty set of states, Σ is the alphabet, I ⊆ Q is the set of initial states, F ⊆ Q is the set of accepting states, and δ : Q × Σ → 2 Q is the transition function that can be extended to the domain 2 Q × Σ * in the usual way. The language accepted by A is the set

L(A) = {w ∈ Σ * | δ(I, w) ∩ F ∅}.
A path π from a state q 0 to a state q n under a word a 1 a 2 • • • a n , for some n ≥ 0, is a sequence of states and input letters q 0 , a 1 , q 1 , a 2 , . . . , q n-1 , a n , q n such that q i+1 ∈ δ(q i , a i+1 ) for all i = 0, 1, . . . , n -1. The path π is accepting if q 0 ∈ I and q n ∈ F, and it is simple if the states q 0 , q 1 , . . . , q n are pairwise distinct. The number of states on the longest simple path in A is called the depth of A. We write q w -→ q to denote that q ∈ δ(q, w) and say that there exists a path from state q to state q under the word w, or labeled by the word w.

The NFA A has a cycle over an alphabet Γ ⊆ Σ if there exists a state q and a word w over Γ such that q w -→ q. A path π contains a cycle over Γ if q w -→ q is a subpath of π for some state q and alph(w) = Γ. The NFA A is deterministic (DFA) if |I| = 1 and |δ(q, a)| ≤ 1 for every q in Q and a in Σ. Note that we allow some transitions to be undefined. In the sequel, we consider only automata without useless states, that is, automata where every state appears on an accepting path. In other words, if it is necessary to add a sink state in order to obtain a complete automaton, such a sink state is not considered when counting the number of states.

For two

words v = a 1 a 2 • • • a n and w ∈ Σ * a 1 Σ * a 2 Σ * • • • Σ * a n Σ * , we say that v is a subsequence of w or that v can be embedded into w, denoted by v w. A word v ∈ Σ * is a prefix of w ∈ Σ * , denoted by v ≤ w, if w = vu for some u ∈ Σ * .
We define towers of subsequences as a generalization of Stern's alternating towers between a language and its complement [START_REF] Stern | Characterizations of some classes of regular events[END_REF]. For two languages L and R, a sequence (w i ) r i=1 of words is a tower of subsequences between L and R if w 1 ∈ L ∪ R and, for all i < r, 1. w i w i+1 , 2. w i ∈ L implies w i+1 ∈ R, and

3. w i ∈ R implies w i+1 ∈ L.
Similarly, a sequence (w i ) r i=1 of words is a tower of prefixes between L and R if w 1 ∈ L ∪ R and, for all i < r, w i ≤ w i+1 , w i ∈ L implies w i+1 ∈ R, and w i ∈ R implies w i+1 ∈ L.

The number of words in the sequence, r, is the height of the tower. If r = ∞, then we speak about an infinite tower between L and R. The languages L and R are not necessarily disjoint. However, if there is a word w ∈ L ∩ R, then there is a trivial infinite tower w, w, w, . . .. If the languages are clear from the context, we usually omit them. By a tower between two automata, we mean a tower between their languages.

In what follows, if we talk about towers without a specification, we mean towers of subsequences. If we mean towers of prefixes, we always specify it explicitly.

Computing a piecewise testable separator

In this section, we briefly describe our approach to compute a piecewise testable separator that motivates the investigation of this paper.

For

a word w = a 1 a 2 • • • a , where a i ∈ Σ, let up(w) denote the language Σ * a 1 Σ * a 2 Σ * • • • Σ * a Σ * of
all supersequences of w (the upward closure). For a language L, let up(L) = w∈L up(w). Then up(L) = w∈M L up(w), where M L is the set of minimal elements of L with respect to , which is finite by Higman's Lemma [START_REF] Higman | Ordering by divisibility in abstract algebras[END_REF]. A regular language is piecewise testable if it is a finite boolean combination of upward closures of some words. Then, up(L) is piecewise testable for any L. If the words used in the boolean combination are of length at most k, then the language is called k-piecewise testable.

Let L and R be two disjoint languages over Σ. To construct a piecewise testable language K ⊇ L disjoint from R (called a piecewise testable separator), we choose up(L) as the first approximation of K. Typically, up(L) is not disjoint from R and, therefore, we try to fix it by putting R 1 = up(L) ∩ R and taking K 0 = up(L) \ up(R 1 ). Although K 0 is obviously disjoint from R, it may not be a superset of L, namely if L 1 = L ∩ up(R 1 ) is not empty. We therefore repeat the construction for L 1 , and construct another "layer" of K defining R 2 = up(L 1 ) ∩ R and K 1 = up(L 1 ) \ up(R 2 ). In this way, we obtain a sequence K 0 , K 1 , K 2 , . . . of piecewise testable sets defined by L 0 = up(L) and by

R i+1 = up(L i ) ∩ R, L i+1 = up(R i+1 ) ∩ L, K i = up(L i ) \ up(R i+1 ) .
Finally we define K = i≥0 K i . Definitions imply that w ∈ R i+1 if and only if there is a tower w 1 w 1 w 2 w 2 • • • w i w i = w between L and R. Therefore, if the maximum height of a tower between L and R is r ≤ 2 j -1, then R j+1 is empty. Then K j = up(L j ) and K = j i=0 K i is the piecewise testable separator we are looking for. Notice that the complexity of the above construction depends on the maximal height of the tower between L and R, which motivates our study on the upper and lower bounds on the height of finite towers.

The height of towers versus the number κ

Recall that Place et al. [START_REF] Place | Separating regular languages by piecewise testable and unambiguous languages[END_REF] construct a number κ for which the separator is κ-piecewise testable. In this section, we show that the number κ provides, in some sense, an upper bound on the maximal height of towers, and that κ can be arbitrarily larger than the maximal height of towers.

We first show that the maximal height of finite towers is bounded by the number of classes of the relation ∼ κ . Let L and R be two separable regular languages, and let κ be such that every class of the relation ∼ κ has a nonempty intersection with at most one of the languages L and R. Let w 1 w 2 w 3 be a part of a tower, where w 1 , w 3 ∈ L, w 2 ∈ R, and w 1 ∼ κ w 3 be two elements of the tower that belong to the same ∼ κ -class. Let sub κ (w) denote all subsequences of w of length up to κ. Then sub κ (w 1 ) ⊆ sub κ (w 2 ) ⊆ sub κ (w 3 ) = sub κ (w 1 ) implies that w 1 ∼ κ w 2 . This means that both w 1 and w 2 belong to the same class of the ∼ κ relation, and hence this class has a nonempty intersection with both L and R, which is a contradiction. Thus, every ∼ κ -class contains at most one element of the tower.

To show that κ can be arbitrarily larger than the height of the maximal finite tower, let c be a constant, and let L 1 = {w | |w| = c} and L 2 = {w | |w| = 2c} be two languages over {0, 1}, where the DFA representations have c + 1 and 2c + 1 states. Then the height of the maximal tower is two and our algorithm computes a piecewise testable separator K = {w | c ≤ |w| < 2c} = up(L 1 ) \ up(L 2 ) in one step using time that is easily seen to be polynomial in c. On the other hand, the optimal κ is c + 1. Therefore, the method of Place et al. [START_REF] Place | Separating regular languages by piecewise testable and unambiguous languages[END_REF] needs to check 2 Θ(c log c) classes in order to construct the separator [START_REF] Karandikar | On the index of Simon's congruence for piecewise testability[END_REF]. This also illustrates the fact that L 1 being piecewise testable itself is not helpful in general. Indeed, deciding whether the language of an NFA is κ-piecewise testable is a PSpace-complete problem even if the NFA is of a very restricted form [START_REF] Masopust | Deciding universality of ptNFAs is PSpace-complete[END_REF].

The height of towers versus the number of words in the boolean combination defining separators

The complexity of a separator K can also be measured by the number of elementary languages of the form up(w) needed in the boolean expression defining K. Let F be the set of words such that K is a boolean combination of languages up(w), where w ∈ F. For each word u ∈ Σ * , the truth value of u ∈ K is determined by the set

σ(u) = {w ∈ F | u ∈ up(w)}. In particular, σ(u) = σ(v) implies that u ∈ K if and only if v ∈ K.
Observe that u u implies that σ(u) ⊆ σ(u ). We now deduce that σ(w 1 ) σ(w 2 ) • • • σ(w r ) ⊆ F for any tower (w i ) r i=1 between two languages L and R, and hence |F| ≥ r -1. 4 This means that any such a boolean expression requires at least as many elements as is the height of the maximal tower. The required number of elements then follows from our lower-bound results.

Upper bound on the height of towers of subsequences

Let two languages over Σ be given, represented as NFAs with n and m states. As already mentioned in the introduction, it is known that there is either an infinite tower between the languages, or the height of towers is bounded [START_REF] Czerwiński | Efficient separability of regular languages by subsequences and suffixes[END_REF].

We now estimate that bound in terms of µ = max{n, m} and k = |Σ|. Stern's bound for minimal DFAs is 2 k 2 µ . Our new bound is O µ k = O 2 k log µ and holds for NFAs. Consequently, if the alphabet is fixed, our bound is polynomial with respect to the number of states; otherwise, it is exponential in the size of the alphabet.

Before stating our upper-bound result, we recall that the depth of an automaton is the number of states on the longest simple path, and hence it is bounded by the number of states of the automaton. Theorem 1. Let A 0 and A 1 be NFAs with n and m states, respectively, over an alphabet Σ. Assume that there is no infinite tower between the languages L(A 0 ) and L(A 1 ), and let (w i ) r i=1 be a tower between the languages such that w i ∈ L(A i mod 2 ). Let 1 < µ ≤ max(n, m) denote the maximum of the depths of A 0 and A 1 . Then r ≤ µ |Σ|+1 -1 µ-1 . Proof. To prove the upper bound, we assign to each w i of the tower an integer W i in such a way that 0

≤ W 1 < W 2 < • • • < W r < µ |Σ|+1 -1 µ-1 .
To this aim, we define a factorization of w r using an accepting path of w r in A r mod 2 . Then we inductively define factorizations of all w i , 1 ≤ i < r, depending on an accepting path of w i in A i mod 2 and on the factorization of w i+1 . The value of W i is derived from these factorizations.

We now define the concepts we need in the proof. We say that a sequence

(v 1 , v 2 , . . . , v k ) of nonempty words is a cyclic factorization of w = v 1 v 2 • • • v k
with respect to some path π from a state q to a state q under w in an automaton A if π can be decomposed into q i-1 v i -→ q i , i = 1, 2, . . . k, and either v i is a letter, or the path q i-1 v i -→ q i contains a cycle over alph(v i ). We call v i a letter factor if it is a letter and q i-1 q i , and a cycle factor otherwise. Note that our cyclic factorization is closely related to the factorization by Almeida [START_REF] Almeida | Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon[END_REF], see also Almeida [2,Theorem 8.1.11], and also to factorizations used in [START_REF] Place | Separating regular languages by piecewise testable and unambiguous languages[END_REF].

We now show that if π is a path q w -→ q in some automaton A with depth µ, then w has a cyclic factorization (v 1 , v 2 , . . . , v k ) with respect to π that contains at most µ cycle factors and at most µ -1 letter factors. Moreover, if k > 1, then alph(v i ) is a strict subset of alph(w) for each cyclic factor v i , i = 1, 2, . . . , k. We call such a cyclic factorization nice. By convention, the empty sequence is a nice cyclic factorization of the empty word with respect to the empty path.

Consider a path π of the automaton A from q to q labeled by a word w. Let q 0 = q and define the factorization (v 1 , v 2 , . . . , v k ) inductively by the following greedy strategy. Assume that we have defined the factors

v 1 , v 2 , . . . , v i-1 such that w = v 1 • • • v i-1 w and q 0 v 1 v 2 •••v i-1
-------→ q i-1 . The factor v i is defined as the label of the longest possible initial segment π i of the path q i-1 w -→ q such that either π i contains a cycle over alph(v i ) or π i = q i-1 , a, q i , where v i = a is a letter. Such a factorization is well defined, and it is a cyclic factorization of w.

Let p i , for i = 1, 2, . . . , k, be a state such that the path q i-1 v i -→ q i contains a cycle p i → p i over the alphabet alph(v i ) if v i is a cycle factor, and p i = q i-1 if v i is a letter factor. If p i = p j with i < j such that v i and v j are cycle factors, then we have a contradiction with the maximality of v i since q i-1

v i v i+1 •••v j ------→ q j contains a cycle p i → p i from p i to p i over the alphabet alph(v i v i+1 • • • v j ).
Therefore, the factorization contains at most µ cycle factors.

Note that v i is a letter factor only if the state p i , which is equal to q i-1 in such a case, has no reappearance in the path q i-1

v i •••v k ----→ q . This implies that there are at most µ -1 letter factors. Finally, if alph(v i ) = alph(w) for a cyclic factor v i , then v i = v 1 = w follows from the maximality of v 1 . Therefore (v 1 , v 2 , . . . , v k ) is a nice cyclic factorization of w.
We are now ready to execute the announced strategy. Let v r,1 , v r,2 , . . . , v r,k r be a nice cyclic factorization of w r with respect to some accepting path in the automaton A r mod 2 . Given a (not necessarily nice) cyclic factorization

(v i,1 , v i,2 , . . . , v i,k i ) of w i , i = 2, 3, . . . , r, the factorization v i-1,1 , v i-1,2 , . . . , v i-1,k i-1 of w i-1 is defined as follows. Let w i-1 = v i,1 v i,2 • • • v i,k i ,
where v i, j v i, j for each j = 1, 2, . . . , k i . Such words (possibly empty) exist, since we have that w i-1 w i . Let π i, j be paths under v i, j that together form an accepting path of w i-1 in A i-1 mod 2 . Then

(v i-1,1 , v i-1,2 , . . . , v i-1,k i-1 ) = k i j=1 v i, j,1 , v i, j,2 , . . . , v i, j,m i, j ,
where v i, j,1 , v i, j,2 , . . . , v i, j,m i, j is a nice cyclic factorization of v i, j with respect to π i, j and the product denotes the concatenation of sequences. Note that if v i, j is a letter factor of w i then either m i, j = 0 (if v i, j is empty) or m i, j = 1 and v i, j,1 is a letter factor of w i-1 .

To define W i , let g be the function g(x) = µ µ x -1 µ-1 , and let f (v i, j ) = 1 if v i, j is a letter factor, and f (v i, j ) = g alph(v i, j ) if v i, j is a cycle factor. We now set

W i = k i j=1 f v i, j .
The key property of g is that g(x + 1) = µ • g(x) + (µ -1) + 1. (In fact, this equality and g(0) = 0 defines g.) The definition of a nice factorization implies that if

(v 1 , v 2 , . . . , v k ) is a nice factorization of w with k > 1, then k i=1 f (v i ) ≤ µ • g alph(w) -1 + (µ -1) < g alph(w) .
Applying this to the nice factorizations defined above, we obtain

m i, j =1 f v i, j, ≤ f v i, j (1)
for all i = 2, 3, . . . , r and j = 1, 2, . . . , k i . In particular,

W r = k r =1 f v r, ≤ g alph(w r ) ≤ g(|Σ|) < g(|Σ|) + 1 = µ |Σ|+1 -1 µ -1 . (2)
Moreover, we have equality in (1) if and only if m i, j = 1, alph v i, j = alph v i, j,1 , and both v i, j and v i, j,1 are either letter factors, or cyclic factors. We deduce that W i-1 ≤ W i , i = 2, 3, . . . , r, and, moreover, W i-1 = W i if and only if

• k i-1 = k i , • alph(v i, j ) = alph(v i-1, j
) for all j = 1, 2, . . . , k i , and

• for all j = 1, 2, . . . , k i , v i, j is a letter factor if and only if v i-1, j is a letter factor.

We show that if these conditions are met for some i, then there is an infinite tower between A 0 and A 1 . Let Z be the language of words z 1 z 2 • • • z k i such that z j = v i, j if v i, j is a letter factor, and z j ∈ (alph(v i, j )) * if v i, j is a cycle factor. In particular, w i , w i-1 ∈ Z. Since w i ∈ L(A i mod 2 ) and w i-1 ∈ L(A i-1 mod 2 ), the definition of a cycle factor implies that, for each z ∈ Z, there exist z ∈ L(A 0 ) ∩ Z such that z z and z ∈ L(A 1 ) ∩ Z such that z z . The existence of an infinite tower follows. As a trivial case, consider the situation where all factors in question are letter factors. Then w i = w i-1 , and the languages are not disjoint, which yields the infinite tower consisting of the shared word. As a more complicated example, assume that k i-1 = k i = 2, and let w i-1 = cab • b, w i = aabbcc • b be the corresponding nice factorizations where factors cab and aabbcc are cyclic with cycles labeled with cab and abbc. Then (cab) * b ⊆ L(A i-1 mod 2 ) and a(abbc) * c b ⊆ L(A i mod 2 ). The infinite tower is now for example cabb a(abbc) 3 cb (cab) 13 b a(abbc) 39 cb • • • .

We have therefore proved that W i-1 < W i , which together with (2) completes the proof.

The question is how good this bound is. We study this question next and show that it is tight if the alphabet is fixed. If the alphabet grows with the number of states of the automata, then we can construct a tower of exponential height with respect to the number of states of the automata (as well as with respect to the size of the alphabet). However, we do not know whether this bound is tight. We formulate this question as the following open problem asking how much the size of the alphabet can increase the height of the tower, given the number of states (or the depth). In Theorem 1, the alphabet plays an important role. It is a natural and very intriguing question, what the potential of the alphabet really is.

Open Problem 1. Let A 0 and A 1 be NFAs with n and m states, respectively, over an alphabet Σ with |Σ| ≥ n + m. Let µ be the maximum depth of A 0 and A 1 . Assume that there is no infinite tower between the languages L(A 0 ) and L(A 1 ), and let (w i ) r i=1 be a tower between them. Is it true that r ≤ µ n+m+1 -1 µ-1

or even that r ≤ 2 n+m ?

Lower bounds on the height of towers

The upper bound of Theorem 1, as well as its proof, indicate that the size of the alphabet is significant for the height of towers. This is confirmed by lower bounds considered in this section. We consider two cases, namely (i) the size of the alphabet is fixed and (ii) the size of the alphabet may grow with the size of the automata. We show that the upper bound of Theorem 1 is asymptotically tight if the size of the alphabet is fixed, and that the lower bound may be exponential with respect to the size of the automata if the alphabet may grow. In this case, the size of the alphabet is approximately the number of states of the automata. However, the precise upper bound for this case is left open, cf. Open Problem 1.

To warm up, we start with the binary alphabet. The upper bound of Theorem 1 gives n 2 + n + 1 in this case, and it is known to be tight up to a linear factor [START_REF] Holub | On upper and lower bounds on the length of alternating towers[END_REF]. Namely, for every odd positive integer n, there are two binary NFAs with n -1 and n states having a tower of height n 2 -4n + 5 and no infinite tower. We now improve this bound. We show that there is no higher tower between the languages, in particular, there is no infinite tower. Notice that any word in L(B e ) is a prefix of a word in (b e a) * . As the languages are disjoint (they require a different parity of the b-tail), any tower (w i ) r i=1 is strictly increasing with respect to and thus |w i | ≥ i -1. Thus if the height of (w i ) r i=1 is larger than d(e + 1) + 2 the word w d(e+1)+1 or w d(e+1)+2 is in L(B e ) and therefore contains at least d occurrences of letter a. However, no such word can be embedded into a word of L(A d ), since each word of L(A d ) contains at most d -1 occurrences of letter a.

As a consequence of Theorem 2, we obtain the following lower bound on the height of binary towers. Corollary 3. For every even positive integer n, there exists a binary NFA with n states and a binary DFA with n states having a tower of height n 2n + 2 and no infinite tower.

Proof. Set d = e = n -1 in Theorem 2.
The construction used in Theorem 2 reveals the main mechanism behind high towers. The automaton A d bounds the number of possible occurrences of letter a (by d -1) but it is very generous concerning letter b. On the other hand, the automaton B e requires at least one a for each sequence of e occurrences of letter b. This general strategy is employed in a more complicated way in the following two theorems, which eventually allow to show that the upper bound from Theorem 1 is asymptotically tight, even for deterministic automata.

Theorem 4. For all integers n, m ≥ 2 there exist two NFAs with n and m states over an alphabet of cardinality n+m-2 having a tower of height 2 n+m-2 -2 m-2 + 1 and no infinite tower.

Proof. For k ≥ 0, let Σ k = {b, a 1 , a 2 , . . . , a k } and Γ k = {c 1 , c 2 , . . . , c k } be alphabets (with Σ 0 = {b} and Γ 0 = ∅). We define two NFAs A n,m and B n,m over Σ n-1 ∪ Γ m-2 as follows.

The set of states of the NFA A n,m is Q n = {0, 1, 2, . . . , n -1}. All states are initial, and state 0 is the unique accepting state. The transition function of A n,m consists of • a self-loop under Σ j-1 for all states j with j > 0,

• an a i -transition i to j if 0 ≤ j < i, and

• transitions under Γ m-2 from state 0 to each state j > 0.

The NFA A 5,m is shown in Figure 2. The NFA B n,m has the state set Q m = {0, 1, 2, . . . , m -2} ∪ {0 B }. All states are initial, except for state 0 B , which, in turn, is the unique accepting state. The transitions of B n,m consist of • self-loops under Σ n-1 ∪ Γ j-1 for all states j with j > 0, and of self-loops under Σ n-1 in state 0,

0 1 2 3 4 a 4 a 3 a 2 a 1 b, a 1 , a 2 , a 3 b, a 1 , a 2 b, a 1 b a 4 a 4 a 4 a 3 a 3 a 2 Γ m-2 Γ m-2 Γ m-2 Γ m-2
• a c i -transition from i to j if 0 ≤ j < i, and from i to 0 B , and

• transitions under Γ m-2 ∪ {b} from 0 to 0 B .
The NFA B n,6 is shown in Figure 3.

We now define a word u n+m-3 b such that all its prefixes form a tower. To do this, we first inductively define a word u n-1 so that u 0 = ε and

u k = u k-1 ba k u k-1 for 0 < k < n. Then u k ∈ Σ * k and |u k | = 2 k+1 -2. We now use the word u n-1 to define, for 0 < p ≤ m -2, a word u n+p-1 = u n+p-2 c p u n+p-2 . Then u n+p-1 ∈ (Σ n-1 ∪ Γ p ) * and |u n+p-1 | = 2 n+p -2 p -1.
Finally, the word u n+m-3 b is of length 2 n+m-2 -2 m-2 , therefore it has 2 n+m-2 -2 m-2 + 1 prefixes.

We now show that the prefixes of u n+m-3 b form a tower between the languages. Namely, we show by induction on p that every prefix v of u n+p-1 b is accepted by A n,m if it ends with a letter from Σ n-1 \ {b}, and it is accepted by B n,m from a state smaller than p + 1 if it ends with a letter from Γ m-2 ∪ {b}.

For p = 0, any prefix v of u n-1 b ending with b is accepted by B n,m from state 0. The empty word is accepted by A n,m in 0. If v is nonempty and ending with a letter from

Σ n-1 \ {b}, then it is of the form v = u k-1 ba k v with k > 0 0 1 2 3 4 0 B c 4 c 3 c 2 c 1 Γ m-2 ∪ {b} Σ n-1 ∪ Γ 3 Σ n-1 ∪ Γ 2 Σ n-1 ∪ Γ 1 Σ n-1 Σ n-1 c 4 c 4 c 4 c 4 c 3 c 3 c 3 c 2 c 2 c 1 Figure 3: Automaton B n,6 of Theorem 4
where v is a prefix of u k-1 . We show by induction on |v| that v is accepted by A n,m from state k. By the induction hypothesis, v is accepted by A n,m from some state k < k. Then v is accepted by A n,m by the path

k u k-1 b -----→ k a k ---→ k v --→ 0 .
In particular, u n-1 is accepted by A n,m from the state n -1.

Let now p ≥ 1 and consider the word u n+p-1 b. By induction, the claim holds for prefixes of u n+p-2 b and u n+p-2 is accepted in A n,m from state n -1. Let v be a prefix of u n+p-1 b of the form u n+p-2 c p v where v is a prefix (possibly empty) of u n+p-2 b. If v ends with a letter from Σ n-1 \ {b}, then A n,m accepts v from a state k by the induction hypothesis. Then the whole prefix v is accepted in A n,m by the path

n -1 u n+p-2 -----→ 0 c p ---→ k v --→ 0 .
If v ends with a letter from Γ p ∪ {b}, then it is accepted by B n,m from a state p < p by the induction hypothesis. Then the whole prefix v is accepted by B n,m by the path

p u n+p-2 -----→ p c p ---→ p v --→ 0 .
This shows the claimed height of the tower.

It remains to show that there is no infinite tower. We first show that there is no infinite tower over the alphabet Σ n-1 and then that there is no infinite tower over the alphabet Σ n-1 ∪ Γ m-2 . Suppose the contrary, and let k ≥ 0 be the smallest integer such that there is an infinite tower over Σ k . Since ε, b is the highest tower over Σ 0 , we have k ≥ 1. Since every word of L(A n,m ) ∩ Σ * k contains at most one occurrence of the letter a k , we can consider, without loss of generality, an infinite tower (w i ) ∞ i=1 in which every w i contains exactly one occurrence of a k . Let w i = w i a k w i , where w i , w i ∈ Σ * k-1 . Since all transitions under a k lead to an initial state in both automata, the word w i is accepted by A n,m (by B n,m resp.) if w i is accepted by A n,m (by B n,m resp.). Then (w i ) ∞ i=1 is an infinite tower over Σ k-1 ; a contradiction. Thus, let p ≥ 1 be the smallest integer such that there is an infinite tower over Σ n-1 ∪ Γ p . Similarly as above, since each word from (Σ n-1 ∪ Γ p ) * accepted by the automaton B n,m contains at most one occurrence of c p , we can choose an infinite tower (w i ) ∞ i=1 such that all words have exactly one occurrence of the letter c p . Let w i = w i c p w i with w i , w i ∈ (Σ n-1 ∪ Γ p-1 ) * . A direct inspection of the automata yields that w i is accepted by A n,m (by B n,m resp.) if w i is accepted by A n,m (by B n,m resp.). Then (w i ) ∞ i=1 is an infinite tower over Σ n-1 ∪ Γ p-1 ; a contradiction.

Remark 1.

As pointed out, the tower constructed in the previous proof is actually a tower of prefixes. Theorem 4 therefore still holds if "tower" is replaced with "tower of prefixes".

The following theorem adapts the previous construction for deterministic automata. • an a i -transition from each (i, j) to (i, j -1), and from (i, 0) to states (i -1, d -1) if i > 1 and j > 0,

• an a 1 -transition from (1, j ) to (1, j -1) if 1 ≤ j ≤ d -1,

• a transition from (i, d -1) to i and back under a

1 if i ≥ 2,
• a b-transition from (1, j) to (1, j ) and back if 0 ≤ j ≤ d -1,

• self-loops in (i, j) under Σ i-1 if i ≥ 2 and 0 ≤ j ≤ d -2, and

• self-loops under a i in states i if i ≥ 2.
See Figure 4 for an example. The DFA B k,e has the states {0, 1, . . . , e}. State 0 is initial and states with odd numbers are accepting. The transitions of B k,e contain b-transitions from state i to state i+1 for each 0 ≤ i ≤ e-1, a transition under {a 1 , a 2 , . . . , a k } from state e to state 0, and a self-loop in state 0 under {a 1 , a 2 , . . . , a k }, see Figure 5 for an illustration. Since w k-1, ∈ Σ * k-1 , it is straightforward to verify that, for each j = 0, . . . , d -1, the word u k, j is a label, in A k,d , of a path from (k, d -1) to (k -1, d -1): if j = 0, then (k, d -1)

1, 0 1, 0 1, 1 1, 1 2, 0 2, 1 2 3, 0 3, 1 3 b b b b a 1 a 1 a 1 a 1 a 3 a 3 a 2 a 2 a 1 Σ 2 Σ 1 a 2 a 3
Σ k \ {b} Σ k \ {b}
a d k ---→ (k -1, d -1) ,
and if 0 < j, then the path is

(k, d -1) (a 1 a k a 1 ) j -------→ (k, d -1) a d-j k ----→ (k, j -1) (w k-1, a k ) j --------→ (k -1, d -1) .
In B k,e , each u k, j is a label for a cycle starting and ending in the state 0; namely, 0

(a 1 a k a 1 ) j a d-j k ----------→ 0 w k-1, -----→ e a k ---→ 0 j-times .
This implies, by induction and by the construction of the automata, that w k,i are accepted as required. By induction, we have that w k, j +m w k, j +m+1 for each 1 ≤ m < , and the definition of u k, j implies that also

w k, j = (a 1 a k a 1 ) j-1 a d-j+1 k w k-1, a k j-1 w k-1, (a 1 a k a 1 ) j a d-j k w k-1, a k j w k-1,1 = w k, j +1 .
This completes the proof that (w k,i ) d i=1 is a tower with required properties. It remains to show that there is no infinite tower. For k = 1, the proof is similar to the corresponding part of Theorem 2. Namely, any word from L(A 1,d ) contains at most d occurrences of a 1 . Looking at B k,e , we obtain an upper bound on the length of words in the tower. For the sake of contradiction, let now k > 1 be the smallest number such that there exists an infinite tower (w i ) ∞ i=1 between A k,d and B k,e for some d and e. Suppose, first, that for all i, w i ∈ {a 1 , a k } * w i where w i ∈ Σ * k-1 . We may assume that a 1 is not the first letter of w i . This implies that after reading the

{a 1 , a k } * part, A k,d is in (k -1, d -1) and that B k,e is in 0. Thus (w i ) ∞
i=1 is an infinite tower between A k-1,d and B k-1,e ; a contradiction. Let now t > 1 be the largest integer such that a word ca t k w i for some i, where c ∈ Σ k \ {a 1 , a k }. It is straightforward to verify that ca d k cannot be embedded into any word from L(A k,d ), hence t < d. Without loss of generality, we can suppose that ca t k w i for all i. Let w i = w i w i where w i is the shortest prefix of w i , such that ca t k w i . Then w i ∈ Σ * k-1 , and (w i ) ∞ i=1 is again a tower between A k-1,d and B k-1,e ; a contradiction. As a corollary, we have that the upper bound of Theorem 1 is tight for a fixed alphabet even for DFAs. Corollary 6. Let k ≥ 2 be a constant. Then the maximum height of a tower between two DFAs with at most n states over an alphabet of cardinality k having no infinite tower is in Ω n k .

Proof. For a sufficiently large n, let k = k -1, d = n-k k , and n -2 ≤ e ≤ n -1. Theorem 5 then implies that there exist two DFAs with at most n states having a tower of height at least (n -1)d k + 2d k -1 ∈ Ω n k , and no infinite tower.

We remark that Corollary 6 in particular improves our former bound Ω(n 3 ) for a four-letter alphabet [START_REF] Holub | On upper and lower bounds on the length of alternating towers[END_REF]Theorem 3].

Theorem 4 shows that the height of a tower can be exponential in the number of states of NFAs, if the alphabet is allowed to grow with the number of states. For DFAs with at most n states, Theorem 5 yields the height of a tower Ω (n + 1)2 n/3 (for d = 2, k = (n -1)/3 and e = n -1). To obtain a better lower bound for DFAs, we combine Theorem 4 with a "determinization" strategy.

Theorem 7. For every n ≥ 0, there exist two DFAs with at most n + 1 states over an alphabet of cardinality n(n+1) 2 + 1 having a tower of height 2 n and no infinite tower.

Proof. For a given integer n, we define a pair of deterministic automata A n and B n with n + 1 and two states, respectively, over the alphabet Σ n = {b} ∪ {a i, j | i = 1, 2, . . . , n; j = 0, 1, . . . , i -1} with a tower of height 2 n between L(A n ) --→ j. Then the tower of Theorem 4 is modified by relabeling the corresponding letters. However, to preserve embeddability of the new letters, several self-loops must be added.

0 1 2 3 a 1,0 b a 2,0 , a 3,0 b, a 1,0 , a 3,0 , a 3,1 b, a 1,0 , a 2,0 , a 2,1 a 2,0 a 2,1 a 3,2 a 3,1 a 3,0 1 2 Σ n \ {b} b b Σ n \ {b}
Formally, the transition function δ n is defined as follows. For every a i, j ∈ Σ n , we define the transition δ n (i, a i, j ) = j. For every k = 1, 2, . . . , n and a i, j ∈ Σ n such that i k and j < k, we define the self-loop δ n (k, a i, j ) = k. Finally, we add the self-loops δ n (k, b) = k to every state k = 1, 2, . . . , n, see Figures 6 and7 for an illustration.

For every 1 ≤ k ≤ n and 0 ≤ j < k, let α k, j = a k, j a k, j-1 • • • a k,0 , and let the words u k be defined by u 0 = ε and

u k = u k-1 b α k,k-1 u k-1 . Note that u k b contains 2 k letters b.
We first give an informal description of the tower of height 2 n between A n and B n , which relates the construction to Theorem 4. The tower is the sequence w n (0), w n (1), . . . , w n (2 n -1), where the longest word w n (2 n -1) is α n,n-1 u n-1 b ∈ L(B n ). The word w n (2i) is obtained from the word w n (2i+1) by removing the last letter, which is b. The word w n (2i-1) is obtained from the word w n (2i) by removing the first letter of some occurrences of α k, j in w n (2i), see Figure 8 for the case n = 3.

We now give a formal definition of w n (i), which is done recursively. For any k ≥ 1, we define w k (0

) = α k,0 = a k,0 and w k (1) = a k,0 b. For 2 ≤ i ≤ 2 k -1, let w k (i) = α k, log i u log i -1 b w log i i -2 log i . (3)
We first show that holds for each k and each 1 ≤ ≤ k. This is true for = 1. For > 1, we have from (3) and by induction

w k 2 -1 = α k, -1 u -1 b (4) 0 1 2 3 4 a 1,0 b a 2,0 , a 3,0 , a 4,0 b a 3,1 , a 4,1 , a 1,0 , a 3,0 , a 4,0 b a 4,2 a 2,1 , a 4,1 , a 1,0 , a 2,0 , a 4,0 b a 3,2 a 2,1 , a 3,1 , a 1,0 , a 2,0 , a 3,0 a 2,0 a 2,1 a 3,2 a 3,1 a 3,0 a 4,3 a 4,2 a 4,1 a 4,0 Figure 7: Automaton A 4 of Theorem 7 w 3 (0) = a 3,0 w 3 (1) = a 3,0 b w 3 (2) = a 3,1 a 3,0 b a 1,0 w 3 (3) = a 3,1 a 3,0 b a 1,0 b w 3 (4) = a 3,2 a 3,1 a 3,0 b a 1,0 b a 2,0 w 3 (5) = a 3,2 a 3,1 a 3,0 b a 1,0 b a 2,0 b w 3 (6) = a 3,2 a 3,1 a 3,0 b a 1,0 b a 2,1 a 2,0 b a 1,0 w 3 (7) = a 3,2 a 3,1 a 3,0 b a 1,0 b a 2,1 a 2,0 b a 1,0 b
w k 2 -1 = α k, -1 u -2 b w -1 2 -1 -1 = α k, -1 u -2 b α -1, -2 u -2 b = α k, -1 u -1 b .
By double induction on n and i, we now prove that the sequence (w n (i)) 2 n -1 i=0 is the required tower. For n = 1, the claim holds, and the tower is

w 1 (0) = a 1,0 , w 1 (1) = a 1,0 b. Let n > 1.
The definition implies, by induction, that w n (i) is in L(B n ) (that is, it ends with b) if and only if i is odd. Consider w n (i) with even i ≥ 2. Using (3), we show that there is a path in A n labeled by w n (i) and it can be decomposed as

n a n, log i ------→ log i α n, log i -1 u log i -1 b ---------------→ log i w log i i-2 log i -------------→ 0 .
For the second segment of the path, note that both the alphabet of α n, log i -1 and the alphabet {b} ∪ {a m,m | m ≤ log i -1, m < m} of u log i -1 b are contained in the alphabet of self-loops of state log i . The last segment exists by induction, since log i < n, i -2 log i ≤ 2 log i -1, the automaton A log i is a restriction of A n , and i -2 log i is even.

We show that w n (i) w n (i + 1). This is true for i = 0, and follows by induction from (3) if log(i + 1) = log i . The latter equality holds unless i is of the form 2 -1 for some > 1. If i = 2 -1, then -1 = log i log(i + 1) = and we have from ( 4)

w n 2 -1 = α n, -1 u -1 b, w n 2 = α n, u -1 b w (0) = α n, u -1 b a ,0 , hence w n 2 -1
w n 2 holds. Finally, observe that if (v i ) i is a tower between A n and B n , then (P(v i ) i ) is a tower between A n,0,1 and B n,0,1 of Theorem 4, where P : a k, j → a k is the natural projection. Therefore there is no infinite tower between A n and B n .

The "determinization" idea of the previous theorem can be generalized. However, compared to the proof of Theorem 7, the general procedure suffers from the increase of states (see Figure 9). The reason why we need not increase the number of states in the proof of Theorem 7 is that the automata we are "determinizing" are such that there is an order in which the transitions/states are used/visited, and that the nondeterministic transitions are acyclic. Theorem 8. For every two NFAs A and B with at most n states and k input letters, there exist two DFAs A and B with O n 2 states and O (k + n) input letters such that there is a tower of height r between A and B if and only if there is a tower of height r between A and B . In particular, there is an infinite tower between A and B if and only if there is an infinite tower between A and B . Proof. Let A and B be two NFAs with at most n states over an alphabet Σ of cardinality k. We first add a unique initial state, if necessary, to the automata A and B and the corresponding transitions in the standard way. Assume now that A and B have a unique initial state, and let Q A and Q B denote their respective sets of states. We modify the automata A and B to obtain the DFAs A and B as follows. Let We now prove that if there is a tower of height r between A and B, then there is a tower of height r between A and B . Informally, given a tower between A and B, in order to obtain a tower between A and B , a sequence of "directing" symbols is inserted before each letter in the tower. "Directing" symbols record the list of transitions the corresponding letter will be responsible for in the rest of the tower. Formally, let (w i ) r i=1 be a tower between A and B.

Q A = Q A ∪ {σ s,t | s, t ∈ Q A } and Q B = Q B ∪ {σ s,t | s, t ∈ Q B },
Let = |w r | and w r = x r,1 x r,2 • • • x r, ,
with x r, j ∈ Σ. Next, for i = 1, 2, . . . , r -1, let

w i = x i,1 x i,2 • • • x i,
where x i, j is either a letter or the empty word such that x i, j x i+1, j for each i = 1, 2, . . . , r -1 and j = 1, 2, . . . , . For every w i , we fix an accepting path π i in the corresponding automaton. Let p i, j be the letter y t where s -→ t is the transition corresponding to x i, j in π i if x i, j is a letter, and let p i, j be empty if x i, j is empty. We define

w i = α i,1 α i,2 • • • α i,
where α i, j = p i, j p i-1, j • • • p 1, j x i, j if x i, j ε, and α i, j = x i, j = ε otherwise. It is straightforward to verify that w i r i=1 is a tower of height r between A and B .

Let now w i r i=1 be a tower between A and B . We show that P w i r i=1 is a tower between A and B, where P is a projection erasing all new letters. Obviously, we have P w i P w i+1 . We now show that if a word w is accepted by A , then P (w ) is accepted by A. Let π be the path accepting w , and let τ 1 , τ 2 , . . . , τ d denote the sequence of all transitions of π labeled with letters from Σ in the order they appear in π . By construction, τ i is of the form σ s i-1 ,s i a i -→ s i for some states s i-1 , s i ∈ Q A , i = 1, 2, . . . , d, with s 0 being initial and s k being accepting. Moreover, for i < d, the transition τ i is immediately followed in π by s i y s i+1 ---→ σ s i ,s i+1 . Let τ i be s i-1 a i -→ s i . It is straightforward to verify that τ 1 , τ 2 , . . . , τ d is an accepting path of P(w ) in A. Analogously for B and B. The fact that the existence of towers of arbitrary height is equivalent to the existence of an infinite tower then concludes the proof.

A similar construction yields the following variant of the previous theorem. Theorem 9. For every two NFAs A and B with at most n states and k input letters, there exist two DFAs A and B with O(kn) states and O(kn) input letters such that there is a tower of height r between A and B if and only if there is a tower of height r between A and B . In particular, there is an infinite tower between A and B if and only if there is an infinite tower between A and B . Proof. -→ σ a,t and σ a,t a -→ t. Self-loops in all new states are added over all new letters. The rest of the proof is analogous to the proof of Theorem 8.

Let Q A = Q A ∪ {σ a,t | a ∈ Σ, t ∈ Q A } and Q B = Q B ∪ {σ a,t | a ∈ Σ, t ∈ Q B },

Towers of prefixes

It is remarkable that lower bounds on the height of finite towers for NFAs in this paper were obtained by examples where w i is not just a subsequence of w i+1 but even its prefix (sometimes this rule is violated by the last element of the tower). In this section we therefore investigate what can be said about alternating towers of prefixes. A simple example of languages L 1 = a(ba) * and L 2 = b(ab) * shows that the towers of prefixes and towers (of subsequences) may behave differently. Indeed, there is no infinite tower of prefixes between L 1 and L 2 , since every word of L 1 begins with a and thus cannot be a prefix of a word of L 2 , which begins with b. But there is an infinite tower, namely, a, bab, ababa, . . .. We first describe a pattern on two automata A and B that characterizes the existence of an infinite tower of prefixes between them.

Let A = (Q A , Σ, δ A , I A , F A ) and B = (Q B , Σ, δ B , I B , F B ) be two NFAs. We say that (σ, σ 1 , σ 2 , τ, τ 1 , τ 2 ) is a pattern of the automata A and B if σ, σ 1 , σ 2 , τ, τ 1 , τ 2 are states of the product automaton such that

• σ 1 ∈ F A × Q B and τ 1 ∈ Q A × F B ,
• σ is reachable from an initial state,

• states σ 1 and σ 2 are reachable from state σ under a common word,

• states τ 1 and τ 2 are reachable from state τ under a common word, and

• τ is reachable from σ 2 and σ is reachable from τ 2 .
The definition is illustrated in Figure 10. We allow any of the words in the definition to be empty, with the convention that any state is reachable from itself under the empty word. The following theorem provides a characterization for the existence of an infinite tower of prefixes.

Theorem 10. Let A and B be two NFAs. Then there is an infinite tower of prefixes between A and B if and only if there is a pattern of automata A and B.

Proof. Let (σ, σ 1 , σ 2 , τ, τ 1 , τ 2 ) be a pattern of the automata A and B. Let u be a word under which state σ is reachable from an initial state (q A , q B ), x (y resp.) be a word under which both σ 1 and σ 2 (τ 1 and τ 2 resp.) are reachable from σ (τ resp.), u 1 be a word under which τ is reachable from σ 2 , and u 2 a word under which σ is reachable from τ 2 , see Figure 10. We then have an infinite tower of prefixes ux, ux(u 1 y), ux(u 1 y)(u 2 x), ux(u 1 y)(u 2 x)(u 1 y), . . . . Assume now that there exists an infinite tower of prefixes (w i ) ∞ i=1 between the languages L(A) and L(B). Consider the automaton det(A × B), the determinization of A × B by the standard subset construction, and let q A × B be its initial state. A sufficiently long element of the tower defines a path By symmetry, it remains to consider cases

q A × B u - → X z X -→ Y z Y -→ X
k i ≤ i , j ≤ k j , {i, j} = {1, 2}. Then 2 min(k 1 k 2 , 1 2 ) + |k 1 k 2 -1 2 | = k 1 k 2 + 1 2 ≤ k 1 k 2 + 1 2 + (k 1 -1 )( 2 -k 2 ) 2 = (k 1 + 1 )(k 2 + 2 ) 2 ,
which concludes the proof.

For DFAs we now have the following bound.

Theorem 13. Let A and B be two DFAs with n and m states that have no infinite tower of prefixes. Then the height of a tower of prefixes between A and B is at

most nm 2 + 1. Proof. Let A = (Q A , Σ, δ A , q A , F A ) and B = (Q B , Σ, δ B , q B , F B ), and let X = F A ×(Q B \ F B ) and Y = (Q A \ F A )× F B .
Final states (p i , q i ) = δ((q A , q B ), w i ) of any tower of prefixes (w i ) r i=1 between A and B in the product automaton A × B have to alternate between the states of X and Y, with the exception of w r : there may be no path labeled by w r in the non-accepting automaton, and therefore also no path in the product automaton A × B (recall our convention not to consider states that do not appear on an accepting path).

If (p i , q i ) = (p j , q j ) for some 1 ≤ i < j < r, then there is a path

(q A , q B ) w i -→ (p i , q i ) u - → (p i+1 , q i+1 ) v - → (p i , q i )
with w i+1 = w i u and w j = w i uv. Then there is an infinite tower of prefixes w i , w i u, w i uv, w i uvu, . . . , a contradiction. Therefore, it remains to show that there may be at most nm 2 alternations without repeated states between X and Y. The following theorem allows to conclude that the above bound is tight. Theorem 14. For every positive integer d and every odd positive integer e, there exists a binary DFA with 2d states and a binary DFA with e + 1 states having a tower of prefixes of height d(e + 1) + 1 and no infinite tower.

Proof. We consider the proof of Theorem 2, but instead of taking the NFA A d , we take its DFA equivalent, which has 2d states and, for simplicity, we denote it A d as well, cf. Figure 11. From Theorem 2, there is no infinite tower between the languages, and hence there is also no infinite tower of prefixes between the DFAs.

Consider the word w = (b e a) d-1 b e+1 . By the proof of Theorem 2, A d accepts all prefixes of w ending with an even number of b's, including those ending with a, and B e accepts all prefixes of w ending with an odd number of b's. The sequence (w i ) |w|+1 i=1 , where w i is the prefix of w of length i -1 for i = 1, 2, . . . , |w| + 1, is therefore a tower of prefixes between A d and B e of height |w| + 1 = (e + 1)(d -1) + e + 1 + 1 = d(e + 1) + 1. (The last word of the tower in Theorem 2 does not fit to a prefix tower.)

The following corollary now states that the bound of Theorem 13 is tight.

Corollary 15. For all even positive integers n and m, there exist binary DFAs with n and m states having a tower of prefixes of height nm 2 + 1 and no infinite tower.

Proof. The claim follows from Theorem 14 by setting d = n 2 and e = m -1. Comparing towers of subsequences and prefixes with respect to the number of states of DFAs, Theorem 7 shows that there are towers of subsequences of exponential height, while Theorem 13 gives a quadratic bound on the height of towers of prefixes. It shows an exponential gap between the height of towers of subsequences and prefixes for DFAs. What is the situation for NFAs? An immediate consequence of the NFA-to-DFA transformation and Theorem 13 give the following asymptotically tight bound.

Corollary 16. Given two NFAs with at most n and m states and with no infinite tower of prefixes, the height of a tower of prefixes between them is at most 2 n+m-1 -2 n-1 -2 m-1 + 1. Moreover, the lower bound is 2 n+m-2 -2 m-2 + 1 for any n, m ≥ 2.

Proof. Let two NFAs with n and m states be given. Their corresponding minimal DFAs have at most 2 n -1 and 2 m -1 nonempty states. By Theorem 13, the upper bound on the height of towers of prefixes is 1 2 (2 n -1)(2 m -1) + 1. Taking the integer part, the height is at most (2 n -1)(2 m -1)+1 2 = 2 n+m-1 -2 n-1 -2 m-1 + 1. The lower bound is obtained from Theorem 4 and Remark 1.

A natural question is whether there are any requirements on the size of the alphabet in case of automata with exponentially high towers of prefixes. The following corollary shows that the alphabet can be binary and the tower is still more than polynomial in the number of states.

Corollary 17. For any n there are binary NFAs with at most n states with no infinite tower of prefixes and with a tower of prefixes of a superpolynomial height with respect to n.

Proof. An automaton over the alphabet of cardinality k can be transformed into a binary automaton in the obvious way: replace each letter with its binary code of length log k, and replace every transition by a path with log k -1 new states. Note that the property of being a tower of prefixes between two automata is preserved by the transformation.

Consider automata A j, j and B j, j of Theorem 4. It can be calculated that each of them has less than 2 j 2 transitions. Therefore, by the transformation, we obtain binary automata A j, j and B j, j , each with at most 2 j 2 log 2 j states. By Remark 1, the transformed automata have no infinite tower of prefixes and a finite tower of prefixes of height at least 2 2 j-3 . Choosing j = n 2 log 2n , the binary automata A j, j and B j, j have at most n states, and they have a tower of prefixes of height

Ω 2 2n log 2n
.

The following question is open.

Open Problem 2. Given two NFAs with n and m states over a fixed alphabet with m letters. Assume that there is no infinite tower of prefixes between the automata. What is the tight bound on the height of towers of prefixes?

Conclusion

We investigated the height of finite towers between two regular languages as a function of the number of states of the automata representing the languages. We also paid attention to three additional parameters: (non)determinism, the structure of the tower (formed by subsequences or by prefixes), and the size of the alphabet. The connection between the parameters is summarized as follows.

The NFA vs. DFA representation does not play a crucial role since any tower between two NFAs can be "determinized" to a tower between two DFAs with only a moderate increase of the number of states.

A difference between towers of subsequences and towers of prefixes is less clear. It is conspicuous that our best, exponentially high towers are essentially towers of prefixes. We want to stress that this was not an intention but rather a surprising observation. Although this holds only for NFAs, it is worth noting that the proper subsequence relation is used exclusively in the determinization constructions. It leaves an intriguing open question whether, in the nondeterministic case, there is any substantial difference between towers of subsequences and towers of prefixes. In other words, the question is whether the subsequence relation can be simulated by the prefix relation using nondeterminism.

The real influence of the alphabet size is also unclear. We have seen that the height of towers grows exponentially with the alphabet size up to the point when the alphabet size is roughly the same as the number of states. The second intriguing question is thus whether the towers can grow beyond this point using a larger alphabet. The unconditional upper bound we have obtained is O n |Σ| , where the only limit on the size of Σ is the trivial bound 2 n 2 on the number of inequivalent letters in an n-state NFA (a letter a can be identified with the mapping δ( • , a) :

Q → 2 Q ).
The lack of understanding of the impact of the alphabet size seems to be related to the fact that the estimate of the number κ in Place et al. [START_REF] Place | Separating regular languages by piecewise testable and unambiguous languages[END_REF] is doubly exponential in the alphabet size. On a positive side, the difficulty to find examples of very high towers means that the construction suggested in Section 2.1 is going to be rather fast on typical instances. This should be contrasted with the construction by Place et al. [START_REF] Place | Separating regular languages by piecewise testable and unambiguous languages[END_REF], where the huge number κ is prohibitive, even if suspected to be overestimated.

The two open questions formulated in the paper are related. If, for NFAs, towers of prefixes are as high as towers of subsequences, then Θ(2 n+m ) is the optimal bound (cf. Open Problem 1).

To conclude, we inform the reader that slightly better bounds can be obtained in specific constellations by more technical constructions that can be found in the technical report of this paper [START_REF] Holub | On the height of towers of subsequences and prefixes[END_REF]. We present simplified constructions in this paper since they do not have any impact on the asymptotic results.

  (a) Towers of subsequences over Σ; µ = max(n, m) Towers of prefixes; ν = min(n, m)

Figure 1 :

 1 Figure 1: Automata A d and B e of Theorem 2 for d = e = 5

Theorem 2 .

 2 For every positive integer d and every odd positive integer e, there exists a binary NFA with d + 1 states and a binary DFA with e + 1 states having a tower of height d(e + 1) + 2 and no infinite tower.Proof. We define the automata A d and B e with d + 1 and e + 1 states, respectively, as depicted in Figure1for d = e = 5. The NFA A d = ({0, 1, . . . , d -1} ∪ {0 A }, {a, b}, δ d , {0, 1, . . . , d -1}, {0}) consists of an a-path through the states d -1, . . . , 0, of self-loops under b in all states 1, . . . , d -1, and of a b-cycle from 0 to 0 A and back to 0. The DFA B e = ({0, 1, . . . , e}, {a, b}, δ e , 0, {i | 1 ≤ i ≤ e and i is odd}) consists of a b-path through the states 0, 1, . . . , e and of an a-transition from state e to state 0. All odd states are accepting. Consider the word w = (b e a) d-1 b e+1 . Note that A d accepts all prefixes of w ending with an even number of b's, including those ending with a, and the empty prefix. On the other hand, the automaton B e accepts all prefixes of w ending with an odd number of b's. Moreover, the automaton B e accepts the word (b e a) d-1 b e ab. Hence the sequence (w i ) |w|+2 i=1 , where, for i = 1, 2, . . . , |w| + 1, w i is the prefix of w of length i -1, and w |w|+2 = (b e a) d-1 b e ab is a tower between A d and B e of height |w| + 2 = (e + 1)(d -1) + e + 1 + 2 = d(e + 1) + 2.

Figure 2 :

 2 Figure 2: Automaton A 5,m of Theorem 4

Theorem 5 .

 5 For all integers k ≥ 1, d ≥ 2 and every odd positive integer e, there exist two DFAs with (k + 1)d + k -1 and e + 1 states over an alphabet of cardinality k + 1 having a tower of height (e + 1)d k + 2d k-1 and no infinite tower.Proof. For every k ≥ 1, let Σ k = {b, a 1 , a 2 , . . . , a k }. We define two DFAs A k,d and B k,e over Σ k as follows. The set of states of the DFA Ak,d is Q k,d = {(m, j) | m = 1, 2, . . . , k; j = 0, 1, 2, . . . , d -1} ∪ {m | m = 2, . . . , k} ∪ {(1, i ) | i = 0, 1, . . . , d -1}. State (k, d -1) is initial, and states (1, j), j = 0, . . . , d -1, are accepting. The transition function of A k,d consists of

Figure 4 :

 4 Figure 4: Automaton A 3,2 of Theorem 5

Figure 5 :

 5 Figure 5: Automata B k,5 of Theorem 5 We now show by induction on k that there is a tower of height (e + 1)d k + 2d k-1 between A k,d and B k,e . For k = 1, the automata A 1,d and B 1,e have the tower of prefixes of the word u = (b e a 1 ) d-1 b e with two additional words: ub accepted by A 1,d , and ua 1 b e accepted by B 1,e in the state e. The tower has the required height (e + 1)d + 2. Let now k ≥ 2 and let (w k-1,i ) i=1 , with = (e + 1)d k-1 + 2d k-2 , be a tower between the automata A k-1,d and B k-1,e , where w k-1,1 is accepted by A k-1,d and w k-1, is accepted by B k-1,e in the state e. Let u k, j = (a 1 a k a 1 ) j a d-j k w k-1, a k j . We show that (w k,i ) d i=1 with w k, j +m = u k, j w k-1,m , j = 0, 1, . . . , d -1, m = 1, 2, . . . , , is a tower between the automata A k,d and B k,e , where w k,1 is accepted by A k,d and w k,d is accepted by B k,e in the state e.

Figure 6 :

 6 Figure 6: The DFA A 3 (left) and the two-state DFA B n (right), n ≥ 0 of Theorem 7

Figure 8 :

 8 Figure 8: The tower between L(A 3 ) and L(B 3 ). We underline transitions between different states in A 3 .

  s

Figure 9 :

 9 Figure 9: Determinization by Theorem 8 and Theorem 9 respectively. (Self-loops under new letters in σ-states omitted.)

Figure 10 :

 10 Figure 10: The pattern (σ, σ 1 , σ 2 , τ, τ 1 , τ 2 )

Figure 11 :

 11 Figure 11: DFAs A d and B e of Theorem 14 for d = e = 5

  If |X| = |Y|, then there are at most 2 • min(|X|, |Y|) such alternations, and if |X| |Y|, then there are at most 2 • min(|X|, |Y|) + 1 such alternations. In both cases, the proof is completed by Lemma 12 with k 1 = |F A |, 2 = |F B |, k 1 + 1 = n and k 2 + 2 = m, noting that for k 1 = 0 or 2 = 0 the claim holds since then L(A) or L(B) is empty.

  where σ s,t are new states. We introduce a new letter y t for every state t∈ Q A ∪ Q B . It results in O n 2 states and O (k + n) letters.The transition function is defined as follows. In both automata, each transition s Moreover, self-loops in all new states are added over all new letters. Note that all transitions are deterministic in A and B .

			a -→ t is replaced with
	two transitions s	y t -→ σ s,t and σ s,t	a -→ t.

  where σ a,t are new states. The alphabet of A andB is Σ ∪ {a t | a ∈ Σ, t ∈ Q A ∪ Q B }.We have O(kn) states and letters. Each transition s

		a -→ t, in both
	automata, is replaced with two transitions s	a t

We thank an anonymous reviewer of an earlier version of this paper for pointing this out.

Acknowledgements. We are grateful to anonymous referees for their suggestions that allowed to improve and simplify the exposition.

 [START_REF] Almeida | Implicit operations on finite J-trivial semigroups and a conjecture of I. Simon[END_REF]Research supported by the Czech Science Foundation grant number 13-01832S 2 Research supported by the by DFG in Emmy Noether grant KR 4381/1-1 (DIAMOND), and by RVO 67985840. 3 Research supported by the Alexander von Humboldt Foundation

in the automaton det(A × B), such that X contains a state ( f 1 , q 1 ) ∈ F A × Q B and Y contains a state (q 2 , f 2 ) ∈ Q A × F B . For every state of X, there exists an incoming path from an element of Y labeled by z Y since X = δ A × B (Y, z Y ). Similarly, for every state of Y, there exists an incoming path from an element of X labeled by z X since Y = δ A × B (X, z X ). Thus, there are infinitely many paths from X to X labeled with words from (z X z Y ) + ending in state ( f 1 , q 1 ). Therefore, there exists a state (s 1 , t 1 ) ∈ X and integers k 1 and 1 such that

Similarly, there exists a state (s 2 , t 2 ) ∈ X and integers k 2 and 2 such that

. The pattern is completed by states σ 2 and τ 2 , such that

where u 1 and u 2 can be chosen as u

We point out that the identification is easy. It could even be shown that to decide whether there is a pattern between the automata, that is, whether there is an infinite tower of prefixes, is an NL-complete problem for both NFAs and DFAs (cf. our technical report [START_REF] Holub | Alternating towers and piecewise testable separators[END_REF]). This is in contrast to deciding the existence of an infinite tower of subsequences, which is PTime-complete [START_REF] Masopust | Separability by piecewise testable languages is PTime-complete[END_REF]. Notice that if there is a pattern, then there is also a pattern with σ = τ as shown in the proof above. From the point of view of finding the pattern, however, it is more natural to keep the more general definition of the pattern given above.

We have already mentioned that if there are towers of arbitrary height, then there is an infinite tower. This property holds for any relation that is a well quasi order (WQO) [3, Lemma 6] of which the subsequence relation is an instance. The prefix relation is not a WQO. However, Theorem 10 and its proof shows that the pattern and therefore also an infinite tower of prefixes can be found as soon as there exists a sufficiently long tower of prefixes. On the other hand, this argument depends on the fact that the languages are regular. Indeed, the following example shows that the property in general does not hold for non-regular languages.

Example 11. Let K = {a, b} * a and L = {a m (ba * ) n b | m > n ≥ 0} be two languages. Note that K is regular and L is non-regular context-free. The languages are disjoint, since the words of K end with a and the words of L with b. For any r ≥ 1, the words w 2i+1 = a r (ba) i ∈ K and w 2(i+1) = a r (ba) i b ∈ L for i = 0, 1, . . . , r -1 form a tower of prefixes between K and L of height 2r. On the other hand, let w 1 , w 2 , . . . be a tower of prefixes between the languages K and L. Without loss of generality, we may assume that w 1 belongs to L. Then a b is a prefix of w 1 for some ≥ 1. It is not hard to see that |w i | b < |w i+2 | b holds for any w i ≤ w i+1 ≤ w i+2 with w i , w i+2 in L and w i+1 in K. As any word of L with a prefix a b can have at most occurrences of letter b, the tower cannot be infinite.

Given that the height of finite towers of prefixes for regular languages is bounded, we now investigate the bound. We need the following auxiliary combinatorial lemma, which is fairly straightforward, but its proof is technical, and therefore we formulate it outside the main proof.

Proof. Suppose that k 1 = 0. Then the first claim is obvious. If k 1 k 2 1 2 , then 1 , 2 > 0. Since also k 2 > 0, we get the second claim. By symmetry, we shall further suppose that k 1 , 1 , k 2 , 2 ≥ 1.

Let us now assume that k 1 ≤ 1 and k 2 < 2 . Then 2 min(k 1 k 2 , 1 2 )