Janusz Brzozowski

Galina Jirásková
email: jiraskov@saske.sk

Bo Liu
email: b23liu@uwaterloo.ca

Aayush Rajasekaran

Marek Szyku La

On the State Complexity of the Shuffle of Regular Languages ⋆

Keywords: regular language, shuffle, state complexity, upper bound

We investigate the shuffle operation on regular languages represented by complete deterministic finite automata. We prove that

) is an upper bound on the state complexity of the shuffle of two regular languages having state complexities m and n, respectively. We also state partial results about the tightness of this bound. We show that there exist witness languages meeting the bound if 2 m 5 and n 2, and also if m = n = 6. Moreover, we prove that in the subset automaton of the NFA accepting the shuffle, all 2 mn states can be distinguishable, and an alphabet of size three suffices for that. It follows that the bound can be met if all f (m, n) states are reachable. We know that an alphabet of size at least mn is required provided that m, n 2. The question of reachability, and hence also of the tightness of the bound f (m, n) in general, remains open.

An Upper Bound for the Shuffle Operation

The state complexity of a regular language L [START_REF] Yu | State complexity of regular languages[END_REF] is the number of states in a complete minimal deterministic finite automaton (DFA) recognizing the language; it will be denoted by κ(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.

Let Σ be a finite non-empty alphabet. The shuffle u v of words u, v ∈ Σ * is defined as follows:

u v = {u 1 v 1 • • • u k v k | u = u 1 • • • u k , v = v 1 • • • v k , u 1 , . . . , u k , v 1 , . . . , v k ∈ Σ * }.
The shuffle of two languages K and L over Σ is defined by

K L = u∈K,v∈L u v.
Note that the shuffle operation is commutative on both words and languages.

The state complexity of the shuffle operation was first studied by Câmpeanu, Salomaa, and Yu [START_REF] Câmpeanu | Tight lower bound for the state complexity of shuffle of regular languages[END_REF], but they considered only bounds for incomplete deterministic automata. In particular, they proved that 2 mn -1 is a tight upper bound for that case. Since we can convert an incomplete deterministic automaton into complete one by adding the empty state, it follows that 2 (m-1)(n-1) -1 is a lower bound for the case of complete deterministic automata. Here we show that this lower bound can be improved, and we derive an upper bound for two regular languages represented by complete deterministic automata, but the question whether this bound is tight remains open.

A nondeterministic finite automaton (NFA) is a quintuple A = (Q, Σ, δ, s, F ), where Q is a finite non-empty set of states, Σ is a finite alphabet of input symbols, δ : Q × Σ → 2 Q is the transition function which is extended to the domain 2 Q × Σ * in the natural way, s ∈ Q is the initial state, and F ⊆ Q is the set of final states. The language accepted by NFA A is the set of words

L(A) = {w ∈ Σ * | δ(s, w) ∩ F = ∅}.
An NFA A is deterministic and complete (DFA) if |δ(q, a)| = 1 for each q in Q and each a in Σ. In such a case, we write δ(q, a) = q ′ instead of δ(q, a) = {q ′ }. A DFA is minimal (with respect to the number of states) if all its states are reachable, and no two distinct states are equivalent.

Every NFA A = (Q, Σ, δ, s, F ) can be converted to an equivalent DFA A ′ = (2 Q , Σ, δ, {s}, F ′ ), where F ′ = {R ∈ 2 Q | R ∩ F = ∅}. The DFA A ′ is called the subset automaton of NFA A. The subset automaton may not be minimal since some of its states may be unreachable or equivalent to other states.

Let K and L be regular languages over an alphabet Σ recognized by deterministic finite automata K = (Q K , Σ, δ K , q K , F K ) and L = (Q L , Σ, δ L , q L , F L ), respectively. Then K L is accepted by the nondeterministic finite automaton

N = (Q K × Q L , Σ, δ, (q K , q L ), F K × F L ),
where δ((p, q), a) = {(δ K (p, a), q), (p, δ L (q, a))}.

Let D = (2 QK ×QL , Σ, δ ′ , {(q K , q L )}, F ′ ) be the subset automaton of N . If |Q K | = m and |Q L | = n,
then NFA N has mn states. It follows that DFA D has at most 2 mn reachable and pairwise distinguishable states. However, this upper bound cannot be met, as we will show.

In the sequel, we assume that Q K = {1, 2, . . . , m}, q K = 1, Q L = {1, 2, . . . , n}, and q L = 1. We say that a state (p, q) of NFA N is in row i if p = i, and it is in column j if q = j. Proposition 1. Let a ∈ Σ. Let S be a state of D. Let π col (S) = {p | (p, q) ∈ S for some q}, and π row (S) = {p | (p, q) ∈ S for some p}. Then π x (S) ⊆ π x (S • a) for x ∈ {col, row}.

Proof. Let p ∈ π col (S); then we have (p, q) ∈ S for some q. Since δ((p, q), a) = {(δ K (p, a), q), (p, δ L (q, a)}, we have (p, δ L (q, a)) ∈ δ(S, a), so p ∈ π col (δ(S, a)). By symmetry, the same claim holds for π row .

⊓ ⊔

We claim that in the subset automaton D, every reachable subset S of Q K × Q L must contain a state in column 1 and a state in row 1, that is, it must satisfy the following condition.

Condition (C):

There exist states (s, 1) and (1, t) in S for some s ∈ Q K and t ∈ Q L . Lemma 2. Every reachable subset S of subset automaton D satisfies Condition (C).

Proof. The initial subset of D is {(1, 1)}, and it satisfies Condition (C). By Proposition 1, for every a ∈ Σ we get that 1 ∈ π col (δ(S, a)) and 1 ∈ π row (δ(S, a)), so δ(S, a) satisfies Condition (C). By induction, all reachable subsets satisfy Condition (C).

⊓ ⊔ Theorem 3 (Shuffle: Upper Bound). Let κ(K) = m and κ(L) = n. Then the state complexity of the shuffle of K and L is at most

f (m, n) = 2 mn-1 + 2 (m-1)(n-1) (2 m-1 -1)(2 n-1 -1). (1)
Proof. By Lemma 2, every reachable subset of D must contain a state in row 1 and a state in column 1. There are 2 mn-1 subsets containing state (1, 1), and 2 (m-1)(n-1) (2 m-1 -1)(2 n-1 -1) subsets not containing (1, 1) but containing (s, 1) for some s ∈ {2, 3, . . . , m} and (1, t) for some t ∈ {2, 3, . . . , n}. This gives f (m, n).

⊓ ⊔

Let K and L be two regular languages over Σ. If κ(K) = κ(L) = 1, then each of K, L, and K L is either ∅ or Σ * , and κ(K L) = 1; hence the bound f (1, 1) = 1 is tight. Now suppose that κ(K) = 1; here we have two possible choices for K, the empty language or Σ * . The first choice leads to κ(K L) = 1. Hence only the second choice is of interest, where the language K L = Σ * L is the allsided ideal [START_REF] Brzozowski | Quotient complexity of ideal languages. Theoret[END_REF] generated by L. If κ(L) = 2, the upper bound f (1, 2) = 2 is met by the unary language L = aa * . Hence assume that κ(K) = 1 and κ(L)

3. The next observation shows that in such a case, the tight bound is less than

f (1, n) = 2 n-1 .
Proposition 4 (Okhotin [4]). If κ(L) 3, then the state complexity of Σ * L is at most 2 n-2 + 1, and this bound can be reached only if |Σ| n -2.

Okhotin showed that the language L = (a

1 Σ * a 1 ∪ • • • ∪ a n-2 Σ * a n-2 )Σ * ,
where Σ = {a 1 , . . . , a n-2 }, meets this bound [START_REF] Okhotin | On the state complexity of scattered substrings and superstrings[END_REF]. This takes care of the case κ(K) = 1 and, by symmetry, of the case κ(L) = 1.

In what follows we assume that m 2 and n 2. First, let us show that the upper bound f (m, n) cannot be met by regular languages defined over a fixed alphabet.

Proposition 5. Let K and L be regular languages over Σ with κ(K) = m and κ(L) = n, where m, n 2.

If κ(K L) = f (m, n), then |Σ| mn -1.
Proof. For s = 2, 3, . . . , m and t = 2, 3, . . . , n denote

A s = {(1, 1), (s, 1)}, B t = {(1, 1), (1, t)}, C st = {(s, 1), (1, t)}.
If all the subsets satisfying Condition (C) are reachable, then, in particular, all the subsets A s , B t , and C st must be reachable. Let us show that all these subsets must be reached from some subsets containing state (1, 1) by distinct symbols.

Suppose that a set A s is reached from a reachable set S with S = A s by a symbol a, that is, we have A s = δ(S, a) and S = A s . The set A s contains only states in column 1 and rows 1 or s. By Proposition 1, the set S may only contain states in column 1 and in rows 1 or s, that is, we have S ⊆ {(1, 1), (s, 1)}. Since S = A s , we must have S = {(1, 1)}.

By symmetry, each B t can only be reached from {(1, 1)}. Suppose that a set C st is reached from a reachable set S with S = C st by a symbol a. By Proposition 1, we must have S ⊆ {(1, 1), (s, 1), (1, t), (s, t)}. Let us show that (1, 1) ∈ S. Suppose for a contradiction that (1, 1) / ∈ S. Then, since S is reachable, it must contain a state in column 1 and a state in row 1, that is, we must have {(s, 1), (1, t)} ⊆ S. But then (s, t) ∈ S since S = C st . However, then δ K (s, a) = 1 and δ L (t, a) = 1 which implies that (1, 1) ∈ δ((s, 1), a), and so (1, 1) ∈ C st . This is a contradiction. Therefore C st is reached from a set containing [START_REF] Brzozowski | Quotient complexity of ideal languages. Theoret[END_REF][START_REF] Brzozowski | Quotient complexity of ideal languages. Theoret[END_REF].

Thus each A s is reached from {(1, 1)} by a symbol a s , each B t is reached from {(1, 1)} by a symbol b t , each C st is reached from a set containing (1, 1) by a symbol c st , and we must have

δ K (1, a s ) = s and δ L (1, a s ) = 1, δ K (1, b t ) = 1 and δ L (1, b t ) = t, δ K (1, c st ) = s and δ L (1, c st ) = t.
It follows that all the symbols a s , b t , and c st must be pairwise distinct. Therefore we have Unfortunately, this lower bound on the size of the alphabet is not tight, as is demonstrated by the following example: Example 6. If t is a transformation of the set {1, 2, . . . , n} and q ∈ {1, 2, . . . , n}, let qt be the image of q under t. Transformation t can now be denoted by [1t, 2t, . . . , nt].

|Σ| m -1 + n -1 + (m -1)(n -1) = mn -1. ⊓ ⊔ 1 ′ 2 ′ a,
(1) If m = n = 2, we have f (2, 2) = 10. Let Σ = {a, b, c, d}, and let the DFAs K and L be as shown in Fig. 1, and let K and L be their languages. Then κ(K L) = 10. We have used GAP [START_REF]GAP -Groups, Algorithms, and Programming[END_REF] to show that the bound cannot be reached with a smaller alphabet, and that the DFAs of Fig. 1 are unique up to isomorphism.

(2) For m = 2 and n = 3, the minimal size of the alphabet of a witness pair is 6. We have verified this by a dedicated algorithm enumerating all pairs of non-isomorphic DFAs with 2 and 3 states. In contrast to the previous case, over a minimal alphabet there are more than 60 non-isomorphic DFAs of L -even if we do not distinguish them by sets of final states -that meet the bound with some K. One of the witness pairs is described below.

Let Σ = {a, b, c, d, e, f }.

Let K = ({1, 2}, Σ, δ K , 1, {2}), and let a = [1, 2], b = c = [2, 1], d = [1, 1], e = [2, 2], and f = [2, 1]. Let L = ({1, 2, 3}, Σ, δ L , 1, {1}), and let a = [2, 2, 3], b = [2, 1, 3], c = [1, 1, 1], d = e = [3, 1, 2], f = [3, 1, 1]. Then κ(K L) = 44 = f (2, 3).
The bound mn -1 on the size of the alphabet is not tight for m = n = 2, where an alphabet of size four is required. For any m, n 2 the subsets of {1, 2} × {1, 2} satisfying (C) must be also reachable, and to reach them we can use only transformations mapping 1 to either 1 or 2. There are only three such transformations counted in Proposition 5; thus we need one more letter.

Partial Results about Tightness

To prove that the upper bound f (m, n) of Equation ( 1) is tight, we must exhibit two languages K and L with state complexities m and n, respectively, such that κ(K L) = f (m, n). As usual, we use DFAs to represent the languages: Let K and L be minimal complete DFAs for K and L. We first construct the NFA N as defined in Section 1, and we consider the subset automaton D of NFA N . We must then show that D has f (m, n) states reachable from the initial state {(1, 1)}, and that these states are pairwise distinguishable. We were unable to prove this for all m and n, but we have some partial results about reachability in Subsection 2.1, and we deal with distinguishability in Subsection 2.2.

Reachability

We performed computations verifying reachability of the upper bound for small values of m and n. These results are summarized in Table 1.

The computation in the hardest case with m = n = 6 took about 48 days on a computer with AMD Opteron(tm) Processor 6380 (2500 MHz) and 64 GB of RAM. Moreover, we verified that in all these cases, every subset of size at least 3 is directly reachable from some smaller subset. We also verified that for reachability in case of m = n = 3 an alphabet of size 12 is sufficient, and in case of m = n = 4 an alphabet of size 50 is sufficient. Using these results, we are going to prove reachability for all m, n with 2 m 5 and n 2.

Without loss of generality, the set of states of any n-state DFA is denoted by Q n = {1, 2, . . . , n}. Let T n be the monoid of all transformations of the set Q n . Let p, q ∈ Q n and P ⊆ Q n . Let 1 denote the identity transformation. Let (p → q) denote the transformation that maps state p to state q and acts as the identity on all the other states. Let (p, q) denote the transformation that transposes p and q.

Here we deal only with reachability, so final states do not matter. We assume that the sets of final states are empty in this subsection.

Let Σ m,n = {a s,t | s ∈ T m and t ∈ T n } be an alphabet consisting of m m n n symbols. If an input a induces transformations s in T m and t in T n , this will be indicated by a : s; t.

Define DFAs K m,n = (Q m , Σ m,n , δ m , 1, ∅) and L m,n = (Q n , Σ m,n , δ n , 1, ∅), where δ m (p, a s,t ) = ps if p ∈ Q m and δ n (q, a s,t ) = qt if q ∈ Q n .
Let N m,n be the NFA for the shuffle of languages recognized by DFAs K m,n and L m,n as described in Section 1, and let D m,n be the subset automaton of N m,n . The NFA N m,n has alphabet Σ m,n , and so has an input letter for every pair of transformations in T m × T n . Therefore the addition of another input letter to the DFAs K m,n and L m,n cannot add any new set of states of N m,n that would be reachable from

{(1, 1)} in D m,n . Let m ′ m and n ′ n. Then DFA K m ′ ,n ′ = (Q m ′ , Σ m ′ ,n ′ , δ m ′ , 1, ∅) (respec- tively, the DFA L m ′ ,n ′ = (Q n ′ , Σ m ′ ,n ′ , δ n ′ , 1, ∅)) is a sub-DFA of K m,n (respec- tively, of L m,n ), in the sense that Q m ′ ⊆ Q m , Σ m ′ ,n ′ ⊆ Σ m,n , and δ m ′ ⊆ δ m .
As well, NFA N m ′ ,n ′ is a sub-NFA of N m,n . Note that D m,n is extremal for the shuffle: every language K L, where K and L are languages with state complexities m and n respectively, is recognized by some sub-DFA of D(m, n) after possibly renaming some letters.

For the next lemma it is convenient to consider a subset S of states (p, q) of N m,n as an m × n matrix, where the entry in row p and column q is (p, q) if (p, q) ∈ S, and it is empty otherwise. We first introduce the following notions.

Definition 7. Let i, i ′ ∈ Q m , i = i ′ , and j, j ′ ∈ Q n , j = j ′ . (a) A row i ′ contains row i, if (i, j) ∈ S implies (i ′ , j) ∈ S for all j ∈ Q n . (b) A column j ′ contains column j if (i, j) ∈ S implies (i, j ′ ) ∈ S for all i ∈ Q m . (c) A subset of Q m × Q n is valid if it satisfies Condition (C) from Lemma 2,
that is, if it contains a state in row 1 and a state in column 1.

Lemma 8. Let S be a valid subset of Q m × Q n with the property that there are distinct i, i ′ or j, j ′ such that either row i ′ contains row i or column j ′ contains column j. Assume that every valid subset

S ′ of Q m ′ × Q n ′ , where m ′ < m, or n ′ < n, or |S ′ | < |S|, is reachable in DFA D m ′ ,n ′ . Then S is reachable in D m,n .
Proof. If S contains an empty row or column, then without loss of generality we can renumber the n states of L m,n in such a way that column n is the empty column in S. By the inductive assumption we know that S is reachable in D m,n-1 by some word w. Since N m,n-1 is a sub-NFA of N m,n , S is reachable in D m,n as well by the same word. Suppose that S has neither an empty row nor an empty column. By symmetry, it is sufficient to consider the case with distinct i and i ′ such that row i ′ contains row i. Let S ′ = S\{(i ′ , j) | (i, j) ∈ S for j ∈ {1, . . . , n}}. Since |S ′ | < |S|, the set S ′ is reachable by assumption. To obtain S, we apply the letter that induces the transformation i → i ′ ; 1.

⊓ ⊔ Lemma 9. Let S be a valid subset of Q m × Q n such that there is a column or a row with exactly one element. Assume that every valid subset

S ′ of Q m ′ × Q n ′ , where m ′ < m, or n ′ < n, or |S ′ | < |S|, is reachable in D m ′ ,n ′ . Then S is reachable in D m,n .
Proof. Recall that we can assume m 2 and n 2. We may assume that there is neither an empty row nor an empty column in S; otherwise S is reachable by Lemma 8. It is sufficient to consider the case involving a column, since the case involving a row follows by symmetric arguments. Let (p, q) be the only element in column q. If there are more elements in row p, then column q is contained in another column and by Lemma 8, the set S is reachable. Let S ′ be the subset of Q m-1 × Q n-1 obtained by removing row p and column q, and renumbering the states to Q m-1 × Q n-1 in the way such that i ∈ Q m becomes i -1 if i > p and otherwise remains the same, and j ∈ Q n becomes j -1 if j > q and otherwise remains the same. We have that S ′ is a valid subset, and by the inductive assumption it is reachable in D m-1,n-1 by some word u ′ ; let u be the word corresponding to u ′ in the original numbering of the states. We consider four cases.

Case p = 1 and q = 1: State {(1, 1), (p, q)} is reachable in D m,n by word a 2 , where a : (1, p); (1, q). Then S is reachable by a 2 u.

Case p = 1 and q = 1: State {(2, 1), (1, q)} is reachable in D m,n by word a 2 , where a : (1, 2); (1, q). Then state (2, 1) corresponds to state (1, 1) after the renumbering, and S is reachable by a 2 u.

Case p = 1 and q = 1: This is symmetrical to the previous case. Case p = 1 and q = 1: State {(1, 1), (2, 2)} is reachable in D m,n by word a 2 , where a : (1, 2); [START_REF] Brzozowski | Quotient complexity of ideal languages. Theoret[END_REF][START_REF] Câmpeanu | Tight lower bound for the state complexity of shuffle of regular languages[END_REF]. Then state (2, 2) corresponds to state (1, 1) after the renumbering, and S is reachable by a 2 u.

⊓ ⊔

Theorem 10. If for some h every valid subset can be reached in D h,( h ⌊h/2⌋ ) then for every m h and every n, every valid subset can be reached in D m,n .

Proof. This follows by induction on m, n, and |S|.

For m = 1 this follows by induction on n: if n = 1 then D 1,1 consists of a single valid subset {(1, 1)}, and if n > 1, then we apply Lemma 8. For m h and n h ⌊h/2⌋ this holds by assumption, since N m,n is a sub-NFA of N h,( h ⌊h/2⌋ ) . If |S| = 1, then {(1, 1)} is the only valid subset, and it is reachable since it is the initial subset of D m,n .

Let S be a valid subset of Q m × Q n , where m h and n > h ⌊h/2⌋ , and assume that every valid subset [START_REF] Sperner | Ein Satz über Untermengen einer endlichen Menge[END_REF], the maximal number of subsets of an m-element set such that none of them contains any other subset is m ⌊m/2⌋ . This is not larger than h ⌊h/2⌋ ; hence, there exist some columns j, j ′ with j = j ′ such that the j-th column is contained in j ′ -th column. By Lemma 8, the subset S is reachable.

S ′ of Q m ′ × Q n ′ is reachable if m ′ < m, or n ′ < n, or |S ′ | < |S|. By Sperner's theorem
⊓ ⊔

Corollary 11. Let 1 m 4 and n 1. Then every valid subset can be reached in D m,n .

Proof. Since we have verified the reachability of all valid subsets for m = 4 and n = 6 = 4 2 , Theorem 10 applies with h = 4.

⊓ ⊔

To strengthen this result and show reachability for m 5, we need to introduce another concept with permutations. Let ϕ be any permutation of m rows. We split subsets of Q m (subsets of rows) into equivalence classes under ϕ. For

U ⊆ Q m , [U ] ϕ = {V ⊆ Q m | V = ϕ i (U ) for some i
0} denotes the equivalence class of U . See Tables 2,3, 4 for examples of subsets whose columns U are partitioned into equivalence classes under some ϕ.

For a subset S of Q m × Q n , by col(S, i) we denote the subset of Q m contained in the i-th column. Then cols(S) = 1 i n col(S, i) is the set of the subsets in the columns of S.

The following lemma assures reachability (under an inductive assumption) of a special kind of subsets whose columns form only full and empty equivalence classes under some permutation ϕ.

Lemma 12. Let ϕ be a permutation of m rows. Let S be a valid subset of Q m × Q n such that [U ] ϕ ⊆ cols(S) for every U ∈ cols(S), and there is a column

V ∈ cols(S) such that |[V ] ϕ | 2. Assume that every valid subset S ′ of Q m ′ × Q n ′ , where m ′ < m, or n ′ < n, or |S ′ | < |S|, is reachable in D m ′ ,n ′ . Then S is reachable in D m,n .
Proof. We can assume that no two columns contain the same subset of rows, no column is empty, and the first row contains at least two elements; otherwise S is reachable by Lemma 8 or by Lemma 9.

Let S j = col(S, j) be the j-th column of a valid subset S. Thus we have

S = {(i, j) | 1 j n and i ∈ S j }. Since |[V ] ϕ | 2, we can always choose V so that ϕ -1 (V ) is in a k-th column S k with k = 1.
Let S ′ be the set obtained from S by omitting the states in the k-th column and by taking the pre-image of S j under ϕ in any other column, that is,

S ′ = {(i, j) | 1 j n, j = k, and i ∈ ϕ -1 (S j )}.
Since k = 1 and the first row of S contains at least two elements, the set S ′ is valid. Since V is non-empty, we have ′ | < |S|. Let ψ be a permutation that maps a column j the column containing ϕ -1 (S j ), that is, we have S ψ(j) = ϕ -1 (S j ). Let t be the transformation given by a ϕ,ψ . Let us show that S ′ t = S.

Let (i, j) ∈ S ′ . Then i ∈ ϕ -1 (S j ), so ϕ(i) ∈ S j , and we have (i, j)t = {(ϕ(i), j), (i, ψ(j))} ⊆ S. Hence S ′ t ⊆ S. Now let (i, j) ∈ S. First let j = k. Then i ∈ S j , so ϕ -1 (i) ∈ ϕ -1 (S j ). Therefore (ϕ -1 (i), j) ∈ S ′ . Since (i, j) ∈ (ϕ -1 (i), j)t, we have (i, j) ∈ S ′ t. Now let j = k. Then i ∈ ϕ -1 (V ) and S ψ -1 (k) = V . Thus (i, ψ -1 (k)) ∈ S ′ , and we have (i, k) ∈ (i, ψ -1 (k))t. Hence S ⊆ S ′ t. Our proof is complete.

⊓ ⊔ Table 2. A subset and the equivalence classes of columns under ϕ = [2, 3,

.

1 2 3 4 5 6 7 8 9 1 • • • • 2 • • • • 3 • • • • 4 • • • 5 • • • eq A A A B B B C C C
1 • • • 2 • • • 3 • • • 4 • • • • 5 • • • • eq A B C D B C D E Table 4.
A subset and the equivalence classes of columns under ϕ = [2, 3,

.

1 2 3 4 5 6 7 8 1 • • • • 2 • • • • 3 • • • • 4 • • • • 5 • • • • eq A A A A B B B B
Corollary 13. Let 1 m 5 and n 1. Then every valid subset can be reached in D m,n .

Proof. The proof follows by analysis of valid subsets S ⊆ Q 5 × Q n , with the aid of Corollary 11, Lemma 8, Lemma 12, and the results from Table 1.

Suppose that there is a valid subset S ⊆ Q 5 × Q n that is not reachable; let S be chosen so that n is the smallest number and S is a smallest non-reachable subset of

Q 5 × Q n .
By Corollary 11 and the choice of n, every valid subset S ′ ⊂ Q m ′ ×Q n ′ , where m ′ < 5, or n ′ < n, or |S ′ | < |S|, is reachable. Hence, S has no column containing another column; otherwise, we can apply Lemma 8. Since we have verified the reachability of all valid subsets for m = 5 and n 7 (Table 1), we must have n 8 and so S has at least 8 distinct columns. Obviously there is neither an empty nor a full column. Let C 3 be the number of 3-element columns (|U | = 3), and C 2 be the number of 2-element columns (|U | = 2). We are searching for possible subsets S that do not have a column containing another column, and with C 3 +C 2 8. We consider the following six cases.

(1) Let C 3 = 0. If C 2 = 10, which implies that S contains all possible 2element subsets, then under ϕ = [START_REF] Câmpeanu | Tight lower bound for the state complexity of shuffle of regular languages[END_REF][START_REF]GAP -Groups, Algorithms, and Programming[END_REF][START_REF] Okhotin | On the state complexity of scattered substrings and superstrings[END_REF][START_REF] Sperner | Ein Satz über Untermengen einer endlichen Menge[END_REF][START_REF] Brzozowski | Quotient complexity of ideal languages. Theoret[END_REF] we have two full and non-trivial equivalence classes. Hence S is reachable from a smaller subset by Lemma 12. If C 2 = 9, then without loss of generality let the missing 2-element subset be {4, 5}; see Table 2. Under ϕ = [2, 3, 1, 4, 5] we have three full and non-trivial equivalence classes, and S is reachable by Lemma 12. Finally, if C 2 = 8, then we have two subcases. If the two missing 2-element subsets have a common element, then without loss of generality let them be {2, 3} and {4, 5}. Under ϕ = [START_REF] Brzozowski | Quotient complexity of ideal languages. Theoret[END_REF][START_REF] Okhotin | On the state complexity of scattered substrings and superstrings[END_REF][START_REF] Sperner | Ein Satz über Untermengen einer endlichen Menge[END_REF][START_REF] Câmpeanu | Tight lower bound for the state complexity of shuffle of regular languages[END_REF][START_REF]GAP -Groups, Algorithms, and Programming[END_REF] we have four full and non-trivial equivalence classes, and S is reachable by Lemma 12. If they have a common element, then without loss of generality let them be {3, 4} and {4, 5}. Under ϕ = [START_REF] Brzozowski | Quotient complexity of ideal languages. Theoret[END_REF][START_REF] Câmpeanu | Tight lower bound for the state complexity of shuffle of regular languages[END_REF][START_REF] Sperner | Ein Satz über Untermengen einer endlichen Menge[END_REF][START_REF] Okhotin | On the state complexity of scattered substrings and superstrings[END_REF][START_REF]GAP -Groups, Algorithms, and Programming[END_REF] we have six full equivalence classes and two of them are non-trivial. Thus S is reachable by Lemma 12.

(2) Let C 3 = 1. The only possible subset, up to permutation of columns and rows, is shown in Table 3. It has all columns with two elements that are not contained in the 3-element column. By Lemma 12 with ϕ = [START_REF] Brzozowski | Quotient complexity of ideal languages. Theoret[END_REF][START_REF] Câmpeanu | Tight lower bound for the state complexity of shuffle of regular languages[END_REF][START_REF]GAP -Groups, Algorithms, and Programming[END_REF][START_REF] Sperner | Ein Satz über Untermengen einer endlichen Menge[END_REF][START_REF] Okhotin | On the state complexity of scattered substrings and superstrings[END_REF], it is reachable.

(3) Let C 3 = 2. A simple analysis reveals that if the 3-element columns have only one common element, then C 2 is at most 4. If they have two common elements, then C 2 is at most 5. Thus in this case, we have C 2 + C 3 7.

(4) Let C 3 = 3. Here C 2 is at most 4.

(5) Let C 3 = 4. The only possible subset, up to permutation of columns and rows, is shown in Table 4. By Lemma 12 with ϕ = [2, 3, 4, 1, 5], it is reachable.

(6) Let C 3 5. These cases are symmetrical to those with C 3 3; it is sufficient to consider the complement of S.

Since these cover all the possibilities for set S, this set is reachable. ⊓ ⊔

Proof of Distinguishability

The aim of this section is to show that there are regular languages defined over a three-letter alphabet such that the subset automaton of the NFA for their shuffle does not have equivalent states. To this aim let A = (Q, Σ, δ, s, F ) be an NFA. We say that a state q in Q is uniquely distinguishable if there is a word w in Σ * which is accepted by A from and only from the state q, that is, if there is a word w such that δ(p, w) ∈ F if and only if p = q. First, let us prove the following two observations. Proposition 14. If each state of an NFA A is uniquely distinguishable, then the subset automaton of A does not have equivalent states.

Proof. Let S and T be two distinct subsets in 2 Q . Then, without loss of generality, there is a state q in Q with q ∈ S \ T . Since q is uniquely distinguishable, there is a word w which is accepted by A from and only from q. Therefore, the subset automaton of A accepts w from S and it rejects w from T . Hence w distinguishes S and T .

⊓ ⊔ Proposition 15. Let a state q of an NFA A = (Q, Σ, δ, s, F ) be uniquely distinguishable. Assume that there is a symbol a in Σ and exactly one state p in Q that goes to q on a, that is, (p, a, q) is a unique in-transition on a going to q.

Then the state p is uniquely distinguishable as well.

Proof. Let w be a word which is accepted by A from and only from q. The word aw is accepted from p since q ∈ δ(p, a) and w is accepted from q. Let r = p. Then q / ∈ δ(r, a) since (p, a, q) is a unique in-transition on a going to q. It follows that the word w is not accepted from any state in δ(r, a). Thus A rejects aw from r, so p is uniquely distinguishable.

⊓ ⊔

Now we can prove the following result.

Theorem 16. Let m, n 2. There exist ternary languages K and L with κ(K) = m and κ(L) = n such that the subset automaton of the NFA accepting K L does not have equivalent states.

Proof. Let m and n be arbitrary but fixed integers with m, n 2. Let K be accepted by the DFA K = ({1, 2, . . . , m}, {a, b, c}, δ K , 1, {m}), where for each i in {1, 2, . . . , m},

δ K (i, a) = i + 1 if i m -1 and δ K (m, a) = 1; δ K (i, b) = 1; δ K (1, c) = 2 and δ K (i, c) = 1 if i 2.
Let L be accepted by the DFA L = ({1, 2, . . . , n}, {a, b, c}, δ L , 1, {n}), where for each j in {1, 2, . . . , n},

δ L (j, a) = 1; δ L (j, b) = j + 1 if j n -1 and δ L (n, b) = 1; δ L (j, c) = n.
The DFAs K and L are shown in Fig. 2. Construct the NFA N for K L as described in Section 1 on page 2. The transitions on a, b, c in N for m = 4 and n = 5 are shown in Fig. 3. Notice that each state (i, j) with 2 i m and 2 j n has a unique in-transition on symbol a and this transition goes from state (i -1, j); see the dashed transitions in Fig. 3 (top-left). Next, each state (m, j) with 2 j n has a unique intransition on b which goes from (m, j -1), and each state (i, 2) with 2 i m has a unique in-transition on b going from (i, 1); see the dashed transitions in Fig. 3 (top-right). Finally, the state (2, 1) has a unique in-transition on c going from (1, 1); see the dashed transition in Fig. 3

(bottom).

The empty word is accepted by N from and only from the state (m, n) since this is a unique accepting state of N . Thus (m, n) is uniquely distinguishable. Next, consider the subgraph of unique in-transitions in N . Fig. 4 shows this subgraph in the case of m = 4 and n = 5. Notice that from each state of N , the state (m, n) is reachable in this subgraph. By Proposition 15, used repeatedly, we get that each state of N is uniquely distinguishable. Hence by Proposition 14, the subset automaton of N does not have equivalent states.

⊓ ⊔

Conclusions

We have examined the state complexity of the shuffle operation on two regular languages of state complexities m and n, respectively, and found an upper bound for it. We know that this bound can be reached for any m with 1 m 5 and any n 1, and also for m = n = 6. For the remaining values of m and n, however, the problem remains open. Since there exist two languages K and L for which all pairs of states in the subset automaton of the NFA accepting the shuffle K L are distinguishable, the main difficulty consists of proving that all valid states in the subset automaton can be reached for the witness languages.

Fig. 1 .

 1 Fig. 1. Witness DFAs K and L for shuffle with |QK | = 2, |QL| = 2.

  If there is a column U with |U | = 1 or |U | = 4, then by Sperner's theorem if n > 4 2 = 6, then S has a column containing another column; hence S can have only columns U with |U | = 3 or |U | = 2.

Fig. 2 .

 2 Fig. 2. The DFAs K and L.

Fig. 3 .Fig. 4 .

 34 Fig. 3. NFA N for m = 4 and n = 5; the transitions on a (top-left), b (top-right), and c (bottom).

Table 1 .

 1 Computational verification of reachability of the bound. The fields with * follow from the proofs of Subsection 2.1.

	m\n 2 3 4 5 6 7	8
	2		*
	3		*
	4		*
	5		*
	6	?	?
	7	?	?
	8		?

Table 3 .

 3 A subset and the equivalence classes of columns under ϕ =[START_REF] Brzozowski | Quotient complexity of ideal languages. Theoret[END_REF][START_REF] Câmpeanu | Tight lower bound for the state complexity of shuffle of regular languages[END_REF][START_REF]GAP -Groups, Algorithms, and Programming[END_REF][START_REF] Sperner | Ein Satz über Untermengen einer endlichen Menge[END_REF][START_REF] Okhotin | On the state complexity of scattered substrings and superstrings[END_REF].

	1 2 3 4 5 6 7 8

Acknowledgments

We would like to thank an anonymous referee for proposing the notions of a uniquely distinguishable state and of a subgraph of unique in-transitions which allow us to simplify the proof of distinguishability. We are also grateful for his comments and suggestions that helped us improve the presentation of the paper.

⋆ This work was supported by the Natural Sciences and Engineering Research Council of Canada under grant No. OGP0000871, by VEGA grant 2/0084/15, and by the National Science Centre, Poland under project number 2014/15/B/ST6/00615.


Galina Jirásková
email: jiraskov@saske.sk

Alexander Szabari
email: alexander.szabari@gmail.com

⋆⋆ Juraj Šebej
email: juraj.sebej@gmail.com

The Complexity of Languages Resulting from the Concatenation Operation

We prove that for all m, n, and α with 1 ≤ α ≤ f (m, n), where f (m, n) is the state complexity of the concatenation operation, there exist a minimal m-state DFA A and a minimal n-state DFA B, both defined over an alphabet Σ with |Σ| ≤ 2n+4, such that the minimal DFA for the language L(A)L(B) has exactly α states. This improves a similar result in the literature that uses an exponential alphabet.

Introduction

Iwama et al. [START_REF] Iwama | Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs[END_REF] stated the question of whether there always exists a minimal nondeterministic finite automaton (NFA) of n states whose equivalent minimal deterministic finite automaton (DFA) has α states for all integers n and α satisfying n α 2 n . The question was also considered by Iwama et al. [START_REF] Iwama | A family of NFAs which need 2 n -α deterministic states[END_REF], and answered positively in [START_REF] Jirásková | Magic numbers and ternary alphabet[END_REF] for a ternary alphabet. However, in the unary case, the existence of holes, so called "magic numbers", was proved by Geffert [START_REF] Geffert | Magic numbers in the state hierarchy of finite automata[END_REF]. The binary case is still open.

The same problem on sub-regular language families was studied by Holzer et al. [START_REF] Holzer | The magic number problem for subregular language families[END_REF]. It turned out that the existence of non-trivial magic numbers is rare, and that the ranges of possible complexities are usually contiguous. One interesting exception was obtained by Čevorová [START_REF] Čevorová | Kleene star on unary regular languages[END_REF]. She studied the star operation on unary regular languages, and proved that there are two linear segments of magic numbers in the range from 1 to (n -1) 2 + 1, that is, of values that cannot be met by the state complexity of the star of a unary language accepted by a minimal n-state DFA. On the other hand, she proved that for the square operation in the unary case no magic numbers exist [START_REF] Čevorová | On the square of regular languages[END_REF]. Another example of the existence of magic numbers for symmetric difference NFAs was presented by Zijl [START_REF] Zijl | Magic numbers for symmetric difference NFAs[END_REF], but they could possibly be trivial.

A similar problem for the reversal, star, and concatenation operation was studied in [START_REF] Jirásková | Preliminary version: On the state complexity of complements, stars, and reversals of regular languages[END_REF][START_REF] Jirásková | Concatenation of regular languages and descriptional complexity[END_REF], where it was shown that for all the three operations the whole range of possible complexities up to known upper bounds can be produced using an exponential alphabet.

The result for reversal and star was improved in [START_REF] Jirásková | Kleene closure on regular and prefix-free languages[END_REF][START_REF] Šebej | Reversal on regular languages and descriptional complexity[END_REF] by showing that a linear alphabet is enough to produce the whole range of complexities.

In this paper we complement these results, and show that a linear alphabet can also be used for the concatenation operation. We prove that for all m, n, and α with 1 ≤ α ≤ f (m, n), where f (m, n) is the state complexity of the concatenation operation, there exist a minimal m-state DFA A and a minimal n-state DFA B, both defined over an alphabet Σ with |Σ| ≤ 2n + 4, such that the minimal DFA for the language L(A)L(B) has exactly α states.

To get this result, we describe three constructions, in which we are able to get m-state and (n + 1)-state DFAs A i , B i for i = 1, 2, 3 from m-state and nstate DFAs A and B, by adding a new state to B, and by adding the transitions on two new symbols. Moreover, if the state complexity of the concatenation of L(A) and L(B) is α, then the state complexity of the concatenation of L(A i ) and L(B i ), i = 1, 2, 3, is 2α, 2α -1, and α + 1, respectively. As a results, we get a contiguous range of complexities from m + n + 1 up to known upper bound for a linear alphabet. To get complexities from 1 to m + n -1, we use a known result from [START_REF] Jirásková | Concatenation of regular languages and descriptional complexity[END_REF]. We deal with the value m + n separately, and use a binary alphabet here.

The paper is organized as follows. The next section contains some definitions and preliminary results. In Section 3, we recall known results concerning the state complexity of concatenation. In Section 4, we prove that the range of possible complexities for the languages resulting from the concatenation operation is contiguous from 1 up to known upper bound, and we show that a linear alphabet is enough for this. Section 5 contains some concluding remarks.

Preliminaries

In this section we give some basic definitions and preliminary results. For details, the reader may refer to [START_REF] Hopcroft | Introduction to automata theory and computation[END_REF][START_REF] Sipser | Introduction to the theory of computation[END_REF][START_REF] Yu | Chapter 2: Regular languages[END_REF].

Let Σ be a finite alphabet of symbols. Then Σ * denotes the set of strings over Σ including the empty string ε. The length of a string w is denoted by |w|, and the number of occurrences of a symbol a in a string w is denoted by # a (w). A language is any subset of Σ * . The concatenation of languages K and L is the language KL = {uv | u ∈ K and v ∈ L}. The cardinality of a finite set A is denoted by |A|, and its power-set by 2 A .

A nondeterministic finite automaton

(NFA) is a quintuple A = (Q, Σ, • , I, F ), where Q is a finite set of states, Σ is a finite alphabet, • : Q × Σ → 2 Q is the transition function which is extended to the domain 2 Q × Σ * in
the natural way, I ⊆ Q is the set of initial states, and F ⊆ Q is the set of final states. The language accepted by A is the set

L(A) = {w ∈ Σ * | I • w ∩ F ̸ = ∅}.
For a symbol a, we say that (p, a, q) is a transition in NFA A if q ∈ p • a, and for a string w, we write p w -→ q if q ∈ p • w. We say that (p, a, q) is an in-transition going to state q.

An NFA A is deterministic (DFA) (and complete) if |I| = 1 and |q • a| = 1 for each q in Q and each a in Σ. In such a case, we write q • a = q ′ instead of q • a = {q ′ }.

The state complexity of a regular language L, sc(L), is the smallest number of states in any DFA for L. The state complexity of a binary regular operation • is defined as a function f (m, n) given by [START_REF] Rabin | Finite automata and their decision problems[END_REF]. The DFA A ′ is called the subset automaton of the NFA A. The subset automaton may not be minimal since some of its states may be unreachable or equivalent to other states.

f (m, n) = max{sc(K • L) | K, L ⊆ Σ * , sc(K) = m, sc(L) = n}. Every NFA A = (Q, Σ, •, I, F ) can be converted to an equivalent DFA A ′ = (2 Q , Σ, • ′ , I, F ′ ), where R • ′ a = R • a and F ′ = {R ∈ 2 Q | R ∩ F ̸ = ∅}
In the following proposition, we provide a sufficient condition for an NFA, which guarantees that the corresponding subset automaton does not have equivalent states.

Proposition 1. Let N = (Q, Σ, • , I, F ) be an NFA. Assume that for each state q in Q, there is a string w q in Σ * which is accepted by N only from the state q, that is, we have q • w q ∩ F ̸ = ∅, and p • w q ∩ F = ∅ if p ̸ = q. Then the subset automaton of N does not have equivalent states.

Proof. Let S and T be two distinct subsets of the subset automaton. Then, without loss of generality, there is a state q with q ∈ S \ T . Then the string w q is accepted by the subset automaton from the subset S, but it is rejected from T .

⊓ ⊔

To describe string w q accepted by an NFA only from state q, we usually use the next observation.

Proposition 2. Let a string w q be accepted by an NFA N only from state q. If (p, a, q) is the unique in-transition going to state q by symbol a, then the string aw q is accepted by N only from state p.

In what follows, we often need to show how the set of all the reachable subsets in a subset automaton looks like. To do this, the following observation is useful.

Proposition 3. Let D be a subset automaton of an NFA N = (Q, Σ, •, I, F ). Let R be a family of subsets of Q such that (1) each subset in R is reachable in D, (2) I ∈ R, and (3) for each S in R and each symbol a in Σ, the set S • a is in R.
Then R is the family of all reachable subsets of DFA D.

Proof. Each set in R is reachable in D by [START_REF] Geffert | Magic numbers in the state hierarchy of finite automata[END_REF]. Let S be a reachable subset of D. Then there is a string w in Σ * such that S = I • w. We prove the proposition by induction on |w|. If |w| = 0, then w = ε and S = I • ε = I, which is in R by [START_REF] Holzer | The magic number problem for subregular language families[END_REF]. Now let w = va for a string v and a symbol a. By the induction hypothesis, the set

S ′ = I • v is in R. Then S = S ′ • a, so S is in R by (3). ⊓ ⊔

State Complexity of Concatenation

Consider minimal DFAs A and B. Without loss of generality, we assume that the state set of A is {q 0 , q 1 , . . . , q m-1 } with the initial state q 0 , and the state set of B is {0, 1, . . . , n -1} with the initial states 0. Moreover, in both A and B, let us denote the transition function by •. This is not confusing since the state sets of A and B are disjoint. First, let us recall the construction of an NFA for the language L(A)L(B).

Construction of NFA for concatenation:

( DFA A and DFA B → NFA N for L(A)L(B) ) Let A = ({q 0 , q 1 , . . . , q m-1 }, Σ, •, q 0 , F A ) and B = ({0, 1, . . . , n -1}, Σ, •, 0, F B ) be DFAs. Construct NFA N from DFAs A and B as follows:

(a) for each symbol a and each state q i with q i • a ∈ F A , add transition (q i , a, 0); (b) the set of initial states of N is {q 0 } if q 0 / ∈ F A , and it is {q 0 , 0} otherwise; (c) the set of final state of N is F B .

In the subset automaton of NFA N constructed as above, each reachable subset is of the form {q i }∪S, where S ⊆ {0, 1, . . . , n-1} since A is deterministic and complete. Moreover, if q i is a final state of A, then 0 ∈ S since N has the transition (q, a, 0) whenever a state q of A goes to a final state q i on a symbol a. It follows that the subset automaton of [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF][START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF]. We write this upper bound as (m -1)2 n + 2 n-1 . The bound is known to be tight if m ≥ 1 and n ≥ 2 [START_REF] Jirásek | State complexity of concatenation and complementation[END_REF][START_REF] Maslov | Estimates of the number of states of finite automata[END_REF][START_REF] Yu | The state complexity of some basic operations on regular languages[END_REF]. If m ≥ 1 and n = 1, then L = ∅ or L = Σ * , so the tight upper bound in this case is m. Hence we get the following result.

N has at most (m -k)2 n + k2 n-1 reachable states. Next we have (m -k)2 n + k2 n-1 = m2 n -k2 n-1 , which is maximal if k = 1

Proposition 4 ([6, 11, 16]). Let m, n ≥ 1 and f (m, n) be the state complexity of the concatenation operation on languages over an alphabet of size at least two defined as

f (m, n) = max{sc(KL) | K, L ⊆ Σ * , |Σ| ≥ 2, sc(K) = m, sc(L) = n}. Then we have f (m, n) = { m, if n = 1; (m -1)2 n + 2 n-1 , if n ≥ 2.

The Range of Possible Complexities

The aim of this section is to show that the whole range of complexities from 1 to f (m, n) for the concatenation operation can be produced using an alphabet that grows linearly with n.

To this aim consider minimal DFAs A = ({q 0 , q 1 , . . . , q m-1 }, Σ, •, q 0 , {q m-1 }), and B = ({0, 1, . . . , n -1}, Σ, •, 0, {1}). Construct an NFA N for L(A)L(B) as described in Section 3. Let D be the subset automaton of N , and R the family of all the reachable subsets in DFA D. We assume that A, B, N, D, and R satisfy the following conditions. (1) The transitions on symbols a, b, c in states in {q 0 , q 1 , . . . , q m-1 } ∪ {0, 1} are defined as in Fig. 1.

(2) If (q i , σ, q 0 ) is a transition in A for some σ in Σ, then i = m -1. (3) Each set in R \ { {q 0 } } is reachable from {q 1 } in the subset automaton D. (4)
For each state q of NFA N , there exists a string w q in Σ * accepted by N only from state q. Moreover, we have

w 1 = ε, w 0 = c, w qm-1 = bc, w qm-2 = cbc, w qm-2-i = a i cbc for i = 1,
{q 0 } a -→ {q 1 } a m-2 ---→ {q m-1 , 0} b -→ {q m-1 , 0, 1} c -→ {q m-2 , 0, 1}.
(b) Assume for a contradiction that there is a set S in R and a symbol σ such that S • σ = {q 0 }. Then we must have q m-1 ∈ S by [START_REF] Holzer | The magic number problem for subregular language families[END_REF]. It follows that the initial state 0 of B must be in S since q m-1 is final in A. However then S • σ ⊇ {q 0 , 0 • σ}, a contradiction.

(c) By (4), the NFA N satisfies the condition in Proposition 1. Therefore the subset automaton D of N does not have equivalent states, and we have sc(L(A)L(B)) = |R|. ⊓ ⊔ Now our goal is to construct a minimal m-state DFA A i and a minimal (n+1)state DFA B i for i = 1, 2, 3 over the alphabet Σ ∪ {a n , b n } from automata A and B, such that A, B, N, D, R satisfy conditions (1)-( 4), in such a way that A i and B i , the NFA N i for L(A i )L(B i ), the subset automaton D i of N i and the family R i of reachable states of D i satisfy conditions (1)-( 4). Moreover, if R = α, then

|R 1 | = 2α, |R 2 | = 2α -1, and |R 3 | = α + 1.
We construct automata A i and B i from automata A and B by adding a new state n to DFA B, and by adding the transitions on two new symbols a n and b n . The transitions on a n are the same in all the three constructions, and they guarantee that the string a n is accepted by N i only from state n. The transitions on b n are used to reach the set {q 0 , n} in D 1 , the set {q 1 , n} in D 2 and the set {q m-1 , 0, n} in D 3 . We have to be careful with condition (4), especially in the third construction. 1)-( 4). Let A i , B i for i = 1, 2, 3 be the DFAs resulting from Constructions 1, 2, 3, respectively. Let N i be an NFA for L(A i )L(B i ) constructed as described in Section 3, D i be the corresponding subset automaton, and R i be the family of all the reachable subsets in DFA D i . Then all these automata satisfy conditions ( 1)-( 4). Moreover, if

C1 C2 C3 σ ∈ Σ n → n n → n n c -→ 0 n σ -→ 0 • σ if σ ̸ = c an qi → qm-1 qi → qm-1 qi → qm-1 n → 1 n → 1 n → 1 j → 0 j → 0 j → 0 bn qm-1 → q0 qm-1 → q1 qi → qm-1 if i ̸ = m -1 qi → qm-1 if i ̸ = m -1 qi → qm-1 n → n n → n n → n j → n j → n j →
|R| = α, then |R 1 | = 2α, |R 2 | = 2α -1, and |R 3 | = α + 1.
Proof. Since we do not change transitions on symbols in Σ on states of A and B, condition (1) is satisfied. Since the only new transition to

q 0 is (q m-1 , b n , q 0 ) in Construction 1, condition (2) is satisfied in each A i .
In each N i , the string a n is accepted only from state n. Moreover, in B 1 and B 2 , state n goes to itself on each symbol in Σ. It follows that condition ( 4

R ⊆ R i for i = 1, 2, 3. Let us show that R 1 = R ∪ { S ∪ {n} | S ∈ R } , R 2 = R ∪ { S ∪ {n} | S ∈ R and S ̸ = {q 0 } } , R 3 = R ∪ { {q m-1 , 0, n} } . If S is in R then S is reachable in D,
so S can be reached from the initial state {q 0 } by a string u S over Σ. If moreover, S ̸ = {q 0 }, then, by (3), S is reached from {q 1 } by a string v S .

In

D 1 we have {q 0 } a -→ {q 1 } a m-2 ---→ {q m-1 , 0} bn -→ {q 0 , n} uS --→ S ∪ {n}. Thus R ∪ { S ∪ {n} | S ∈ R } ⊆ R 1 ,
and every new set S ∪ {n} can be reached from {q 1 }. Let us show that no other set is reachable in D 1 . For each set S in R and each σ in Σ, we have Finally, in

S • σ ∈ R, S • a n ∈ {{q m-1 , 0}, {q m-1 , 0, 1}}, S • b n ∈ {{q 0 , n}, {q m-1 , 0}, {q m-1 , 0, n}}, (S ∪ {n}) • σ = S • σ ∪ {n}, (S ∪ {n}) • a n = {q m-1 , 0, 1}
in R ∪ { S ∪ {n} | S ∈ R } . By Proposition 3, we have R 1 = R ∪ { S ∪ {n} | S ∈ R } , and, moreover, R 1 satisfies condition (3). Next, in D 2 we have {q 0 } a -→ {q 1 } a m-2 ---→ {q m-1 , 0} bn -→ {q 1 , n} vS -→ S ∪ {n} if S ̸ = {q 0 }. So every new set S ∪
D 3 we have {q 0 } a -→ {q 1 } a m-2 ---→ {q m-1 , 0}
bn -→ {q m-1 , 0, n}, so the new set {q m-1 , 0, n} is reached from {q 1 }. The transitions on a n are the same as above, and for each S in R and each σ in Σ, we have S • b n ∈ {{q m-1 , 0}, {q m-1 , 0, n}}. Next, for the new set {q m-1 , 0, n}, we have

{q m-1 , 0, n} • c = {q m-2 , 0, 1}, {q m-1 , 0, n} • σ = {q m-1 , 0} • σ if σ ∈ Σ and σ ̸ = c; {q m-1 , 0, n} • b n = {q m-1 , 0, n}. All the resulting subsets are in R ∪ { {q m-1 , 0, n} } . By Proposition 3, we have R 3 = { R ∪ {q m-1 , 0, n} } , and again, R 3 satisfies condition (3). ⊓ ⊔ Recall that f (m, n) = (m -1)2 n + 2 n-1
is the state complexity of concatenation if n ≥ 2. Our first aim is to show that each value in the range from m+n+1 to f (m, n) may be attained by the state complexity of concatenation of m-state and n-state DFA languages provided that m ≥ 3. We show this by induction, with the basis proved in the next lemma. 1)-( 4) on page 5.

Proof. We first consider the values α = i(m -2) + 6 for i = 1, 2, 3, 4. Then we consider all the intermediate values of α. Finally we deal with the case α = m+3.

First let i = 1, so α = (m -2) + 6 = m + 4. Define a minimal m-state DFA A 1,0 = ({q 0 , q 1 , . . . , q m-1 }, {a, b, c, d}, •, q 0 , {q m-1 }) where for each i in {0, 1, . . . , m -1},

q i • a = q i+1 if i ̸ = m -1 and q m-1 • a = q m-1 , q i • b = q m-2 if i ̸ = m -1 and q m-1 • b = q m-1 , q i • c = q m-2 if i ̸ = m -2 and q m-2 • c = q m-1 , and
q i • d = q m-
{q 0 } a -→ {q 1 } a i-1 ---→ {q i } for i = 0, 1, . . . , m -2, {q m-2 } a -→ {q m-1 , 0} b -→ {q m-1 , 0, 1} c -→ {q m-2 , 0, 1}, {q m-1 , 0} d -→ {q m-2 , 0} c -→ {q m-2 , 1}.
Thus the subset automaton has m + 4 reachable subsets. Next, notice that each of these m + 4 subsets goes to some of them by each symbol in {a, b, c, d}. By Proposition 3, no other set is reachable, so the complexity of L(A 1,0 )L(B 1,0 ) is m + 4. Notice that all the possible subsets containing states q m-1 and q m-2 are reachable in D 1,0 . Now we construct appropriate DFAs from automata A 1,0 and B 1,0 by adding transitions on new symbols. Thus we do not change the transitions on symbols a, b, c, d, and therefore the conditions (1) and ( 4) are always satisfied. Moreover, for each new symbol, the new transition is defined in such a way that condition (2) is satisfied as well. Finally, notice that {q m-1 , 0} is reachable from {q 1 } by a m-2 in the subset automaton D 1,0 . In what follows, we always reach new subsets in the corresponding subset automata for concatenation from the subset {q m-1 , 0}. Hence condition ( 3) is always satisfied.

Next, let α = 2(m -2) + 6. Construct DFAs A 2,0 , B 2,0 from DFAs A 1,0 , B 1,0 by adding the transitions on a new symbol e 0 as follows:

q m-1 • e 0 = q 0 and q i • e 0 = q m-1 for i = 0, 1, . . . , m -2; 0 • e 0 = 0 and 1 • e 0 = 0. Construct the NFA N 2,0 for L(A 2,0 )L(B 2,0 ). In the subset automaton D 2,0 , all the sets that were reachable in the subset automaton D 1,0 are reachable as well, since the transitions on the old symbols a, b, c, d are the same. For the same reason, the NFA N 2,0 satisfies (4), and therefore the subset automaton D 2,0 does not have equivalent states. Next, in D 2,0 , we have

{q m-1 , 0} e0 -→ {q 0 , 0} a i -→ {q i , 0} for i = 1, 2, . . . , m -3.
No other new set is reachable since each set {q i , 0} goes either to a set {q j , 0} or to a set containing q m-2 or q m-1 by each symbol in {a, b, c, d, e 0 }, and moreover, by e 0 , each set goes either to {q 0 , 0} or to a set containing q m-1 . Therefore the resulting complexity of the concatenation L(A 2,0 )L(B 2,0 ) is 2(m -2) + 6.

In a similar way, we construct DFAs A 3,0 , B 3,0 from A 2,0 , B 2,0 by adding transitions on a new symbol e 01 defined as follows:

q m-1 • e 01 = q 0 and q i • e 01 = q m-1 for i = 0, 1, . . . , m -2; 0 • e 01 = 0 and 1 • e 01 = 1. This results in the reachability of m -2 new subsets {q i , 0, 1} in the subset automaton of N 3,0 . Since no other new set is reachable, the complexity of

L(A 3,0 )L(B 3,0 ) is 3(m -2) + 6.
Finally, construct DFAs A 4,0 , B 4,0 from A 3,0 , B 3,0 by adding the transitions on a new symbol e 1 defined as q m-1 • e 1 = q 0 and q i • e 1 = q m-1 for i = 0, 1, . . . , m -2; 0 • e 1 = 1 and 1 • e 1 = 1. This results in the reachability of subsets {q i , 1} in the subset automaton of N 4,0 , and the complexity of L(A 4,0 )L(B 4,0 ) is 4(m -2) + 6.

Up to now we have defined appropriate automata A i,0 and B i,0 for the values α = i(m -2) + 6 for i = 1, 2, 3, 4. Now let us consider an intermediate value α = i(m -2) + 6 + j where 1 ≤ i ≤ 3 and 1 ≤ j ≤ m -3. Construct DFAs A i,j and B i,j from automata A i,0 and B i,0 by adding the transitions on a new symbol f 1 as follows:

q m-1 • f 1 = q m-2-j and q i • f 1 = q m-1 for i = 0, 1, . . . , m -2; 0 • f 1 = 1 and 1 • f 1 = 1.
This results in the reachability of the following j new subsets in the subset automaton of N i,j :

{q m-1 , 0} f1 -→ {q m-2-j , 1} a -→ {q m-2-j+1 , 1} a -→ • • • a -→ {q m-3 , 1}.
Recall that the subset automaton of N i,0 has i(m -2) + 6 reachable states, and since i ≤ 3, the subsets {q i , 1} are unreachable in the subset automaton of N i,0 . Hence the resulting complexity of of L(A i,j )L(B i,j ) is i(m -2) + 6 + j as desired. Moreover, all the automata satisfy conditions (1)-( 4).

Finally notice that if A and B are DFAs over a, b, c shown in Fig. 1 then sc(L(A)L(B)) = m + 3. This concludes our proof.

⊓ ⊔

Now we are ready to prove the main lemma. Recall that the state complexity of concatenation is

f (m, n) = (m -1)2 n + 2 n-1 if n ≥ 2. Moreover, notice that we have f (m, n + 1) = (m -1)2 n+1 + 2 n = 2((m -1)2 n + 2 n-1 ) = 2f (m, n). Lemma 8. Let m ≥ 3 and n ≥ 2. For each α with m + n + 1 ≤ α ≤ f (m, n),
there exist a minimal m-state DFA A, and a minimal n-state DFA B, both defined over an alphabet Σ with |Σ| ≤ 2n + 4, such that sc(L(A)L(B)) = α.

Proof. We prove the claim by induction on n. Moreover, in the induction hypothesis, we assume that DFAs A and B, the corresponding NFA N for L(A)L(B) constructed as in Section 3, the subset automaton D of N , and the set R of reachable states of D satisfy conditions ( 1)-( 4) on page 5.

The basis, in which we have m ≥ 3, n = 2, and m+3

≤ α ≤ f (m, 2) = 4m-2, is proved in Lemma 7. Let m ≥ 3, n ≥ 2,
and assume that for each β with m + n + 1 ≤ β ≤ f (m, n), there exist a minimal m-state DFA A and a minimal n-state DFA B, both defined over an alphabet Σ with |Σ| ≤ 2n + 4, such that sc(L(A)L(B)) = β. Moreover, assume that DFAs A and B, the NFA N for L(A)L(B), the subset automaton D of N , and the set of reachable states R of D satisfy conditions (1)-(4) on page 5. Let us show that the claim holds for n + 1. To this aim let α be an integer with m + (n + 1) + 1 ≤ α ≤ f (m, n + 1).

First, let 2m + 2n + 2 ≤ α ≤ f (m, n + 1) and α be even. Let β = α/2. Then m+n+1 ≤ β ≤ f (m, n), and by the induction hypothesis, there exists a minimal m-state DFA A and a minimal n-state DFA B, both defined over an alphabet Σ with |Σ| ≤ 2n + 4, such that sc(L(A)L(B)) = β. Moreover, conditions (1)-( 4) are satisfied for A, B, N, D, R. We use Construction 1, in which we add a new state to DFA B and the transitions on two new symbols to get a minimal m-state A 1 and a minimal (n + 1)-state DFA B 1 . By Lemma 6, all conditions (1)-( 4) are satisfied for

A 1 , B 1 , N 1 , D 1 , and R 1 . It follows that sc(L(A 1 )L(B 1 )) = 2β = α. Now, let 2m + 2n + 1 ≤ α ≤ f (m, n + 1) -1 and α be odd. Let β = (α + 1)/2. Then m + n + 1 ≤ β ≤ f (m, n),
and we use the induction hypothesis and our Construction 2, to get automata A 2 and B 2 over

Σ ∪ {a n , b n } satisfying (1)-(4) such that sc(L(A 2 )L(B 2 )) = 2β -1 = α. Finally, if m + (n + 1) + 1 ≤ α ≤ 2m + 2n, we set β = α -1. Then m + n + 1 ≤ β ≤ f (m, n) since we have 2m + 2n -1 ≤ m2 n -2 n-1 if m ≥ 3 and n ≥ 2.
We use the induction hypothesis and Construction 3, get appropriate automata A 3 and B 3 , satisfying (1)-( 4) such that sc(L(A 3 )L(B 3 )) = β + 1 = α. Our proof is complete.

⊓ ⊔ Now we consider the case of m = 2 and n ≥ 2. In such a case, we only need to modify conditions (1)-( 4). All the proofs are the same as above, except for the base case, which is a bit more complicated in this case. Proof. We modify conditions ( 1)-( 4) as follows.

(1') The transitions on symbols a, b, c in states in {q 0 , q 1 } ∪ {0, 1} are defined as in Fig. 1 for m = 2. This means that the subsets {q 1 , 0}, {q 1 , 0, 1}, and {q 0 , 0, 1} are reachable in D, that is, they are in R.

(2') If (q i , a, q 0 ) is a transition in A, then i = 1 (3') Each set in R \ { {q 0 } } is reachable from {q 1 , 0} in the subset automaton D. ( 4
') For each state q of NFA N , there exists a string w q in Σ * which is accepted by N only from state q. Moreover, we have

w 1 = ε, w 0 = c, w q1 = bc, w q0 = cbc, w j = a j for j = 2, 3, . . . , n -1.
Now we continue with exactly the same constructions as in the case of m ≥ 3, and, using induction on n, we get the lemma.

⊓ ⊔

The case of m = 1 and n ≥ 3 is slightly different, although, the main idea is the same. Lemma 10. Let m = 1 and n ≥ 3. For each α with n+1 ≤ α ≤ f (1, n) = 2 n-1 , there exist a minimal 1-state DFA A, and a minimal n-state DFA B, both defined over an alphabet Σ with |Σ| = n -1, and such that sc(L(A)L(B)) = α.

Proof (Proof Idea).

Let A be a 1-state DFA accepting Σ * . We prove the lemma again by induction on n, where we assume that the following conditions hold for DFA B, the NFA N for Σ * B, constructed from B by adding a loop in the initial state 0 on each input symbol in Σ, for the subset automaton D of N , and the set R of reachable subsets in D:

(1") In DFA B, the transitions on a, b, c in states 0, 1, 2 are as in Fig. 2.

(2") In DFA B, we have 0 • σ ̸ = 0 for each σ ∈ Σ. (3") Each subset in R, except for the initial subset {0}, can be reached from the subset {0, 1}. (4") NFA N satisfies the condition in Proposition 1, that is, for each state j of N , there exists a string w j in Σ * which is accepted by N only from state j. Moreover, we have w 0 = c and w 1 = ε. The basis, in which we have n = 3 and n + 1 = f (1, 3) = 4, holds true since the 3-state DFA B shown in Fig. 2 satisfies (1")-(4").

For the induction step, we again describe three constructions: We construct (n + 1)-state DFAs B 1 , B We can show that all the resulting automata satisfy conditions (1")-(4"), and, moreover, if

|R| = β, then |R 1 | = 2β, |R 2 | = 2β -1, |R 3 | = β + 1. Since N and N i satisfy (4"), we have sc(L(A)L(B)) = |R| and sc(L(A i )L(B i )) = |R i |.
This proves the lemma by induction.

⊓ ⊔

Up to now we have considered the complexities in the range from m + n + 1 to f (m, n). The complexities from 1 to m + n -1 are covered by the following result from [START_REF] Jirásková | Concatenation of regular languages and descriptional complexity[END_REF]. Notice that this lemma also covers the case of m = 1 and n = 2, since then

f (1, 2) = 2 1 = 2 = m + n -1.

Lemma 11 ([8, Lemma 5]

). Let m, n ≥ 1. For each α with 1 ≤ α ≤ m+n-1, there exist a minimal m-state DFA A and a minimal n-state DFA B, both defined over an alphabet of at most two symbols, such that sc(L(A)L(B)) = α.

The next lemma shows that the complexity m + n can be produced. Then we consider the case of n = 1. Lemma 12. Let m ≥ 2, n ≥ 2. There exist binary regular languages K and L with sc(K) = m and sc(L) = n such that sc(KL) = m + n. Proof. Let K and L be the binary languages accepted by minimal DFAs A and B shown in Fig. 3, where for each i in {0, 1, . . . , m -1} and j in {0, 1, . . . , n -1}, we have

C1 C2 C3 σ ∈ Σ n → n n → n n → 0 an n → 1 n → 2 n → 1 j → n 0 → 1 j → 2 1 → n j → 0 if j ≥ 2 bn - - n → n j → n
q i • a = q i+1 if i ̸ = m -1, q m-1 • a = q m-1 and q i • b = q m-1 ; j • a = j + 1 if j ̸ = n -1, (n -1)
• a = 0, and j • b = n -1. Construct an NFA N from DFAs A and B by adding transitions (q m-2 , a, 0), (q m-1 , a, 0), and (q i , b, 0) for each i; the initial state of N is q 0 , and the set of final states is {n -1}. In the corresponding subset automaton, the initial subset is {q 0 }, and we have

{q 0 } a i -→ {q i } for i = 1, 2, . . . , m -2, {q m-2 } a -→ {q m-1 , 0} a j
-→ {q m-1 , 0, 1, . . . , j} for j = 1, 2, . . . , n -1, and

{q m-1 , 0} b -→ {q m-1 , 0, n -1}.
It follows that the subset automaton has m + n reachable subsets. Notice that each of these m + n subsets goes to some of them by a, and each of them goes to {q m-1 , 0} or to {q m-1 , 0, n -1} by b. By Proposition 3, no other set is reachable.

To prove distinguishability, let {q i }∪S and {q j }∪T be two distinct reachable subsets. Since NFA N accepts the string a n-1-t only from state t (0 ≤ t ≤ n-1), the two subsets are distinguishable if S ̸ = T . Next, if i < j, then we have

{q j } a m-1-j -----→ {q m-1 , 0} and {q i } a m-1-j -----→ {q m-1-(j-i) },
where the resulting subsets are distinguishable since they differ in a state of B. This proves distinguishability and concludes the proof. The next theorem summarizes our results, and shows that the whole range of complexities for the concatenation operation can be produced using an alphabet which grows linearly with n. Recall that f (m, n) is the state complexity of the concatenation operation on languages over an alphabet of size at least two and we have f (m, 1) = m and f (m, n) = (m -1)2 n + 2 n-1 if n ≥ 2. Theorem 14. Let m, n ≥ 1. For each α with 1 ≤ α ≤ f (m, n), there exist regular languages K and L defined over an alphabet Σ with |Σ| ≤ 2n + 4 such that sc(K) = m, sc(L) = n, and sc(KL) = α.

Proof. In each of the following six cases, we refer to the corresponding lemma dealing with this case: This covers all the possible cases, and proves the theorem. ⊓ ⊔

Conclusions

We investigated the state complexity of languages resulting from the concatenation operation. We proved that for all m, n, α with m, n ≥ 1 and 1 ≤ α ≤ f (m, n), where f (m, n) is the state complexity of the concatenation operation, there exist regular languages K and L defined over an alphabet of size at most 2n + 4 such that sc(K) = m, sc(L) = n, and sc(KL) = α. This improves the result from [START_REF] Jirásková | Concatenation of regular languages and descriptional complexity[END_REF], where an alphabet of size growing exponentially with n is used to produce the whole range of complexities for the concatenation operation. Our result complements similar results from [START_REF] Jirásková | Kleene closure on regular and prefix-free languages[END_REF][START_REF] Šebej | Reversal on regular languages and descriptional complexity[END_REF], where a linear alphabet is used to get the whole range of complexities for the reversal and Kleene closure operations.

A similar problem for the square operation, defined as L 2 = LL, remains open even for an exponential alphabet.

Fig. 1 .

 1 Fig. 1. Transitions on a, b, c in states in {q0, q1, . . . , qm-1} ∪ {0, 1}.

2 , 1 . 5 .

 215 . . . , m -2, and w j = a j for j = 2, 3, . . . , n -Proposition Let A, B, N , D, and R satisfy conditions (1)-(4). Then (a) The sets {q 1 }, {q m-1 , 0}, {q m-1 , 0, 1}, {q m-2 , 0, 1} are in R. (b) The initial subset {q 0 } of the subset automaton D cannot be reached from any other reachable subset of D. (c) The subset automaton D of NFA N does not have equivalent states, so sc(L(A)L(B)) = |R|. Proof. (a) By (1), the transitions on a, b, c are as in Fig. 1. It follows that in the subset automaton D, we have

  ) is satisfied for N 1 and N 2 . In B 3 , we have n• c = 0 and n • b = 0 • b = b. It follows that (0, c, 1) is the only transition on c going to state 1, and (q m-1 , b, 0) is the only transition on b going to state 0. It follows that (4) is satisfied for N 3 as well. Now consider the subset automata D 1 , D 2 , D 3 . Since we did not change transitions on symbols in Σ on states in A and B, we have

  , and (S ∪ {n}) • b n ∈ {{q 0 , n}, {q m-1 , 0, n}}. Using Proposition 5(a), we get that all the resulting sets are

  {n} is reached from {q 1 }. The transitions on each σ in Σ and on a n are the same as in Construction 1, and for each S in R, S • b n ∈ {{q 1 , n}, {q m-1 , 0}, {q m-1 , 0, n}}, and (S ∪ {n}) • b n ∈ {{q 1 , n}, {q m-1 , 0, n}}. All the resulting sets are in R ∪ { S ∪ {n} | S ∈ R and S ̸ = {q 0 } } . Moreover, {q 0 } cannot be reached from any other subset in R. By Proposition 3, we have R 2 = R ∪ { S ∪ {n} | S ∈ R and S ̸ = {q 0 } } . Moreover, R 2 satisfies condition (3).

Lemma 7 .

 7 Let m ≥ 3 and n = 2. For each α with m + 3 ≤ α ≤ f (m, 2) = 4m -2, there exist a minimal m-state DFA A and a minimal 2-state DFA B, both defined over an alphabet Σ with |Σ| ≤ 7, such that sc(L(A)L(B)) = α. Moreover, the corresponding NFA N for L(A)L(B), the subset automaton D of N , and the set R of reachable states of D satisfy conditions (

2 .

 2 Define a minimal two-state DFA B 1,0 = ({0, 1}, {a, b, c, d}, •, 0, {1}) where 0 • a = 0, and 1 • a = 1, 0 • b = 1, and 1 • b = 1, 0 • c = 1, and 1 • c = 0, 0 • d = 0, and 1 • d = 1. Construct NFA N 1,0 for L(A 1,0 )L(B 1,0 ), and let D 1,0 be the corresponding subset automaton. Notice that (1), (2), and (4) are satisfied. Next, in D 1,0 we have

Lemma 9 .

 9 Let m = 2, n ≥ 2. For each α with n + 3 ≤ α ≤ f (2, n) = 2 n + 2 n-1 ,there exist a minimal 2-state DFA A, and a minimal n-state DFA B, both defined over an alphabet Σ with |Σ| ≤ 2n + 4, and such that sc(L(A)L(B)) = α.

Fig. 2 .

 2 Fig. 2. Base case if m = 1.

wn an anc an Table 2 .Fig. 3 .

 23 Fig. 3. The minimal DFAs A and B with sc(L(A)L(B)) = m + n.

⊓ ⊔ Lemma 13 .Fig. 4 .

 134 Fig. 4. The minimal DFA A with sc(L(A) Σ * ) = α.

( 1 )

 1 If n = 1, then f (m, n) = m, and the theorem follows by Lemma 13. (2) If n ≥ 2 and 1 ≤ α ≤ m + n -1, then the theorem follows by Lemma 11. (3) If m = 1 and n = 2, then f (1, 2) = 2 = m + n -1, so this case is covered by Lemma 11 as well. (4) If m = 1, n ≥ 3, and m + n = n + 1 ≤ α ≤ f (1, n) = 2 n-1 , then the theorem follows by Lemma 10. (5) The case of m ≥ 2, n ≥ 2, and α = m + n follows by Lemma 12. (6) Finally, if m ≥ 2, n ≥ 2, and m + n + 1 ≤ α ≤ f (m, n), then the theorem follows by Lemma 9 if m = 2, and by Lemma 8 if m ≥ 3.

Table 1 .

 1 n New Construct DFAs A 2 and B 2 from DFAs A and B as follows: (1) add a new state n to DFA B going to itself on each old symbol σ in Σ; (2) add the transitions on two new symbols a n and b n as shown in Table 1 in column C2. (2) add the transitions on two new symbols a n and b n as shown in Table 1 in column C3. Let A, B, N, D, R satisfy conditions (

	Construction 2. (α → 2α -1)
	Construction 3. (α → α + 1)
	Construct DFAs A

transitions; i ∈ {0, 1, . . . , m -1}, j ∈ {0, 1, . . . , n -1}.

Construction 1. (α → 2α)

Construct DFAs A 1 and B 1 from DFAs A and B as follows:

(1) add a new state n to DFA B going to itself on each old symbol σ in Σ;

(2) add the transitions on two new symbols a n and b n as shown in Table

1

in column C1. 3 and B 3 from DFAs A and B as follows: (1) add a new state n to DFA B with n • c = 1 and n • σ = 0 • σ if σ ∈ Σ \ {c};

  2 , B 3 from DFA B by adding a new state n, and by adding transitions on new symbol a n , b n , as shown in Table 2 in columns C1, C2, and C3, respectively.

⋆ Research supported by grant VEGA 2/0084/15. ⋆⋆ Research supported by grant VEGA 1/0142/15.