Andrea Herrmann

Martin Kutrib

Andreas Malcher

Matthias Wendlandt

Descriptional Complexity of Bounded Regular Languages

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Descriptional complexity is an area of theoretical computer science in which one of the main questions is how succinctly a formal language can be described by a formalism in comparison with other formalisms. A fundamental result is the exponential trade-off between nondeterministic (NFA) and deterministic finite automata (DFA) [START_REF] Meyer | Economy of description by automata, grammars, and formal systems[END_REF]. A further exponential trade-off is known to exist between unambiguous and deterministic finite automata, whereas the trade-offs between alternating and deterministic finite automata [START_REF] Leiss | Succinct representation of regular languages by Boolean automata[END_REF] as well as between deterministic pushdown automata and deterministic finite automata [START_REF] Valiant | Regularity and related problems for deterministic pushdown automata[END_REF] are bounded by doubly-exponential functions.

The question of whether the costs for determinization remain exponential even for subclasses of the regular languages, called subregular language classes, has been studied in [START_REF] Chrobak | Finite automata and unary languages[END_REF][START_REF] Chrobak | Errata to "Finite automata and unary languages[END_REF] for unary languages and in [START_REF] Salomaa | NFA to DFA transformation for finite languages over arbitrary alphabets[END_REF] for finite languages. A systematic study of the problem for subregular language classes is provided in [START_REF] Bordihn | Determination of finite automata accepting subregular languages[END_REF]. In this paper, we study with bounded regular languages another subregular language class which has not gained much attention yet apart from the fundamental paper [START_REF] Ginsburg | Bounded regular sets[END_REF] in which bounded regular languages are introduced and, for example, characterization theorems are established. In general, a language is called (strongly) bounded if it is a subset of a * 1 a * 2 • • • a * k , where a 1 , a 2 , . . . , a k are (pairwise distinct) symbols. Bounded languages have been investigated to a large extent in the literature. We would like to mention that basic results are summarized in [START_REF] Ginsburg | The Mathematical Theory of Context-Free Languages[END_REF] and that there exist strong connections to counter machines which are shown, for example, in [START_REF] Ibarra | Reversal-bounded multicounter machines and their decision problems[END_REF][START_REF] Ibarra | Characterizations of bounded semilinear languages by oneway and two-way deterministic machines[END_REF]. The descriptional complexity of bounded context-free languages has first been studied in [START_REF] Malcher | Descriptional complexity of bounded context-free languages[END_REF] and recently in [START_REF] Ibarra | On bounded languages and reversal-bounded automata[END_REF].

In this paper, we start to investigate the descriptional complexity of bounded regular languages. We provide the necessary definitions and notions in Section 2. Additionally, we summarize the closure properties for (strongly) bounded regular languages. In Section 3 we compute the costs for determinizing NFAs accepting strongly bounded regular languages. As bounded languages are both an extension of unary languages and a restriction of arbitrary languages, we obtain a 'similar' result for the upper bound of the determinization costs that turns out to be larger than the costs for determinizing unary NFAs, but lower than the costs for determinizing arbitrary NFAs. Finally, we study in Section 4 the deterministic operation problem for bounded regular languages which quantifies the costs (in terms of states of a DFA) of operations on (strongly) bounded regular languages such as union, intersection, concatenation, iteration, and reversal. The deterministic operation problem for regular languages has initially been studied in [START_REF] Yu | State complexity of regular languages[END_REF][START_REF] Yu | The state complexities of some basic operations on regular languages[END_REF]. Nowadays, there exists a vast literature on the deterministic and nondeterministic operational state complexity of subregular languages, and we refer to the recent survey [START_REF] Gao | A survey on operational state complexity[END_REF]. Here, we complement these findings with the results for (strongly) bounded regular languages. It should be noted that we devise a new tool to obtain lower bounds for bounded regular languages which may be of interest on its own.

Preliminaries and Closure Properties

Let Σ * denote the set of all words over the finite alphabet Σ. The empty word is denoted by λ, and Σ + = Σ * \ {λ}. The reversal of a word w is denoted by w R . For the length of w we write |w|. For the number of occurrences of a symbol a in w we use the notation |w| a . We denote the powerset of a set S by 2 S . By gcd(x 1 , x 2 , . . . , x k ) we denote the greatest common divisor of the integers x 1 , x 2 , . . . , x k , and by lcm(x 1 , x 2 , . . . , x n ) their least common multiple. If two numbers x and y are relatively prime, that is gcd(x, y) = 1, we write x ⊥ y.

A nondeterministic finite automaton (NFA) is a system M = S, Σ, δ, s 0 , F , where S is the finite set of internal states, Σ is the finite set of input symbols, s 0 ∈ S is the initial state, F ⊆ S is the set of accepting states, and

δ : S × Σ → 2 S is the partial transition function. The language accepted by M is L(M ) = { w ∈ Σ * | δ(s 0 , w) ∩ F = ∅ }, where the transition function is recur- sively extended to δ : S × Σ * → 2 S .
A finite automaton is deterministic (DFA) if and only if |δ(s, a)| = 1, for all s ∈ S and a ∈ Σ. In this case we simply write δ(s, a) = p for δ(s, a) = {p} assuming that the transition function is a mapping δ : S × Σ → S. So, any DFA is complete, that is, the transition function is total, whereas for NFAs it is possible that δ maps to the empty set.

A language L ⊆ Σ * is said to be bounded if and only if

L ⊆ a * 1 a * 2 • • • a * k , for k ≥ 1 and a i ∈ Σ, 1 ≤ i ≤ k.
It is strongly bounded if all letters a 1 , a 2 , . . . , a k are pairwise different. It should be noted that in the literature bounded languages which are defined as above are often called letter-bounded languages. Moreover, if symbols a 1 , a 2 , . . . , a k are replaced by fixed words w 1 , w 2 , . . . , w k , a language

L ⊆ w * 1 w * 2 • • • w * k is called word-bounded.
However, in this paper we confine ourselves to investigating only bounded and strongly bounded languages over symbols.

The closure properties of bounded and strongly bounded languages are summarized in Table 1. Although both language classes are not closed under all operations, it is well known that the regular languages are closed under all operations. This allows to study the deterministic state complexity of all operations for (strongly) bounded regular languages.

Determinization

It is well known that the costs for the simulation of a nondeterministic finite automaton with n states by a deterministic finite automaton can be limited by 2 n many states using the power set construction. On the other hand, several different NFAs are known that reach this bound exactly. In the unary case the upper bound as well as the lower bound collapses to e Θ( √ n•log n) . Considering the costs for determinization in the strongly bounded regular case, one may expect that the bounds for the conversion might be strictly in between the bounds for the general and the unary case. In the following, we present an upper bound which is slightly more costly than in the unary case. Proof. Given an NFA A = S, Σ, s 0 , δ, F with n states accepting a strongly bounded regular language L(A) over the alphabet Σ, we will construct an equivalent DFA. We may assume that Σ = {a 1 , a 2 , . . . , a k } and

L(A) ⊆ a * 1 a * 2 • • • a * k with k ≥ 2 and pairwise distinct a i ∈ Σ with 1 ≤ i ≤ k.
The principal idea of the construction is to divide automaton A into 'unary' sections S a1 , S a2 , . . . , S a k according to the read input symbols, to determinize these unary subautomata, and finally to reassemble the different deterministic subautomata to an equivalent DFA. In the first step, we construct an equivalent NFA A with the property that each state of A has incoming edges with at most one type of symbol. We define A = S , Σ, s 0 , δ , F , where s 0 is a new state,

S = { s x | s ∈ S, x ∈ Σ } ∪ {s 0 } and F = { s x | s ∈ F, x ∈ Σ } ∪ { s 0 | s 0 ∈ F }.
If s ∈ δ(s, a) for some s, s ∈ S and a ∈ Σ, then define s a ∈ δ (s x , a) for all x ∈ Σ. If s ∈ δ(s 0 , a) for some s ∈ S and a ∈ Σ, then define s a ∈ δ (s 0 , a).

The number of states of A is at most n • |Σ| + 1. Now, each state of A has incoming edges with at most one type of symbol and a state s a is defined to be in section S a of A , for a ∈ Σ. Furthermore, the initial state s 0 of A is only visited in the first computation step and then never again. It is the single state in the special section S init . The next step is to modify A in such a way that it has no states having more than one edge to another section labeled with the same symbol. Assume that there is some state s ∈ S having ≥ 2 edges labeled with a leading to section S a . Then we add a new state s to section S a , add for every edge from s labeled with an a to some state s in S a an edge from s labeled with λ to the state s , and replace the old edges by one edge from s to s labeled with a. These modifications introduce at most |Σ| new states for every state as well as λ-moves to the NFA, but preserve the given language. Moreover, for every input symbol a ∈ Σ, all nondeterministic moves on a take place inside section S a . The number of states of

A is now at most n • |Σ| 2 + |Σ|.
The first two steps of the construction based on the example NFA shown in Figure 1 are depicted in Figure 2.

In the following, the sections are successively determinized. We start with the determinization of the first section S a1 having n 1 many states and define the set I a1 of incoming states as the set of all states with incoming edges from other sections. Here, I a1 = δ (s 0 , a 1 ) consists of one state only, since there are no states having more than one edge to another section labeled with the same symbol. Additionally, we define the set O a1 of states with outgoing edges to other sections as O a1 = { s ∈ S a1 | r ∈ δ (s, a j ) for some r ∈ S and k ≥ j > 1 }. For the state s ∈ I a1 we construct an NFA A s as subautomaton of A with Fig. 2. The first two steps of the construction of A . States 00 and 07 are added so that the initial state has no incoming edges and every state has only incoming edges with the same label. State i is added to ensure that there are no states having more than one edge to another section labeled with the same symbol.

state set S a1 and s as initial state. Furthermore, all edges labeled with a i such that i = 1 are removed. Finally, we eliminate λ-moves applying the construction given in [START_REF] Hopcroft | Introduction to Automata Theory, Languages, and Computation[END_REF] which does not increase the number of states. Additionally, we set all outgoing states from O a1 as accepting. This is done to avoid that states with outgoing edges possibly disappear in the determinization process. Such states will later be rechanged to non-accepting states and completed with the outgoing edges to other sections. Thus, the NFA A s accepts the unary language { w ∈ a * 1 | δ (s, w) ∩ (F ∪ O a1 ) = ∅ } and has at most n 1 states. Next, we apply the construction given in [START_REF] Chrobak | Finite automata and unary languages[END_REF] to obtain a DFA A s such that L(A s ) = L(A s ). According to [START_REF] Chrobak | Finite automata and unary languages[END_REF] on A by replacing automaton A s in section S a1 of A by its deterministic version. Additionally, let s be the initial state of the DFA A s , then all transitions in A that link to state s are redirected to the initial state s of A s . As a result of the construction, the DFA A s implemented in A has two different types of accepting states. The first type are the original accepting states where some input is accepted in A . The second type are the states where the outgoing edges have to be placed. These have to be changed into non-accepting states and the outgoing edges have to be added to A .

To find out which states in section S a1 have to be accepting and which states have to be connected with other sections, we do the following considerations. Let B be an NFA accepting a unary language having a single accepting state. Then the lengths of the words of the accepted language L(B) can be described by a finite set E of equations of the form g(x) = z g •x+y g , where x, y g , z g ≥ 0 are integers (see, for example, [START_REF] Chrobak | Finite automata and unary languages[END_REF]). Looking at the equivalent DFA B , we obtain that for each equation g ∈ E there are one or more accepting states in B indicating the divisibility of the input words according to g. Now, we consider again for state s ∈ I a1 the NFA A s and its equivalent DFA A s . First, we set all states in A s non-accepting. Second, for every accepting state f in A s such that f ∈ F (thus, being an original accepting state in A ), we consider an NFA A s,f based on A s where f is the only accepting state and we determine the set of equations E for A s,f . Based on the obtained divisibilities we set the corresponding states in A s as accepting. Third, for every outgoing state o ∈ O a1 linking with input symbol a j to some state s j ∈ S j for some k ≥ j > 1, we consider an NFA A s,o based on A s where o is the only accepting state and we determine the set of equations E for A s,o . Based on the obtained divisibilities we add to the corresponding states in A s outgoing edges labeled with a j to state s j . We notice that this adding of edges may introduce nondeterminism in A s . To remove such possible nondeterministic moves, we do the following: for every state q ∈ A s having more than one outgoing edges labeled by some a j with k ≥ j > 1, we introduce a new state p to section S aj , replace all outgoing a j -edges from q by outgoing λ-edges from p, and add one a j -edge from q to p. Note that the removing of nondeterministic moves adds at most 1 states to each section S aj . Finally, we rename the NFA A with a determinized section S a1 to A and start the determinization of the next section S a2 .

Again, we define the set I a2 of states with incoming edges from other sections and the set O a2 of states with outgoing edges to other sections. Formally,

I a2 = { s ∈ S a2 | s ∈ δ (r, a 2 )
for some r ∈ S and r ∈ δ (q, a 2 ) for all q ∈ S },

O a2 = { s ∈ S a2 | r ∈ δ (s, a j ) for some r ∈ S and k ≥ j > 2 }.
For each state s in I a2 we construct an automaton A s in a similar way as above. Thus, A s accepts the unary language { w ∈ a * 2 | δ (s, w)∩(F ∪O a2 ) = ∅ } and has at most n 2 + 1 states, if s has been added by removing nondeterministic moves in the previous step, and at most n 2 states otherwise. Next, we determinize A s and obtain an equivalent DFA A s with at most

e Θ √ (m+1)•log(m+1) = e Θ √ m•log(m) = 1
many states. Then we construct an NFA A based on A by replacing automaton A s in section S a2 of A by its deterministic version and all transitions in A that link to state s are redirected in A to the initial state of A s . Finally, we determine the accepting states of A s as well as the connections from outgoing states to other sections, and we remove possibly introduced nondeterminism.

Having done this for all s ∈ I a2 we rename the NFA A with determinized sections S a1 and S a2 again to A . The size of the determinized section S a2 can be calculated as follows: we have at most m

+ 1 = e Θ √ m•log(m) = 1 states in I a2 .
Each determinization costs at most 1 states. Thus, we obtain 2 = 2 1 as an upper bound for the determinization costs of section S a2 . Again, note that the removing of nondeterministic moves adds at most 2 states to each section S aj with k ≥ j > 2.

We continue the construction by determinizing successively the following sections in a similar way as described above. The costs for determinizing section S ai with 3 ≤ i ≤ k can be calculated as follows. There are at most

m + 1 + 2 + • • • + i-1
states in I ai and each determinization costs at most 1 states. By setting i = i 1 , we obtain i • i as total upper bound. After determinizing all sections S a1 , S a2 , . . . , S a k we obtain a DFA A being equivalent to A and the number of states of A is bounded by the function

1 + 1 + 2 2 + • • • + k • k ≤ k 2 k 1 = |Σ| 2 • e |Σ|•Θ √ m•log(m) .

Deterministic Operational State Complexity

This section is devoted to studying the deterministic operational state complexity of the family of strongly bounded regular languages, that is, the languages are given by DFAs. Clearly, the known upper bounds for general regular languages apply also here. Moreover, every unary language is also (strongly) bounded. So, the known lower bounds for unary languages apply here as well. In [START_REF] Yu | The state complexities of some basic operations on regular languages[END_REF] it has been shown that the tight bounds for Boolean operations coincide for general regular and unary regular languages. In the unary case the lower bound requires the numbers of states to be relatively prime. In [START_REF] Pighizzini | Unary language operations, state complexity and Jacobsthal's function[END_REF] unary regular languages are studied whose deterministic state complexities are not relatively prime. Here we can derive the following corollary for strongly bounded regular languages.

Corollary 2. For any integers m, n ≥ 1 let A be an m-state and B be an n-state DFA that accept strongly bounded languages.

1. Then m states are sufficient and necessary in the worst case for a DFA to accept the language L(A). Notice that the languages L(A) ∪ L(B) and L(A) are not necessarily strongly bounded. However, since they are regular they are accepted by DFAs in any case.

In the following, we turn to the operations reversal, iteration, and concatenation for which the deterministic state complexities of general and unary languages are different (see, for example, the summary in Table 2). So, an immediate question is to what extent the state complexity of strongly bounded languages is strictly in between both cases. Since the deterministic state complexities for unary languages are well known, we suppose that the strongly bounded languages that are investigated in the remainder of this section are defined over an alphabet of size at least two. In other words, we consider strongly bounded languages

L ⊆ a * 1 a * 2 • • • a * k such that k ≥ 2.

A Tool for Constructing Lower Bound Witnesses

A widely used method to show lower bounds is to define an infinite family of witness languages so that the sizes of the minimal automata accepting them establish the bound. In order to allow the construction of witnesses as well as to determine the necessary sizes of the automata, lower bound techniques are very helpful. For example, in proofs dealing with the nondeterministic state complexity on regular languages specified by NFAs, the so-called fooling set technique can be used [START_REF] Birget | Intersection and union of regular languages and state complexity[END_REF][START_REF] Glaister | A lower bound technique for the size of nondeterministic finite automata[END_REF].

Here we first present a tool for the definition of lower bound witnesses, that is, for the construction of DFAs accepting (strongly) bounded languages. The idea is based on the number of possibilities to color a cycle of a DFA whose edges are labeled with the same input letter. All cycles in a DFA accepting a (strongly) bounded language have this unary form. We use the two colors gray (g) and white (w).

Let S c be a (sub)set of states of a given DFA that build a cycle on some fixed input letter. The set of all colorings of S c with colors from {g, w} is For the clarity of presentation, colorings are written as words. For example, coloring f 1 can be written as ggww, and the set of all such colorings is X = {wwww, gwww, wgww, . . . , gggg}. Moreover, a coloring can be uniquely identified by the set of states that are colored by w. For example, f 1 is given by {3, 4}.

X = { f | f : S c →
Two colorings f 1 and f 2 are said to be equivalent if f 1 can be obtained from f 2 by applying the transition function. More precisely, two colorings f 1 and f 2 are equivalent if and only if there is some ≥ 0 so that f 1 (i) = f 2 (δ(i, x )), for all i ∈ S c . Here, S c is the set of cycle states and the cycle is on input symbol x.

Example 4. Let f 2 ∈ X with f 2 (1) = w, f 2 (2) = g, f 2 (3) = g,
and f 2 (4) = w be the coloring shown at the bottom of Figure 3. Then f 1 and f 2 are equivalent, since f 1 (i) = f 2 (δ(i, b)), for all i ∈ {1, 2, 3, 4}. Now, we turn to determine the number of possibilities to color a cycle with inequivalent colorings. The number depends only on the number of states in the cycle. For example, for four states we obtain the following equivalence classes {wwww}, {gwww, wgww, wwgw, wwwg}, {ggww, wggw, wwgg, gwwg}, {gggg}, {gggw, wggg, gwgg, ggwg}, and {gwgw, wgwg}, and thus six possibilities. Now we consider the cyclic group G generated by the cyclic permutation (12

• • • |S c |)
. The group naturally operates on S c . Moreover, for σ ∈ G and f ∈ X, let σf ∈ X be defined as σf (s) = f (σ -1 (s)), for all s ∈ S c . With this operation, G acts on the set X of colorings as well. So, two colorings are equivalent if and only if they are in the same orbit of G. Therefore, the number of possibilities to color a cycle with inequivalent colorings coincides with the number of orbits of G acting on X. This number can be determined by Polya's enumeration lemma that is a generalization of the well-known Burnside lemma on the number of orbits of a group action on a set (see, for example, [START_REF] Erickson | Introduction to Combinatorics[END_REF]Chapter 8]). In the particular case of a cyclic group generated by a cyclic permutation (12 • • • n) and two colors, the number or orbits is

1 n d|n ϕ(d) • 2 n d
, where d|n denotes the positive divisors of n and ϕ(d

) = |{ 1 ≤ k ≤ d | gcd(k, d) = 1 }| is Euler's func- tion.
For example, for n = 4 we have d|n = {1, 2, 4}. Since ϕ(1) = 1, ϕ(2) = 1, and ϕ(4) = 2, the number of orbits and, identically, the number of inequivalent colorings is 1 4 (1

• 2 4 + 1 • 2 4 2 + 2 • 2 4 4 ) = 6.

Reversal, Concatenation, and Iteration

The first operation we consider in detail is the reversal. It turns out that the upper bound and lower bound can be described by an exponential function which is slightly smaller than in the case of arbitrary regular languages. On the other hand, in comparison with unary regular languages we obtain an exponential increase. The upper bound in the bounded case is derived from the observation that any DFA accepting some bounded language over an alphabet with at least two elements must have a rejecting sink state.

Theorem 5. Let k, n ≥ 2 be two integers and A be an n-state DFA that accepts a (strongly) bounded language

L(A) ⊆ a * 1 a * 2 • • • a * k .
Then 2 n-1 states are sufficient for a DFA to accept the language L(A) R .

Proof. Every non-unary DFA A = S, Σ, δ, s 0 , F accepting a (strongly) bounded language necessarily has a rejecting sink state, say e ∈ S. Now an NFA for the reversal of L(A) is constructed by interchanging the initial state with the accepting states and reversing the direction of the transitions. The NFA is determinized which yields a DFA A = 2 S , Σ, δ , s 0 , F accepting L(A) R . Since for all states p, q ∈ 2 S so that p = q ∪{e} we have δ (p, v) ∈ F if and only if δ (q ∪{e}, v) ∈ F if and only if δ (q, v) ∈ F , for all v ∈ Σ * , the states p and q are equivalent. We conclude that A has at most 2 n-1 states.

In order to show the lower bound 2 n-2 + 1 the coloring of cycles is exploited. Next, the construction of the witness DFAs is given, then we analyze a witness for six states. Finally, the general case is proven.

Let n > 3 be an integer. The DFA A n = S n , Σ, δ n , 0, {n -2} is constructed as follows (see Figure 4): S n = {0, 1, . . . , n -2, e} where e denotes the rejecting

sink state, Σ = {a, a 1 , a 2 , . . . , a k } with k = 1 n-2 d|n-2 ϕ(d) • 2 n-2 d
-1, and

δ n (i, a) = (i + 1) mod n -2 for 0 ≤ i ≤ n -3 e otherwise .
The transition function is still incomplete. Now we consider the colorings of the cycle, that is, of the states {0, 1, . . . , n -3}, whereby we disregard gg • • • g. From above it is known that there remain k

= 1 n-2 d|n-2 ϕ(d) • 2 n-2 d
-1 inequivalent colorings. From each equivalence class M j one element m j , 1 ≤ j ≤ k, is chosen and identified by the states that are colored white. For example, wwgw is identified by {0, 1, 3}. Now, the definition of the transition function is completed by setting

δ n (i, a j ) = n -2 if i ∈ m j e otherwise for 1 ≤ j ≤ k. The DFA A n accepts the language L(A n ) = k j=1 i∈mj (a n-2 ) * a i a j ⊆ a * a * 1 a * 2 • • • a * k . 0 2 • • • n -4 n -3 n -2 a a a a a a X 0 X 1 X 2 X n-4 X n-3
start Fig. 4. The witness DFA An reversal. The set of all aj with i ∈ mj are denoted by Xi. Edges to the rejecting sink state are omitted.

Example 6. There are six inequivalent possibilities to color the 4-state cycle of A 6 . Disregarding the coloring where all states are gray, the five equivalence classes in question are

M 1 = {{0}, {1}, {2}, {3}}, M 2 = {{0, 1}, {1, 2}, {2, 3}, {3, 0}}, M 3 = {{0, 2}, {1, 3}}, M 4 = {{0, 1, 2}, {1, 2, 3}, {2, 3, 0}, {3, 0, 1}}, M 5 = {{0, 1, 2, 3}}. Choosing m 1 = {3}, m 2 = {2, 3}, m 3 = {1, 3}, m 4 = {1, 2, 3}, m 5 = {0, 1, 2, 3} yields X 0 = {a 5 }, X 1 = {a 3 , a 4 , a 5 }, X 2 = {a 2 , a 4 , a 5 }, X 3 = {a 1 , a 2 , a 3 , a 4 , a 5 } in Figure 4.
Theorem 7. For any integer n > 3, there exists an n-state DFA A that accepts a (strongly) bounded language such that any DFA accepting L(A) R needs at least 2 n-2 + 1 states.

Proof. We use the DFA A n = S n , Σ, δ n , 0, {n -2} from above as witness. To show that A n is minimal, consider two states p, q ∈ {0, 1, . . . , n -3}. Let M r denote the equivalence class with the colorings that color only one state white, and let m r = {s}. Then δ n (p, a x a r ) = n -2 and δ n (q, a x a r ) = n -2, for x = n -2 -|p -s|, since a r sends only state s to the sole accepting state n -2. Clearly, the states n -2 and p ∈ {0, 1, . . . , n -3} are inequivalent.

The NFA B n = P n , Σ, ν n , p n-2 , {p 0 } with P n = {p 0 , p 1 , . . . , p n-2 } and ν n (p n-2 , a i ) = j∈mi p j , for 1 ≤ i ≤ k, and ν n (p i , a) = p j with i = (j + 1) mod (n -2), for 0 ≤ i ≤ n -3, accepts the language L(A n ) R . Notice that n -2 / ∈ m j for all 1 ≤ j ≤ k. By applying the powerset construction, the NFA B n is determinized which yields the DFA A n = S n , Σ, δ n , p n-2 , F n } , where S n = 2 Pn\{pn-2} ∪ {p n-2 }, The DFA A n accepts L(A) R and has 2 n-2 + 1 states. By the construction of A n and since the equivalence classes of colorings partition the set 2 Pn\{pn-2} , all states of A n are reachable.

F n = { T ∈ 2 Pn\{pn-2} | T ∩{p 0 } = ∅ }, δ n ({p n-2 }, a i ) = j∈mi p j , for 1 ≤ i ≤ k, δ n ({p n-2 }, a) = ∅,
In order to show that A n is minimal, first consider the states {p n-2 } and R i ∈ S n , for 0 ≤ i ≤ n -3. For p l ∈ R i we have δ n (R i , a l ) ∈ F n while δ n ({p n-2 }, a l ) / ∈ F n . Now let R i and R j be two different states from S n \ {p n-2 } and let p l be in their symmetric difference, say,

p l ∈ R i \ R j . Then δ n (R i , a l ) ∈ F n while δ n (R j , a l ) / ∈ F n . Therefore, A n is minimal.
Next, we turn to the operation iteration. Here, we will obtain tight upper and lower bounds that lie strictly in between the bounds for unary regular and arbitrary regular languages. Roughly speaking, the bounds for unary regular languages are quadratic and for arbitrary regular languages exponential. The bound for strongly bounded regular languages turns out to be the sum of a quadratic and an exponential function, where the quadratic function depends on the number of states of the first part of the given DFA and the exponential function depends on the number of remaining states. The partitioning of the state set of a DFA accepting a strongly bounded language L ⊆ a * 1 a * 2 • • • a * k into two sets is done, roughly speaking, as follows: the first set is given by all states that are reachable with words from a * 1 . Since the DFA is deterministic, these states form a line or a line followed by a cycle in the state graph.

More precisely, let A = S, Σ, δ, s 0 , F be a minimal DFA accepting a strongly bounded language L ⊆ a * 1 a * 2 • • • a * k and let e denote the rejecting sink state of A if it exists. In the sequel, the set of states q ∈ S with q = e such that there exists a word

v from a * 1 a * 2 • • • a * k \ a * 1 with δ(s 0 , v) = q is denoted by S 2 . The set S \ (S 2 ∪ {e}) is denoted by S 1 .
So, all states from S 1 are reachable only by words of the form a * 1 . For k ≥ 2, we have S = S 1 ∪ S 2 ∪ {e}. The next theorem shows the upper bound for the iteration.

Theorem 8. Let n 1 ≥ 2 and n 2 ≥ 1 be two integers and A be an (n 1 + n 2 + 1)state DFA with state set S that accepts a strongly bounded language, so that S = S 1 ∪ S 2 ∪ {e} with |S 1 | = n 1 and |S 2 | = n 2 . Then (n 1 -1) 2 + 2 n2 + 2 states are sufficient for a DFA to accept the language L(A) * .

In order to show a matching lower bound the coloring of cycles is exploited. Next, the construction of a (2n + 1)-state witness DFA is given. Let n ≥ 1 be an integer. The DFA B n = S, Σ, δ n , 0, {n -1, 2n -1} is constructed as follows (see Figure 5): S = {0, 1, . . . , 2n -1, e} where e denotes the rejecting sink state,

Σ = {a, b, a 1 , a 2 , . . . , a k } with k = 1 n d|n ϕ(d) • 2 n d -n -1, and δ n (i, a) = (i + 1) mod n for 0 ≤ i ≤ n -1 e otherwise , δ n (i, b) =      i + n for 0 ≤ i ≤ n -1 (i + 1) mod n for n ≤ i ≤ 2n -1 e otherwise .
In order to complete the definition of the transition function we consider colorings of the cycle on input letter b, that is, of the states {n, n + 1, . . . , 2n -1}, whereby we disregard gg

• • • g, wgg • • • g, wwgg • • • g, • • • , ww • • • wg, and ww • • • w. There remain k = 1 n d|n ϕ(d) • 2 n d
n -1 inequivalent colorings. From each equivalence class M j one element m j , 1 ≤ j ≤ k, is chosen and identified by the states that are colored white. The states in m j are denoted by r 0,j , r 1,j , . . . , r |mj |-1,j . The definition of the transition function is completed by setting So, δ n (0, a 1 ) = 4 and δ(1, a 1 ) = 6 are defined (see Figure 5).

δ n (i, a j ) = r i,j if 0 ≤ i ≤ n -1 and r i,j is defined e otherwise for 1 ≤ j ≤ k. The DFA B n accepts the language L(B n ) = (a n ) * a n-1 ∪ n-1 j=0 (a n ) * a j b n-j (b n ) * ∪ k j=1 |mj |-1 i=0 (a n ) * a i a j b 2n-1-ri,j (b n ) * , that is, L(B n ) ⊆ a * a * 1 a * 2 • • • a * k b * . 0 1 2
Theorem 10. For any integers n 1 = n 2 ≥ 1, there exists an (n 1 + n 2 + 1)state DFA A that accepts a (strongly) bounded language such that any DFA accepting L(A) * needs at least (n 1 -1) 2 + 2 n2 + 2 states.

The final operation we consider is the concatenation. Again, the structure of (strongly) boundedness allows to reduce the descriptional complexity compared with the general case. As for iteration we obtain that the upper bound is described by the sum of a quadratic and an exponential function, where the number of states of the first DFA appear as quadratic resp. linear factor in both addends. As is done for iteration, the states of the second DFA are partitioned into two parts and the number of states of the first part appear as linear factor in the quadratic addend and as exponential factor in the other addend. The proof of the next theorem gives a detailed construction of the upper bound for the concatenation of two strongly bounded regular languages.

Theorem 11. Let m, n 1 , n 2 ≥ 1 be integers, A be an m-state DFA, and A be an (n 1 + n 2 + 1)-state DFA with state set S that accept strongly bounded languages, so that S = S 1 ∪ S 2 ∪ {e } with |S 1 | = n 1 and |S 2 | = n 2 . Then in total m 2 n 1 + (2m -1)2 n2 states are sufficient for a DFA to accept the language L(A)L(A ).

The currently best known lower bound for the concatenation of strongly bounded languages is derived from the concatenation of unary languages. In [START_REF] Yu | The state complexities of some basic operations on regular languages[END_REF] it is shown that for any m, n ≥ 1 with gcd(m, n) = 1 there exist an m-state DFA A and an n-state DFA A accepting unary (and thus strongly bounded) languages so that any DFA that accepts the concatenation L(A)L(A ) has at least mn states. The results on the deterministic state complexity obtained in this section are summarized in Table 2.

unary regular bounded regular regular

L1 ∪ L2 ≤ mn ≤ mn mn L1 ∩ L2 ≥ mn, if gcd(m, n) = 1 ≥ mn, if gcd(m, n) = 1 L m m m L1L2 ≤ mn ≤ m 2 n1 + (2m -1)2 n 2 (2m -1)2 n-1 ≥ mn, if gcd(m, n) = 1 ≥ mn, if gcd(m, n) = 1 L * (m -1) 2 + 1 (m1 -1) 2 + 2 m 2 + 2 2 m-1 + 2 m-2 L R m ≤ 2 m-1 2 m ≥ 2 m-2 + 1
Table 2. Summary of the deterministic state complexity of the operations studied in this section. The upper and lower bounds for bounded regular languages are obtained in this section. The results for unary regular and arbitrary regular languages may be found, for example, in [START_REF] Gao | A survey on operational state complexity[END_REF][START_REF] Yu | The state complexities of some basic operations on regular languages[END_REF].

Conclusions

In this paper, we have studied the descriptional complexity of (strongly) bounded regular languages. We have described a procedure for determinizing nondeterministic finite automata accepting strongly bounded regular languages. The obtained upper bound on the number of states is close to the known upper bound for the determinization of unary nondeterministic finite automata. Moreover, we have determined the deterministic state complexity of several operations on strongly bounded regular languages, in particular, of the operations reversal, iteration, and concatenation. The resulting upper and lower bounds are basically strictly in between the known bounds for unary and arbitrary regular languages. As interesting points for further research on the topic we would like to mention the improvement of the lower bound on concatenation, the study of additional operations, and the investigation of the nondeterministic state complexity of operations. Another interesting question is to look more closely at the size of the alphabets of the witness languages for the lower bounds. In the proofs given in this paper, the size is depending on the given number of states. It would clearly be of interest to study fixed alphabets or to consider the size of the alphabet as an additional parameter for upper and lower bounds.

Theorem 1 .

 1 Let A be an NFA with n states accepting a strongly bounded regular language L(A) over the alphabet Σ and m = n • |Σ| 2 + |Σ|. Then an equivalent DFA A with at most |Σ| 2 • e |Σ|•Θ √ m•log(m) many states can be constructed.

Fig. 1 .

 1 Fig. 1. An NFA A accepting a strongly bounded regular language.

  the costs for determinizing A s are bounded by e Θ √ n1•log(n1) . Since n 1 is bounded by m = n • |Σ| 2 + |Σ|, we get an upper bound of 1 = e Θ √ m•log(m) many states. Next, we construct an NFA A based

2 .

 2 Then m•n states are sufficient for a DFA to accept the language L(A)∩L(B) (respectively L(A) ∪ L(B)). 3. If m ⊥ n, then there exist a unary m-state DFA A and a unary n-state DFA B (with the same input symbol) such that any DFA accepting L(A) ∩ L(B) (respectively L(A) ∪ L(B)) needs at least m • n states.

  {g, w} }. So, there are |X| = 2 |Sc| different such colorings. Example 3. The DFA A depicted in Figure 3 has a cycle on input letter b, where the states of the cycle are S c = {1, 2, 3, 4}. The coloring shown at the top of the figure is f 1 ∈ X with f 1 (1) = g, f 1 (2) = g, f 1 (3) = w, and f 1 (4) = w.

Fig. 3 .

 3 Fig. 3. Coloring of the cycle of DFA A from Example 3. Edges to the rejecting sink state are omitted.

  and δ n (T, a) = t∈T ν(t, a), for T ∈ 2 Pn\{pn-2} .

Fig. 5 .Example 9 .

 59 Fig. 5. The witness DFA B4 for iteration. Edges to the rejecting sink state are omitted.

Table 1 .

 1 Summary of closure properties of the language families discussed.

		∪	∩	R	•	*
	Bounded Regular	no yes yes yes yes no
	Strongly Bounded Regular no no yes yes no no


Janusz Brzozowski

David R Cheriton

Unrestricted State Complexity of Binary Operations on Regular Languages ⋆

Keywords: boolean operation, concatenation, different alphabets, most complex languages, product, quotient complexity, regular language, state complexity, stream, unrestricted complexity 1 Motivation

I study the state complexity of binary operations on regular languages over different alphabets. It is well known that if L ′ m and Ln are languages restricted to be over the same alphabet, with m and n quotients, respectively, the state complexity of any binary boolean operation on L ′ m and Ln is mn, and that of the product (concatenation) is (m -1)2 n + 2 n-1 . In contrast to this, I show that if L ′ m and Ln are over their own different alphabets, the state complexity of union and symmetric difference is mn + m + n + 1, that of intersection is mn + 1, that of difference is mn + m + 1, and that of the product is m2 n + 2 n-1 .

2. ... m • n states are ... sufficient for a DFA to accept the intersection (union) of an m-state DFA language and an n-state DFA language.

Here DFA stands for deterministic finite automaton, and complete means that there is a transition from every state under every input letter.

I will show that statements 1 and 2 of Maslov are incorrect without the restriction that the languages are over the same alphabet. In [START_REF] Yu | The state complexities of some basic operations on regular languages[END_REF] the first statement includes that restriction, but the second omits it (presumably it's implied).

The same-alphabet restriction is unnecessary: There is no reason why we should not be able to find, for example, the union of languages L ′ = {a, b} * b and L = {a, c} * c accepted by the minimal complete two-state automata D ′ 2 and D 2 of Figure 1, where an incoming arrow denotes the initial state and a double circle represents a final state. The union of L ′ and L is a language over three letters. To find the DFA for L ′ ∪ L, we view D ′ 2 and D 2 as incomplete DFA's, the first missing all transitions under c, and the second under b. After adding the missing transitions we obtain DFAs D ′ 3 and D 3 . Now we can proceed as is usually done in the same-alphabet approach, and take the direct product of D ′ 3 and D 3 to find L ′ ∪ L. Here it turns out that six states are necessary to represent L ′ ∪ L, but the state complexity of union is actually (m + 1)(n + 1). In general, when calculating the result of a binary operation on regular languages with different alphabets, we deal with special incomplete DFAs that are only missing some letters and all the transitions caused by these letters. The complexity of incomplete DFAs has been studied previously by Gao, K. Salomaa, and Yu [START_REF] Gao | Transition complexity of incomplete DFAs[END_REF] and by Maia, Moreira and Reis [START_REF] Maia | Incomplete operational transition complexity of regular languages[END_REF]. However, the objects studied there are arbitrary incomplete DFAs, whereas we are interested only in complete DFAs with some missing letters. Secondly, we study state complexity, whereas the above-mentioned papers deal mainly with transition complexity. Nevertheless, there is some overlap. It was shown in [START_REF] Gao | Transition complexity of incomplete DFAs[END_REF]Corollary 3.2] that the incomplete state complexity of union is less than or equal to mn + m + n, and that this bound is tight in some special cases. In [START_REF] Maia | Incomplete operational transition complexity of regular languages[END_REF]Theorem 2], witnesses that work in all cases were found. These complexities correspond to my result for union in Theorem 1. Also in [START_REF] Maia | Incomplete operational transition complexity of regular languages[END_REF]Theorem 5], the incomplete state complexity of product is shown to be m2 n + 2 n-1 -1, and this corresponds to my result for product in Theorem 2.

0 ′ 1 ′ 2 ′
In this paper I remove the restriction of equal alphabets of the two operands. I prove that the complexity of union and symmetric difference is mn + m + n + 1, that of intersection is mn + 1, that of difference is mn + m -1, and that of the product is m2 n + 2 n-1 , if each language's own alphabet is used. I exhibit a new most complex regular language that meets the complexity bounds for boolean operations, product, star, and reversal, has a maximal syntactic semigroup and most complex atoms. All the witnesses used here are derived from that one most complex language.

Terminology and Notation

A basic complexity measure of a regular language L over an alphabet Σ is the number n of distinct (left) quotients of L, where a (left) quotient of L by a word w ∈ Σ * is w -1 L = {x | wx ∈ L}. The number of quotients of L is its quotient complexity [START_REF] Brzozowski | Quotient complexity of regular languages[END_REF], κ(L). A concept equivalent to quotient complexity is the state complexity [START_REF] Yu | The state complexities of some basic operations on regular languages[END_REF] of L, which is the number of states in a complete minimal deterministic finite automaton (DFA) recognizing L. Since we do not use any other measures of complexity in this paper (with the exception of one mention of time and space complexity in the next paragraph), we refer to quotient/state complexity simply as complexity.

Let L ′ m ⊆ Σ ′ * and L n ⊆ Σ * be regular languages of complexities m and n, respectively. The complexity of a binary operation

• on L ′ m and L n is the maximal value of κ(L ′ m • L n ) as a function f (m, n), as L ′
m and L n range over all regular languages of complexity m and n, respectively. The complexity of an operation gives a worst-case lower bound on the time and space complexity of the operation. For this reason it has been studied extensively; see [START_REF] Brzozowski | Quotient complexity of regular languages[END_REF][START_REF] Brzozowski | In search of the most complex regular languages[END_REF][START_REF] Yu | State complexity of regular languages[END_REF][START_REF] Yu | The state complexities of some basic operations on regular languages[END_REF] for additional references.

A deterministic finite automaton (DFA) is a quintuple D = (Q, Σ, δ, q 0 , F ), where Q is a finite non-empty set of states, Σ is a finite non-empty alphabet, δ : Q × Σ → Q is the transition function, q 0 ∈ Q is the initial state, and F ⊆ Q is the set of final states. We extend δ to a function δ : Q × Σ * → Q as usual. A DFA D accepts a word w ∈ Σ * if δ(q 0 , w) ∈ F . The language accepted by D is denoted by L(D). If q is a state of D, then the language L q of q is the language accepted by the DFA (Q, Σ, δ, q, F ). A state is empty (or dead or a sink state) if its language is empty. Two states p and q of D are equivalent if L p = L q . A state q is reachable if there exists w ∈ Σ * such that δ(q 0 , w) = q. A DFA is minimal if all of its states are reachable and no two states are equivalent. Usually DFAs are used to establish upper bounds on the complexity of operations, and also as witnesses that meet these bounds.

If δ(q, a) = p for a state q ∈ Q and a letter a ∈ Σ, we say there is a transition under a from q to p in D. The DFAs defined above are complete in the sense that there is exactly one transition for each state q ∈ Q and each letter a ∈ Σ. If there is at most one transition for each state of Q and letter of Σ, the automaton is an incomplete DFA.

A nondeterministic finite automaton (NFA) is a 5-tuple D = (Q, Σ, δ, I, F ), where Q, Σ and F are defined as in a DFA, δ : Q × Σ → 2 Q is the transition function, and I ⊆ Q is the set of initial states. An ε-NFA is an NFA in which transitions under the empty word ε are also permitted.

To simplify the notation, without loss of generality we use Q n = {0, . . . , n-1} as the set of states of every DFA with n states. A transformation of Q n is a mapping t : Q n → Q n . The image of q ∈ Q n under t is denoted by qt. For k 2, a transformation (permutation) t of a set P = {q 0 , q 1 , . . . , q k-1 } ⊆ Q is a k-cycle if q 0 t = q 1 , q 1 t = q 2 , . . . , q k-2 t = q k-1 , q k-1 t = q 0 . This k-cycle is denoted by (q 0 , q 1 , . . . , q k-1 ), and acts as the identity on the states in Q n \ P . A 2-cycle (q 0 , q 1 ) is called a transposition. A transformation that changes only one state p to a state q = p and acts as the identity for the other states is denoted by (p → q). The identity transformation is denoted by 1.

In any DFA, each a ∈ Σ induces a transformation δ a of the set Q n defined by qδ a = δ(q, a); we denote this by a : δ a . For example, when defining the transition function of a DFA, we write a : (0, 1) to mean that δ(q, a) = q(0, 1), where the transformation (0, 1) acts on state q as follows: if q is 0 it maps it to 1, if q is 1 it maps it to 0, and it acts as the identity on the remaining states.

By a slight abuse of notation we use the letter a to denote the transformation it induces; thus we write qa instead of qδ a . We extend the notation to sets of states: if P ⊆ Q n , then P a = {pa | p ∈ P }. We also find it convenient to write P a -→ P a to indicate that the image of P under a is P a. If s, t are transformations of Q, their composition is denoted by s * t and defined by q(s * t) = (qs)t; the * is usually omitted. Let T Qn be the set of all n n transformations of

Q n ; then T Qn is a monoid under composition. A sequence (L n , n k) = (L k , L k+1 , . . . )
, of regular languages is called a stream; here k is usually some small integer, and the languages in the stream usually have the same form and differ only in the parameter n. For example, ({a, b} * a n {a, b} * | n

2) is a stream. To find the complexity of a binary operation • we need to find an upper bound on this complexity and two streams (L ′ m , m h) and (L n , n k) of languages meeting this bound. In general, the two streams are different, but there are many examples where L ′ n "differs only slightly" from L n ; such a language

L ′ n is called a dialect [3] of L n .
Let Σ = {a 1 , . . . , a k } be an alphabet; we assume that its elements are ordered as shown. Let π be a partial permutation of Σ, that is, a partial function π : Σ → Γ where Γ ⊆ Σ, for which there exists ∆ ⊆ Σ such that π is bijective when restricted to ∆ and undefined on Σ \ ∆. We denote undefined values of π by "-", that is, we write π(a) = -, if π is undefined at a.

If L ⊆ Σ * , we denote it by L(a 1 , . . . , a k ) to stress its dependence on Σ. If π is a partial permutation, let s π (L(a 1 , . . . , a k )) be the language obtained from L(a 1 , . . . , a k ) by the substitution s π defined as follows: for a ∈ Σ, a → {π(a)} if π(a) is defined, and a → ∅ otherwise. The permutational dialect, or simply dialect, of L(a 1 , . . . , a k ) defined by π is the language L(π(a 1 ), . . . , π(a k )) = s π (L(a 1 , . . . , a k )).

Similarly, let D = (Q, Σ, δ, q 0 , F ) be a DFA; we denote it by D(a 1 , . . . , a k ) to stress its dependence on Σ. If π is a partial permutation, then the permutational dialect, or simply dialect, D(π(a 1 ), . . . , π(a k )) of D(a 1 , . . . , a k ) is obtained by changing the alphabet of D from Σ to π(Σ), and modifying δ so that in the modified DFA π(a i ) induces the transformation induced by a i in the original DFA. One verifies that if the language L(a 1 , . . . , a k ) is accepted by DFA D(a 1 , . . . , a k ), then L(π(a 1 ), . . . , π(a k )) is accepted by D(π(a 1 ), . . . , π(a k )).

If the letters for which π is undefined are at the end of the alphabet Σ, then they are omitted. For example, if Σ = {a, b, c, d} and π(a) = b, π(b) = a, and π(c) = π(d) = -, then we write L n (b, a) for L n (b, a, -, -), etc.

Boolean Operations

A binary boolean operation is proper if it is not a constant and does not depend on only one variable. We study the complexities of four proper boolean operations only: union (∪), symmetric difference (⊕), difference (\), and intersection (∩); the complexity of any other proper operation can be deduced from these four. For example, κ(L

′ ∪ L) = κ L ′ ∪ L = κ(L ′ ∩ L) = κ(L ′ \ L)
, where we have used the well-known fact that κ(L) = κ(L), for any L.

The DFA of Definition 1 is required for the next theorem; this DFA is the 4-input "universal witness" called U n (a, b, c, d) in [START_REF] Brzozowski | In search of the most complex regular languages[END_REF].

Definition 1. For n 3, let D n = D n (a, b, c, d) = (Q n , Σ, δ n , 0, {n -1})
, where Σ = {a, b, c, d}, and δ n is defined by the transformations a : (0, . . . , n -1), b : (0, 1), c : (n-1 → 0), and d : b,c,d) be the language accepted by D n . The structure of D n (a, b, c, d) is shown in Figure 3.

1. Let L n = L n (a,
Theorem 1. For m, n 3, let L ′ m (respectively, L n ) be a regular language with m (respectively, n) quotients over an alphabet Σ ′ , (respectively, Σ). Then Proof.

κ(L ′ m ∪ L n ) = κ(L ′ m ⊕ L n ) = mn + m + n + 1, κ(L ′ m \ L n ) = mn + m + 1, κ(L ′ m ∩ L n ) = mn + 1.
Let D ′ m = (Q ′ m , Σ ′ , δ ′ , 0 ′ , F ′ ) and D n = (Q n , Σ, δ, 0, F ) be minimal DFAs for L ′
m and L n , respectively. To calculate an upper bound for the boolean operations assume that Σ ′ \ Σ and Σ \ Σ ′ are non-empty. We add an empty state to D ′ m to send all transitions under the letters from Σ \ Σ ′ to that state; thus we get an (m + 1)-state DFA D ′ m,∅ . Similarly, we add an empty state to D n to get D n,∅ . Now we have two DFAs over the same alphabet, and an ordinary problem of finding an upper bound for the boolean operations on two languages over the same alphabet, except that these languages both contain empty quotients. It is clear that (m + 1)(n + 1) is an upper bound for all four operations; however, this bound can be improved for difference and intersection. Consider the direct product P m,n of D ′ m,∅ and D n,∅ . For difference, all n + 1 states of P m,n that have the form (∅, q), where q ∈ Q n are empty. Hence the bound can be reduced by n states to mn + m + 1. For intersection, all n states (∅, q), q ∈ Q n , and all m states (p ′ , ∅), p ′ ∈ Q ′ m , are equivalent to the empty state (∅, ∅), thus reducing the upper bound to mn + 1.

To prove that the bounds are tight, we start with To finish the proof, we complete the two DFAs by adding empty states, and construct their direct product as illustrated in Figure 5. If we restrict both DFAs to the alphabet {a, b}, we have the usual problem of determining the complexity of two DFAs over the same alphabet. By [1, Theorem 1], all mn states of the form {p ′ , q}, p ′ ∈ Q ′ m , q ∈ Q n , are reachable and pairwise distinguishable by words in {a, b} * for all proper boolean operations if (m, n) / ∈ {(3, 4), (4, 3), (4, 4)}. For our application, the three exceptional cases were verified by computation.

To prove that the remaining states are reachable, observe that (0 ′ , 0)

d -→ (∅ ′ , 0) and (∅ ′ , 0) b q -→ (∅ ′ , q), for q ∈ Q n . Symmetrically, (0 ′ , 0) c -→ (0 ′ , ∅) and (0 ′ , ∅) a p -→ (p ′ , ∅), for p ′ ∈ Q ′ m . Finally, (∅ ′ , n-1) c -→ (∅ ′ , ∅)
, and all (m+1)(n+1) states of the direct product are reachable. It remains to verify that the appropriate states are pairwise distinguishable. From [1, Theorem 1], we know that all states in

0 ′ 1 ′ 2 ′ . . . (m -1) ′ a,
0 ′ , 0 1 ′ , 0 2 ′ , 0 ∅ ′ , 0 0 ′ , 1 1 ′ , 1 2 ′ , 1 ∅ ′ , 1 0 ′ , 2 1 ′ , 2 2 ′ , 2 ∅ ′ , 2 0 ′ , 3 1 ′ , 3 2 ′ , 3 ∅ ′ , 3 0 ′ , ∅ 1 ′ , ∅ 2
Q ′ m × Q n are distinguishable. Let H = {(∅ ′ , q) | q ∈ Q n }, and V = {(p ′ , ∅) | p ′ ∈ Q ′ m }.
For the operations consider four cases:

Union The final states of P m,n are {((m-1) ′ , q) | q ∈ Q n ∪{∅}}, and {(p ′ , n-1) | p ′ ∈ Q ′ m ∪ {∅ ′ }}.
Every state in V accepts a word with a c, whereas no state in H accepts such words. Similarly, every state in H accepts a word with a d, whereas no state in V accepts such words. Every state in Q ′ m × Q n accepts a word with a c and a word with a d. State (∅ ′ , ∅) accepts no words at all. Hence any two states chosen from different sets (the sets being Q ′ m × Q n , H, V , and {(∅ ′ , ∅)}) are distinguishable. States in H are distinguishable by words in b * and those in V , by words in a * . Therefore all mn + m + n + 1 states are pairwise distinguishable. Symmetric Difference The final states here are all the final states for union except ((m -1) ′ , n -1). The rest of the argument is the same as for union. Difference The final states now are {((m -1) ′ , q) | q = n -1}. The n states of the form (∅ ′ , q), q ∈ Q n , are now equivalent to the empty state {(∅ ′ , ∅)}.

The remaining states are pairwise distinguishable by the arguments used for union. Hence we have mn + m + 1 distinguishable states. Intersection Here only ((m -1) ′ , n -1) is final and all states (p ′ , ∅), p ′ ∈ Q ′ m , and (∅ ′ , q), q ∈ Q n are equivalent to {(∅ ′ , ∅)}, leaving mn + 1 distinguishable states.

⊓ ⊔ Remark 1 (Marek Szykuła, personal communication). In the case of intersection the alphabet of one of the witnesses can be binary: L ′ m (a, b, -, c) and L n (b, a) meet the bound mn + 1. Reachability and distinguishability of all mn states of the form {p ′ , q}, p ′ ∈ Q ′ m , q ∈ Q n , is the same as above. State (p ′ , ∅) can be reached from (p ′ , 0) by c, and is equivalent to the empty state, thus giving mn+1 states in the intersection.

Product

Theorem 2. For m, n 3, let L ′ m (respectively, L n ) be a regular language with m (respectively, n) quotients over an alphabet Σ ′ , (respectively, Σ). Then

κ(L ′ m L n ) = m2 n + 2 n-1 .
Proof. First we derive the upper bound. Let D ′ m = (Q ′ m , Σ ′ , δ ′ , 0 ′ , F ′ ) and D n = (Q n , Σ, δ, 0, F ) be minimal DFAs of L ′ m and L n , respectively. We use the normal construction of an ε-NFA N to recognize L ′ m L n , by introducing an ε-transition from each final state of D ′ m to the initial state of D n , and changing all final states of D ′ m to non-final. This is illustrated in Figure 6, where (m -1) ′ is the only final state of D ′ m . We then determinize N using the subset construction to get the DFA D for L ′ m L n . Suppose D ′ m has k final states, where 1 k m -1. I will show that D can have only the following types of states: (a) at most

(m -k)2 n states {p ′ } ∪ S, where p ′ ∈ Q ′ m \ F ′ , and S ⊆ Q n , (b) at most k2 n-1 states {p ′ , 0} ∪ S, where p ′ ∈ F ′ and S ⊆ Q n \ {0}, and (c) at most 2 n states S ⊆ Q n . Because D ′
m is deterministic, there can be at most one state p ′ of Q ′ m in any reachable subset. If p ′ / ∈ F ′ , it may be possible to reach any subset of states of Q n along with p ′ , and this accounts for (a). If p ′ ∈ F ′ , then the set must contain 0 and possibly any subset of Q n \ {0}, giving (b). It may also be possible to have any subset S of Q n by applying an input that is not in Σ ′ to {0 ′ } ∪ S to get S, and so we have (c). Altogether, there are at most (mk)2 n + k2 n-1 + 2 n = (2mk)2 n-1 + 2 n reachable subsets. This expression reaches its maximum when k = 1, and hence we have at most m2 n + 2 n-1 states in D. To prove that the bound is tight, we use the same witnesses as for boolean operations; see Figure 6. If S = {q 1 , . . . , q k } ⊆ Q n then S +i = {q 1 +i, . . . , q k +i} and Si = {q 1i, . . . , q k -i}, where addition and subtraction are modulo n. Note that b 2 and a m (a 2 and b n ) act as the identity on

0 ′ 1 ′ 2 ′ . . . (m -1) ′ a,
Q ′ m (Q n ). If p < m -1, then {p ′ }∪S b 2 -→ {p ′ }∪(S+2), for all S ⊆ Q n . If n is odd, then (b 2 ) (n-1)/2 = b n-1 and {p ′ } ∪ S b n-1 -→ {p ′ } ∪ (S -1), for all q ∈ Q n . If 0, 1 /
∈ S or {0, 1} ⊆ S, then a acts as the identity on S.

Remark 2. If 1 / ∈ S and {(m -2) ′ } ∪ S is reachable, then {0 ′ , 1} ∪ S is reachable for all S ⊆ Q n \ {1}. Proof. If 0 ∈ S, then {(m -2) ′ , 0} ∪ S \ {0} a -→ {(m -1) ′ , 0, 1} ∪ S \ {0} a -→ {0 ′ , 0, 1} ∪ S \ {0} = {0 ′ , 1} ∪ S. If 0 / ∈ S, then {(m -2) ′ } ∪ S a -→ {(m -1) ′ , 0} ∪ S a -→ {0 ′ , 1} ∪ S. ⊓ ⊔
We now prove that the languages of Figure 6 meet the upper bound.

Claim 1: All sets of the form {p ′ } ∪ S, where p ′ ∈ Q ′ m-1 and S ⊆ Q n , are reachable. We show this by induction on the size of S.

Basis: |S| = 0. The initial set is {0 ′ }, and from {0 ′ } we reach {p ′ }, p ′ ∈ Q ′ m-1
, by a p , without reaching any states of Q n . Thus the claim holds if |S| = 0.

Induction Assumption: {p ′ } ∪ S, where p ′ ∈ Q ′ m-1 and S ⊆ Q n , is reachable if |S| k. Induction Step: We prove that if |S| = k + 1, then {p ′ } ∪ S is reachable. Let S = {q 0 , q 1 , . . . , q k }, where 0 q 0 < q 1 < • • • < q k n -1. Suppose q ∈ S. By assumption, sets {p ′ } ∪ (S \ {q} -(q -1)) are reachable for all p ′ ∈ Q ′ m-1 . • All sets of the form {0 ′ } ∪ S are reachable. Note that 1 / ∈ (S \ {q} -(q -1)). By assumption, {(m -2) ′ } ∪ (S \ {q} -(q -1)) is reachable. By Remark 2, {0 ′ , 1} ∪ (S \ {q} -(q -1)) is reachable. 1. If there is an odd state q in S, then {0 ′ , 1} ∪ (S \ {q} -(q -1)) b q-1 -→ {0 ′ , q} ∪ (S \ {q}) = {0 ′ } ∪ S.
2. If there is no odd state in S and n is odd, then S ⊆ {0, 2, . . . , n -1}. Pick

q ∈ S. Then {0 ′ , 1} ∪ (S \ {q} -(q -1)) b q -→ {0 ′ , q + 1} ∪ (S \ {q} + 1) b n-1 ---→ {0 ′ , q} ∪ S \ {q} = {0 ′ } ∪ S.
3. If there is no odd state and n is even, then S ⊆ {0, 2, . . . , n-2} (so n-1 / ∈ S).

-→ {0 ′ , n -1, 0} ∪ (S \ {0, 2} -1) ab -→ {0 ′ , 0, 2} ∪ (S \ {0, 2}) = {0 ′ } ∪ S.
• All sets of the form {1 ′ } ∪ S are reachable.

If 0 and 1 are not in S or are both in S, then

{0 ′ } ∪ S a -→ {1 ′ } ∪ S. If 0 ∈ S but 1 / ∈ S, then {0 ′ , 1} ∪ S \ {0} a -→ {1 ′ , 0} ∪ S \ {0} = {1 ′ } ∪ S. If 1 ∈ S but 0 / ∈ S, then {0 ′ , 0} ∪ S \ {1} a -→ {1 ′ , 1} ∪ S \ {1} = {1 ′ } ∪ S.
• All sets of the form {p ′ } ∪ S, where 2 p m -2, are reachable.

If p is even, then {0 ′ } ∪ S a p -→ {p ′ } ∪ S. If p is odd, then {1 ′ } ∪ S a p-1 -→ {p ′ } ∪ S.
Claim 2: All sets of the form {(m -1) ′ , 0} ∪ S are reachable.

1. By Claim 1, {(m -3) ′ } ∪ S is reachable. If q 0 = 1, then {(m -3) ′ , 1} ∪ S \ {1} a 2 -→ {(m -1) ′ , 0, 1} ∪ S \ {1} = {(m -1) ′ , 0} ∪ S. 2. By Claim 1, {(m -2) ′ } ∪ S is reachable. If q 0 2, then {(m -2) ′ } ∪ S a -→ {(m -1) ′ , 0} ∪ S.
Claim 3: All sets of the form S are reachable. By Claim 1, {0 ′ } ∪ S is reachable for every S, and

{0 ′ } ∪ S d -→ S.
For distinguishability, note that only state q accepts w q = b n-1-q in D n . Hence, if two states of the product have different sets S and S ′ and q ∈ S ⊕ S ′ , then they can be distinguished by w q . State {p ′ } ∪ S is distinguished from S by ca m-1-p b n-1 . If p < q, states {p ′ } ∪ S and {q ′ } ∪ S are distinguished as follows. Use ca m-1-q to reach {(p+m-1-q) ′ } from p ′ and {(m-1) ′ }∪{0} from q ′ . The reached states are distinguishable since they differ in their subsets of Q n .

⊓ ⊔

Most Complex Regular Languages

A most complex regular language stream is one that, together with some dialects, meets the complexity bounds for all boolean operations, product, star, and reversal, and has the largest syntactic semigroup and most complex atoms [START_REF] Brzozowski | In search of the most complex regular languages[END_REF]. A most complex stream should have the smallest possible alphabet sufficient to meet all the bounds. Most complex streams are useful in systems dealing with regular languages and finite automata. One would like to know the maximal sizes of automata that can be handled by the system. In view of the existence of most complex streams, one stream can be used to test all the operations. Here we present a stream similar to that of [START_REF] Brzozowski | In search of the most complex regular languages[END_REF] but with one added input letter that induces the identity transformation, as shown in Figure 3.

κ(A S ) = 2 n -1, if S ∈ {∅, Q n }; 1 + |S| x=1 n-|S| y=1 n x n-x y , if ∅ S Q n .
5. The star of L n (a, b) has complexity 2 n-1 + 2 n-2 . 6. The product L ′ m (a, b, -, c)L n (b, a, -, d) has complexity m2 n + 2 n-1 .

The complexity of L

′ m (a, b, -, c)•L n (b, a, -, d) is mn+m+n+1 if • ∈ {∪, ⊕}, mn + m + 1 if • = \, and mn + 1 if • = ∩.
Proof. The proofs of 1-5 can be found in [START_REF] Brzozowski | In search of the most complex regular languages[END_REF], and Claims 6 and 7 are proved in the present paper, Theorems 1 and 2.

⊓ ⊔ Proposition 1 (Marek Szykuła, personal communication). At least four inputs are required for a most complex regular language. In particular, four inputs are needed for union: two inputs are needed to reach all pairs of states in Q ′ m × Q n , one input in Σ ′ \ Σ for pairs (p ′ , ∅) with p ′ ∈ Q ′ m , and one in Σ \ Σ ′ for pairs (∅ ′ , q) with q ∈ Q n . 1 The atom congruence is a left congruence defined as follows: two words x and y are equivalent if ux ∈ L if and only if uy ∈ L for all u ∈ Σ * . Thus x and y are equivalent if x ∈ u -1 L if and only if y ∈ u -1 L. An equivalence class of this relation is called an atom of L [START_REF] Brzozowski | Theory of átomata[END_REF][START_REF] Iván | Complexity of atoms, combinatorially[END_REF]. It follows that an atom is a non-empty intersection of complemented and uncomplemented quotients of L. The number of atoms and their quotient complexities are possible measures of complexity of regular languages [START_REF] Brzozowski | In search of the most complex regular languages[END_REF].

For more information about atoms and their complexity, see [START_REF] Brzozowski | Complexity of atoms of regular languages[END_REF][START_REF] Brzozowski | Theory of átomata[END_REF][START_REF] Iván | Complexity of atoms, combinatorially[END_REF].

Conclusions

Two complete DFAs over different alphabets Σ ′ and Σ are incomplete DFAs over Σ ′ ∪ Σ. Each DFA can be completed by adding an empty state and sending all transitions induced by letters not in the DFA's alphabet to that state. This results in an (m + 1)-state DFA and an (n + 1)-state DFA. From the theory about DFAs over the same alphabet we know that (m + 1)(n + 1) is an upper bound for all boolean operations on the original DFAs, and that m2 n+1 + 2 n is an upper bound for product. We have shown that the tight bounds for boolean operations are (m + 1)(n + 1) for union and symmetric difference, mn + m + 1 for difference, and mn + 1 for intersection, while the tight bound for product is m2 n + 2 n-1 . In the same-alphabet case the tight bound is mn for all boolean operations and it is (m -1)2 n + 2 n-1 for product. In summary, the restriction of identical alphabets is unnecessary and leads to incorrect results.

It should be noted that if the two languages in question already have empty quotients, then making the alphabets the same does not require the addition of any states, and the traditional same-alphabet methods are correct. This is the case, for example, for prefix-free, suffix-free and finite languages.

Fig. 1 .

 1 Fig. 1. Two minimal complete DFAs D ′ 2 and D2.

Fig. 2 .

 2 Fig. 2. DFAs D ′ 3 and D3 over three letters.

Fig. 3 .

 3 Fig. 3. DFA of Definition 1.

  D n (a, b, c, d) of Definition 1. For m, n 3, let D ′ m (a, b, -, c) be the dialect of D ′ m (a, b, c, d) where c plays the role of d and the alphabet is restricted to {a, b, c}, and let D n (b, a, -, d) be the dialect of D n (a, b, c, d) in which a and b are permuted, and the alphabet is restricted to {a, b, d}; see Figure 4.

Fig. 4 .

 4 Fig. 4. Witnesses D ′ m (a, b, -, c) and Dn(b, a, -, d) for boolean operations.

Fig. 5 .

 5 Fig. 5. Direct product for union shown partially.

Fig. 6 .

 6 Fig. 6. An NFA for the product of L ′ m (a, b, -, c) and Ln(b, a, -, d).

( a )

 a If 0 / ∈ S, then 0, 1 / ∈ S + 1. By 1, {0 ′ } ∪ (S + 1) is reachable, since S + 1 contains an odd state. Then {0 ′ }∪(S +1)a -→ {1 ′ }∪(S +1) b n-1 -→ {0 ′ }∪S. (b) If 2 / ∈ S, then 0, 1 / ∈ S -1. By 1, {0 ′ } ∪ (S -1) is reachable, since S -1 contains an odd state. Then {0 ′ }∪(S -1) a -→ {1 ′ }∪(S -1) b n+1 -→ {0 ′ }∪S. (c) If {0, 2} ⊆ S, then 0 / ∈ S -1, and 1, n -1 ∈ S -1. By 1, {0 ′ } ∪ (S -1) is reachable, since 1 ∈ S -1.Note that aba sends 1 to 0, n -1 to 1, and adds 1 to each state q 3 of S -1; thus 2 / ∈ (S -1)aba, and {0 ′ } ∪ (S -1) aba -→ {1 ′ , 0, 1} ∪ S \ {0, 2}. Next, b n-1 sends 0 to n -1 and subtracts 1 from every other element of S \ {0, 2}. Hence {1 ′ , 0, 1} ∪ S \ {0, 2} b n-1

Theorem 3 (

 3 Most Complex Regular Languages). For each n 3, the DFA of Definition 1 is minimal and its language L n (a, b, c, d) has complexity n. The stream (L m (a, b, c, d) | m 3) with dialect streams (L n (a, b, -, c) | n 3) and (L n (b, a, -, d) | n 3) is most complex in the class of regular languages. In particular, it meets all the complexity bounds below, which are maximal for regular languages. In several cases the bounds can be met with a restricted alphabet. 1. The syntactic semigroup of L n (a, b, c) has cardinality n n . 2. Each quotient of L n (a) has complexity n. 3. The reverse of L n (a, b, c) has complexity 2 n , and L n (a, b, c) has 2 n atoms 1 . 4. For each atom A S of L n (a, b, c), the complexity κ(A S ) satisfies:

Acknowledgment I am very grateful to Sylvie Davies, Bo Yang Victor Liu and Corwin Sinnamon for careful proofreading and constructive comments. I thank Marek Szykuła for contributing the important Remark 1 and Proposition 1.

states which accepts L(A⋆ This work was supported by the Natural Sciences and Engineering Research Council of Canada grant No. OGP0000871.


Rafaela Bastos

Sabine Broda

António Machiavelo

Nelma Moreira

Rogério Reis

On the State Complexity of Partial Derivative Automata for Regular Expressions with Intersection

Extended regular expressions (with complement and intersection) are used in many applications due to their succinctness. In particular, regular expressions extended with intersection only (also called semi-extended) can already be exponentially smaller than standard regular expressions or equivalent nondeterministic finite automata (NFA). For practical purposes it is important to study the average behaviour of conversions between these models. In this paper, we focus on the conversion of regular expressions with intersection to nondeterministic finite automata, using partial derivatives and the notion of support. First, we give a tight upper bound of 2 O(n) for the worst-case number of states of the resulting partial derivative automaton, where n is the size of the expression. Using the framework of analytic combinatorics, we then establish an upper bound of (1.056+o(1)) n for its asymptotic average-state complexity, which is significantly smaller than the one for the worst case.

Introduction

Regular expressions with additional operators are used in applications such as programming languages [START_REF] Christiansen | Programming Perl[END_REF], XML processing [START_REF] Van Der Vlist | RELAX NG[END_REF], or runtime verification [START_REF] Sen | Generating optimal monitors for extended regular expressions[END_REF]. Most of these operators do not increase their language expressive power but lead to gains in the succinctness of the representation. This is the case for intersection. For regular expressions with intersection (RE ∩ ) (or semi-extended), several computational complexity decision problems, such as membership, equivalence and emptiness, were studied by various authors. Petersen [START_REF] Petersen | The membership problem for regular expressions with intersection is complete in logcfl[END_REF] has shown that the membership problem is LOGCFL-complete, while for standard regular expressions (RE) it is NL-complete [START_REF] Jiang | A note on the space complexity of some decision problems for finite automata[END_REF]. Fürer [START_REF] Fürer | The complexity of the inequivalence problem for regular expressions with intersection[END_REF] has proved that inequivalence and non-empty complement are EXPSPACE-complete, which contrasts with the PSPACE-completeness of these problems for RE. The complexity of the conversions from regular expressions with intersection to standard regular expressions, and to finite automata, were recently studied by Gelade and Neven [START_REF] Gelade | Succinctness of the complement and intersection of regular expressions[END_REF], Gruber and Holzer [START_REF] Gruber | Finite automata, digraph connectivity, and regular expression size[END_REF], and Gelade [START_REF] Gelade | Succinctness of regular expressions with interleaving, intersection and counting[END_REF]. The conversion from RE ∩ to RE or to nondeterministic finite automata (NFA) is exponential and it is double exponential to deterministic finite automata (DFA). The conversion from α ∈ RE ∩ to a DFA can be accomplished using Brzozowski's derivatives [START_REF] Brzozowski | Derivatives of regular expressions[END_REF]. From RE to NFA a standard algorithm is the partial derivative automaton construction (A pd ) introduced by Antimirov [START_REF] Antimirov | Partial derivatives of regular expressions and finite automaton constructions[END_REF], which coincides with the resolution of systems of equations by Mirkin [START_REF] Mirkin | An algorithm for constructing a base in a language of regular expressions[END_REF]. The average complexity of these conversions was recently studied using the framework of analytic combinatorics [START_REF] Broda | On the average state complexity of partial derivative automata[END_REF][START_REF] Broda | On the average size of Glushkov and partial derivative automata[END_REF], and also their extension to regular expressions with shuffle [START_REF] Broda | Partial derivative automaton for regular expressions with shuffle[END_REF]. For these studies, Mirkin's construction is essential as it provides inductive definitions that can be used to obtain generating functions.

Caron et al. [START_REF] Caron | Partial derivatives of an extended regular expression[END_REF] extended the A pd to regular expressions with both intersection and complement (extended regular expressions) 1 . In their approach a partial derivative is a set of sets of expressions (akin a disjunctive normal form), whereas here it is simply a set of expressions. In the worst-case, their approach also leads to NFAs that can be exponentially larger than the original expressions. Moreover, considering sets of sets of expressions would turn the analytic combinatoric analysis much harder.

In this paper we show that for RE ∩ , Mirkin's construction can lead to automata not initially connected and thus larger than the ones built by Antimirov's construction. However, the two constructions can produce identical NFAs. We present an exponential worst-case upper bound which is tight for both. Using the framework of analytic combinatorics, we give an upper bound for the asymptotic average-state complexity for the Mirkin's construction, which turns out to be much smaller than the worst-case bound. This also means that Antimirov's construction is asymptotically and on average much smaller than the worst-case upper bound.

Regular Expressions with Intersection

Let Σ = {a 1 , . . . , a k } be an alphabet of size k. A word over Σ is a finite sequence of symbols of Σ. The empty word is denoted by ε. The set Σ is the set of all words over Σ. A language over Σ is a subset of Σ . The set RE ∩ of regular expressions with intersection over Σ contains the expression ∅ and all terms generated by the following grammar:

α → ε | a | (α + α) | (α • α) | (α ∩ α) | (α ) (a ∈ Σ), (1)
where the operator • (concatenation) is often omitted. Parenthesis can also be omitted considering the following precedences for the operators:

> • > ∩ > +.
The size of a regular expression α ∈ RE ∩ is denoted by ||α|| and defined as the number of occurrences of symbols (parenthesis not counted) in α. Similarly, |α| Σ denotes the number of occurrences of alphabet symbols in α, and |α| ∩ the 1 And a more general framework is also reported in [START_REF] Caron | A general framework for the derivation of regular expressions[END_REF].

number of occurrences of the binary operator ∩. The language L(α) for α ∈ RE ∩ is defined as usual, with L(α ∩ β) = L(α) ∩ L(β). We say that two regular expressions α, β ∈ RE ∩ are equivalent, if L(α) = L(β), and write α . = β in this case. For a set S ⊆ RE ∩ , the language of S is defined as L(S) = α∈S L(α). The notion of equivalence extends naturally to sets of regular expressions. The left-quotient of a language L w.r.t. a word w ∈ Σ is defined as w -1 L = { x | wx ∈ L }. The algebraic structure (RE ∩ , +, •, ∅, ε) constitutes an idempotent semiring, that with the unary operator is a Kleene algebra. Antimirov and Mosses [START_REF] Antimirov | Rewriting extended regular expressions[END_REF] presented a complete and sound axiomatization for RE ∩ , where the binary operator ∩ is idempotent, commutative, associative, distributes over +, and also satisfies the following axioms, where a i , a j ∈ Σ:

(ε ∩ β) . = ∅ ∧ (α . = βα + γ) ⇒ α . = β γ, ε ∩ α . = ε, ε ∩ (αβ) . = (ε ∩ α) ∩ β, ε ∩ a i . = ∅ ∩ α . = ∅, (a i α) ∩ (a j β) . = (a i ∩ a j )(α ∩ β), a i ∩ a j . = ∅ (a i = a j ), (αa i ) ∩ (βa j ) . = (α ∩ β)(a i ∩ a j ), α + (α ∩ β) . = α.
With the usual abuse of notation, define the function ε :

RE ∩ → {∅, ε} by ε(α) = ε if ε ∈ L(α)
, and ε(α) = ∅ otherwise. The methods developed in Sections 3 and 4 are syntactical and aim at building automata equivalent to a given regular expression. To ensure the finiteness of the constructions it is not necessary to consider regular expressions modulo any of the above properties2 . However, in some examples, for the sake of succinctness, we also consider regular expressions modulo the identities of • and +. Note that this does not affect the upper bounds of the number of states, both in the worst and in the average case.

Automata and Systems of Equations

We first recall the definition of a nondeterministic finite automaton (NFA) as a tuple A = S, Σ, S 0 , δ, F , where S is a finite set of states, Σ is a finite alphabet, S 0 ⊆ S a set of initial states, δ : S × Σ → 2 S the transition function, and F ⊆ S a set of final states. The language of A is

L(A) = {w ∈ Σ | δ(S 0 , w) ∩ F = ∅}.
The right language of a state s, denoted by L s , is the language accepted by A if we take S 0 = {s}. It is well known that, for each n-state NFA A, over Σ = {a 1 , . . . , a k }, having right languages L 1 , . . . , L n , it is possible to associate a system of linear language equations

L i = a 1 L 1i ∪ • • • ∪ a k L ki ∪ ε(L i ), for i ∈ [1, n],
where L ji = l∈δ(i,aj ) L l and L(A) = i∈S0 L i . In the same way, it is possible to associate to each regular expression a system of equations. We here extend Mirkin's contruction to regular expressions with intersection.

Definition 1. Consider α 0 ∈ RE ∩ over Σ = {a 1 , . . . , a k }. A support of α 0 is a set {α 1 , . . . , α n } of regular expressions with intersection that satisfies a system of equations

α i . = a 1 α 1i + • • • + a k α ki + ε(α i ) i ∈ [0, n], (2)
for some α 1i , . . . , α ki , where each α j,i is a (possibly empty) sum of elements in {α 1 , . . . , α n }.

It is clear that the existence of a support of α implies the existence of an NFA that accepts the language of α.

A support for a regular expression α ∈ RE ∩ can be computed using the function π : RE ∩ → 2 RE∩ defined below. First, we define some operations on sets of regular expressions. Given S, T ⊆ RE ∩ and

β ∈ RE ∩ , Sβ = { αβ | α ∈ S } and S∩ • T = { α∩β | α ∈ S, β ∈ T }. Note, in particular, that L(S∩ • T ) = L(S)∩L(T ).
Definition 2. Given α ∈ RE ∩ , the set π(α) is inductively defined by:

π(∅) = π(ε) = ∅, π(a) = {ε} (a ∈ Σ), π(α ) = π(α)α , π(α + β) = π(α) ∪ π(β), π(αβ) = π(α)β ∪ π(β), π(α ∩ β) = π(α) ∩ • π(β). Proposition 3. If α ∈ RE ∩ , then π(α) is a support of α.
Proof. We will proceed by induction on the structure of α. The proof for all cases, excluding α ∩ β, can be found in [START_REF] Mirkin | An algorithm for constructing a base in a language of regular expressions[END_REF][START_REF] Champarnaud | From Mirkin's prebases to Antimirov's word partial derivatives[END_REF][START_REF] Broda | On the average state complexity of partial derivative automata[END_REF]. Let π(α 0 ) = {α 1 , . . . , α n } and π(β 0 ) = {β 1 , . . . , β m } be a support of α 0 and β 0 , respectively. Thus,

α i . = a 1 α 1i + • • • + a k α ki + ε(α i ), for i = 0, . . . , n and β j . = a 1 β 1j + • • • + a k β kj + ε(β j ), for j = 1, . . . , m,
where, for all l = 1, . . . , k, α li and β lj are linear combinations of elements of π(α 0 ) and π(β 0 ), respectively. We want to prove that π(α 0 ∩ β 0 ) is a support for α 0 ∩ β 0 . For i = 0, . . . , n and j = 0, . . . , m, and using the axioms for ∩, we have

α i ∩ β j . =(a 1 α 1i + • • • + a k α ki + ε(α i )) ∩ (a 1 β 1j + • • • + a k β kj + ε(β j )) . =(a 1 α 1i ∩ a 1 β 1j ) + • • • + (a 1 α 1i ∩ a k β kj ) + (a 1 α 1i ∩ ε(β j ))+ . . . + (a k α ki ∩ a 1 β 1j ) + • • • + (a k α ki ∩ a k β kj ) + (a k α ki ∩ ε(β j ))+ . . . + (ε(α i ) ∩ a 1 β 1j ) + • • • + (ε(α i ) ∩ a k β kj ) + (ε(α i ) ∩ ε(β j )) . =(a 1 ∩ a 1 )(α 1i ∩ β 1j ) + • • • + (a k ∩ a k )(α ki ∩ β kj ) + (ε(α i ) ∩ ε(β j )) . =a 1 (α 1i ∩ β 1j ) + • • • + a k (α ki ∩ β kj ) + ε(α i ∩ β j ).
For each l = 1, . . . , k, we know that α li = i ∈I li α i and β lj = j ∈J lj β j , for I li ⊆ {1, . . . , n} and J lj ⊆ {1, . . . , m}. And, since

α li ∩ β lj . = i ∈I li α i ∩ j ∈J lj β j . = i ∈I li ,j ∈J lj (α i ∩ β j ), we conclude that π(α 0 )∩ • π(β 0 ) = {α 1 ∩β 1 , . . . , α 1 ∩β m , . . . , α n ∩β m } is a support for α 0 ∩ β 0 . Example 4. Given the regular expression α 1 = (b + ab + aab + abab) ∩ (ab) , π(α 1 ) = {bab ∩ b(ab) , ab ∩ b(ab) , b ∩ b(ab) , ε ∩ b(ab) , bab ∩ (ab) , ab ∩ (ab) , b ∩ (ab) , ε ∩ (ab) }.
The next proposition provides an upper bound on the cardinality of the support of a regular expression.

Proposition 5. For all α ∈ RE ∩ , the inequality |π(α)| ≤ 2 |α| Σ -|α|∩-1 holds.
Proof. We proceed by induction on the structure of the regular expression α. It is easily proved that the statement holds for the base cases ε, ∅ and a ∈ Σ. Assume that the result holds for some α, β ∈ RE ∩ . We will make use of the fact that 2 m + 2 n ≤ 2 m+n+1 , for any m, n ≥ 0. For α + β, one has

|π(α + β)| = |π(α) ∪ π(β)| ≤ |π(α)| + |π(β)| ≤ ≤ 2 |α| Σ -|α|∩-1 + 2 |β| Σ -|β|∩-1 ≤ ≤ 2 |α| Σ -|α|∩-1+|β| Σ -|β|∩-1+1 = 2 |α+β| Σ -|α+β|∩-1 .
The case for αβ is analogous. For α , one has

|π(α )| = |π(α)α | = |π(α)| ≤ 2 |α| Σ -|α|∩-1 = 2 |α | Σ -|α |∩-1 .
Finally, for α ∩ β, one has

|π(α ∩ β)| = |π(α) ∩ • π(β)| ≤ ≤ |π(α)| • |π(β)| ≤ 2 |α| Σ -|α|∩-1 • 2 |β| Σ -|β|∩-1 = = 2 |α| Σ -|α|∩-1+|β| Σ -|β|∩-1 = 2 |α∩β| Σ -(|α∩β|∩-1)-2 = = 2 |α∩β| Σ -|α∩β|∩-1 .
The next examples present families of regular expressions that witnesses the tightness of the upper bound established in Proposition 5.

Example 6. Let the regular expression r n ∈ RE ∩ over Σ = {a, b} be inductively defined by r 0 = a b , r 1 = b a and

r n = r n-2 ∩ r n-1 , for n ≥ 2. Using the definition of support it is straightforward that |π(r 0 )| = |{a b , b }| = 2 1 , |π(r 1 )| = |{b a, ε}| = 2 1 , and |π(r n )| = |π(r n-2 )| • |π(r n-1 )|, for n ≥ 2. Thus, we obtain |π(r n )| = 2 fib(n)
, for n ≥ 0, and where fib(n) is the Fibonacci sequence. Also,

|r 0 | Σ -|r 0 | ∩ -1 = 2 -0 -1 = 1, |r 1 | Σ -|r 1 | ∩ -1 = 2 -0 -1 = 1, and |r n | Σ -|r n | ∩ -1 = |r n-2 | Σ + |r n-1 | Σ -|r n-2 | ∩ -|r n-1 | Σ -1 -1 = (|r n-2 | Σ -|r n-2 | ∩ -1) + (|r n-1 | Σ -|r n-1 | ∩ -1), for n ≥ 2. Consequently, |r n | Σ -|r n | ∩ -1 = fib(n), for n ≥ 0. We conclude that |π(r n )| = 2 |rn| Σ -|rn|∩-1 , for n ≥ 0.
Example 7. Let the regular expression r n ∈ RE ∩ over {a}, be defined inductively by r 0 = a a and r n = r n-1 ∩ a a, for n ≥ 1. We have π(r 0 ) = π(a a) = {a a, ε}, and for n ≥ 1,

π(r n ) = {a * a, ε} ∩ • • • • ∩ • {a * a, ε}
|r n | ∩ = n. Therefore |π(r n )| = 2 n+1 = 2 2n+2-n-1 = 2 |rn| Σ -|rn|∩-1 .

Partial Derivatives

The notions of partial derivatives and partial derivative automata were introduced by Antimirov [START_REF] Antimirov | Partial derivatives of regular expressions and finite automaton constructions[END_REF] for standard regular expressions. We now consider the Antimirov construction from RE ∩ expressions to NFAs.

Definition 8. For a regular expression α ∈ RE ∩ and a symbol a ∈ Σ, the set ∂ a (α) of partial derivatives of α w.r.t. a is defined by: As for standard regular expressions, the partial derivative automaton of an expression α ∈ RE ∩ is defined by A pd (α) = ∂(α), Σ, {α}, δ α , F α , where

∂ a (∅) = ∅, ∂ a (ε) = ∅, ∂ a (b) = {ε}, if a = b ∅ otherwise, ∂ a (αβ) = ∂ a (α)β ∪ ∂ a (β), if ε(α) = ε ∂ a (α)β otherwise, ∂ a (α + β) = ∂ a (α) ∪ ∂ a (β), ∂ a (α ∩ β) = ∂ a (α) ∩ • ∂ a (β), ∂ a (α ) = ∂ a (α)α .
F α = { γ ∈ ∂(α) | ε(γ) = ε } and δ α (γ, a) = ∂ a (γ). It follows that L(A pd (α))
is exactly L(α). Mirkin's and Antimirov's constructions coincide for standard regular expressions. We will see that this is not true for regular expressions with intersection.

The following lemmas present some properties of the function ∂ w , used to prove Proposition 11 and are easy to prove. Lemma 9. For all S, S ⊆ RE ∩ and a ∈ Σ, the following property holds

∂ a (S ∩ • S ) = ∂ a (S) ∩ • ∂ a (S ).
Let suff(w) be the set of all non-empty suffixes of w, being defined as suff(w) = { v ∈ Σ + | ∃u ∈ Σ : uv = w }. Except for the second case, the following lemma was shown by Antimirov.

Lemma 10. For every regular expressions α, β ∈ RE ∩ and word w ∈ Σ + , ∂ w satisfies the following:

∂ w (α + β) = ∂ w (α) ∪ ∂ w (β), (3)
∂ w (α ∩ β) = ∂ w (α) ∩ • ∂ w (β), (4)
∂ w (αβ) ⊆ ∂ w (α)β ∪ v∈suff(w) ∂ v (β), (5)
∂ w (α ) ⊆ v∈suff(w) ∂ v (α)α . ( 6
)
Proposition 11. For every regular expressions α, β ∈ RE ∩ , the following holds.

∂ + (α + β) ⊆ ∂ + (α) ∪ ∂ + (β), ∂ + (α ∩ β) ⊆ ∂ + (α) ∩ • ∂ + (β), ∂ + (αβ) ⊆ ∂ + (α)β ∪ ∂ + (β), ∂ + (α ) ⊆ ∂ + (α)α .
Proof. First note that, given a set E ⊆ RE ∩ and a regular expression α ∈ RE ∩ , if, for all w ∈ Σ + , we have that ∂ w (α) ⊆ E, then we have w∈Σ + ∂ w (α) ⊆ E and thus ∂ + (α) ⊆ E. Moreover, we know that for every

w ∈ Σ + , ∂ w (α) ⊆ ∂ + (α), since ∂ + (α) = w∈Σ + ∂ w (α).
Let α, β ∈ RE ∩ be regular expressions over Σ. In order to prove the inclusions above, the facts mentioned above are used. The proof of each inclusion is given, respectively, by the following four proofs:

1. From equation ( 3), for all w ∈ Σ + , the following holds:

∂ w (α + β) = ∂ w (α) ∪ ∂ w (β) ⊆ ∂ + (α) ∪ ∂ + (β).
And thus, we can conclude that

∂ + (α + β) ⊆ ∂ + (α) ∪ ∂ + (β). 2.
In the same way, from equation ( 4), for all w ∈ Σ + , the following holds:

∂ w (α ∩ β) ⊆ ∂ w (α) ∩ • ∂ w (β) ⊆ ∂ + (α) ∩ • ∂ + (β). And then, ∂ + (α ∩ β) ⊆ ∂ + (α) ∩ • ∂ + (β).
3. From equation ( 5), for all w ∈ Σ + , the following holds:

∂ w (αβ) ⊆ ∂ w (α)β ∪ v∈suff(w) ∂ v (β) ⊆ ∂ + (α)β ∪ ∂ + (β). Thus, ∂ + (αβ) ⊆ ∂ + (α)β ∪ ∂ + (β).
4. Finally, from equation ( 6), for all w ∈ Σ + , the following holds: The following proposition relates the function ∂ + and the support π.

∂ w (α ) ⊆ v∈suff(w) ∂ v (α)α ⊆ ∂ + (α)α . Therefore, we have that ∂ + (α) ⊆ ∂ + (α)α .
Proposition 13. Given α ∈ RE ∩ , ∂ + (α) ⊆ π(α).
Proof. The proof proceeds by induction on the structure of α. It is trivial that

∂ + (∅) = π(∅), ∂ + (ε) = π(ε) and ∂ + (a) = π(a), for a symbol a ∈ Σ. Assume that ∂ + (α) ⊆ π(α) and ∂ + (β) ⊆ π(β) holds, for α, β ∈ RE ∩ . For α + β, we have ∂ + (α+β) ⊆ ∂ + (α)∪∂ + (β) ⊆ π(α)∪π(β). For α∩β, there is ∂ + (α∩β) ⊆ ∂ + (α)∩ • ∂ + (β) ⊆ π(α)∩ • π(β). For αβ, we have ∂ + (αβ) ⊆ ∂ + (α)β∪∂ + (β) ⊆ π(α)β∪π(β). Finally, for α , ∂ + (α ) ⊆ ∂ + (α)α ⊆ π(α)α .
Since, for every regular expression α ∈ RE ∩ , the set π(α) is finite, Proposition 13 also proves that the set ∂ + (α) is finite. For regular expressions without intersection it is known that π and ∂ + coincide [START_REF] Champarnaud | From Mirkin's prebases to Antimirov's word partial derivatives[END_REF]. Examples 4 and 12 show that there exists α ∈ RE ∩ such that π(α) = ∂ + (α). The following lemmas establish some conditions for the equality of π(α ∩ β) and ∂ + (α ∩ β) to hold for α, β ∈ RE ∩ , and will be used in Proposition 16.

Lemma 14. Given α, β ∈ RE ∩ , one has π(α ∩ β) = ∂ + (α ∩ β) if and only if π(α) = ∂ + (α), π(β) = ∂ + (β) and ∂ + (α ∩ β) = ∂ + (α) ∩ • ∂ + (β). Proof. (⇒) We have that π(α ∩ β) = ∂ + (α ∩ β) ⊆ ∂ + (α) ∩ • ∂ + (β). From Proposi- tion 13 follows that ∂ + (α) ⊆ π(α) and ∂ + (β) ⊆ π(β). Suppose by contradiction that ∂ + (α) ⊂ π(α) or ∂ + (β) ⊂ π(β). Then ∂ + (α ∩ β) ⊆ ∂ + (α) ∩ • ∂ + (β) ⊂ π(α) ∩ • π(β) = π(α ∩ β), a contradiction since π(α ∩ β) = ∂ + (α ∩ β). Thus, we conclude that π(α) = ∂ + (α) and π(β) = ∂ + (β). Consequently, π(α ∩ β) = π(α) ∩ • π(β) = ∂ + (α ∩ β).
(⇐) This follows trivially from the definition of support, i.e., π(α

∩ β) = π(α) ∩ • π(β), since π(α) = ∂ + (α) and π(β) = ∂ + (β). Lemma 15. Given α, β ∈ RE ∩ , such that ∂ w (α) = π(α) or ∂ w (β) = π(β) holds for all w ∈ Σ + , then ∂ + (α ∩ β) = ∂ + (α) ∩ • ∂ + (β). Proof. First, note that if γ ∈ RE ∩ and ∂ w (γ) = π(γ) for every w ∈ Σ + , then ∂ + (γ) = w∈Σ + ∂ w (γ) = π(γ). Given α, β ∈ RE ∩ ,
there are three possible cases to prove. First, suppose that, for all w ∈ Σ + , we have

∂ w (α) = π(α) and ∂ w (β) = π(β). Then ∂ + (α ∩ β) = w∈Σ + (∂ w (α) ∩ • ∂ w (β)) = π(α) ∩ • π(β) = ∂ + (α) ∩ • ∂ + (β).
It remains to prove the cases that either ∂ w (α) = π(α) or ∂ w (β) = π(β), for all w ∈ Σ + . The proof is the same for both cases. So, we will only present the proof for the first case. Suppose that, for all w ∈ Σ + , ∂ w (α) = π(α), it holds that

∂ + (α ∩ β) = w∈Σ + (∂ w (α) ∩ • ∂ w (β) = w∈Σ + (π(α) ∩ • ∂ w (β)) = w∈Σ + {α i ∩ β j | α i ∈ π(α), β j ∈ ∂ w (β)} = α i ∩ β j α i ∈ π(α), β j ∈ w∈Σ + ∂ w (β) = {α i ∩ β j | α i ∈ π(α), β j ∈ ∂ + (β)} = π(α) ∩ • ∂ + (β) = ∂ + (α) ∩ • ∂ + (β).
By Proposition 13, |π(α)| is an upper bound for the cardinality of ∂ + (α). This upper bound can be achieved, as shown by the following proposition.

Proposition 16. For any n ∈ N there exists a regular expression

r n ∈ RE ∩ of size O(n) such that |∂ + (r n )| = 2 |rn| Σ -|rn|∩-1 .
Proof. Consider the regular expressions r n ∈ RE ∩ from Example 7. We prove that π(r n ) = ∂ + (r n ). The proof proceeds by induction on n. For n = 0 and for all w ∈ Σ + , we have

∂ w (a a) = {a a, } = ∂ + (a a) = π(a a). Let us assume, by induction, that π(r n ) = ∂ + (r n ), for n ≥ 1. It follows from Lemma 15 that ∂ + (r n+1 ) = ∂ + (r n ∩ a a) = ∂ + (r n ) ∩ • ∂ + (a a). Since π(a a) = ∂ + (a a), π(r n ) = ∂ + (r n ), and ∂ + (r n ∩ a a) = ∂ + (r n ) ∩ • ∂ + (r n ), we conclude, from Lemma 14, that π(r n+1 ) = π(r n ∩ a a) = ∂ + (r n ∩ a a) = ∂ + (r n+1 ).
The next example provides another non-trivial family of regular expressions for which the set of partial derivatives and the support coincide.

)| = n i=2 2 i + 3 • 2 n , for n ≥ 2 Thus, for n ≥ 2 we have |π(s n )| = O(2 n ). Let m = |s n | Σ -|s n | ∩ -1 = 5 + 7n -1, i.e. n = (m -4)/7. Then, |π(s n )| = O(2 1 7 m ) = O(1.105 m ), which is much smaller than the upper bound 2 m . For all n ≥ 0, π(s n ) = ∂ + (s n ).

Average Complexity Results

We know that the number of states in the partial derivative automaton of an expression α has |π(α)| as its tight upper bound. In this section we estimate an upper bound for the asymptotic average size of π(α). This is done using standard methods of analytic combinatorics as expounded by Flajolet and Sedgewick [START_REF] Flajolet | Analytic Combinatorics[END_REF], which apply to generating functions f (z) = n a n z n associated with combinatorial classes. Given some measure of the objects of a combinatorial class A, the coefficient a n represents the sum of the values of this measure for all objects of size n. We will use the notation [z n ]f (z) for a n . For an introduction to this approach applied to formal languages, we refer to Broda et al. [START_REF] Broda | A hitchhiker's guide to descriptional complexity through analytic combinatorics[END_REF].

Although the methods here used are the standard ones from the Analytic Combinatorics (and Complex Analysis), each application of these techniques is always a challenge, as one cannot foresee the analytic difficulties that one can incur into when conducting the study of the generation function. The generating function f can be seen as a complex analytic function, and the study of its behaviour near its dominant singularity η (in case there is only one, as it happens with the functions here considered) gives us access to the asymptotic form of its coefficients. In particular, if f (z) is analytic in some appropriate neighbourhood of 0 containing η, then one has the following [START_REF] Flajolet | Analytic Combinatorics[END_REF][START_REF] Broda | A hitchhiker's guide to descriptional complexity through analytic combinatorics[END_REF]:

Proposition 18. If f (z) = a-b 1 -z/ρ+o 1 -z/ρ , with a, b ∈ R, b = 0, then [z n ]f (z) ∼ b 2 √ π ρ -n n -3/2 . If f (z) = a √ 1-z/ρ + o 1 √ 1-z/ρ
, with a ∈ R, and a = 0, then

[z n ]f (z) ∼ a √ π ρ -n n -1/2 .

Number of Expressions and Letters and ∩ symbols

The study of the combinatorial behaviour of the RE ∩ -expressions, both in terms of the number of expressions and the number of letters in them, is identical to the study of any other regular expressions with 3 binary operators and a single unary operator. Thus the results presented in Broda et al. [START_REF] Broda | Partial derivative automaton for regular expressions with shuffle[END_REF] are valid for the case here studied. Denoting by R k (z) the generating function for the number of RE ∩ -expressions without ∅ over a k letters alphabet, and by L k (z) the generating function for the number of letters in the expressions, one has:

[z n ]R k (z) ∼ c k ρ -n-1 2 k n -3 2 , ( 7
) [z n ]L k (z) ∼ k 12πc k ρ -n+ 1 2 k n -1 2 , (8)
where

c k = 4 √ 3+3k 6 √ π and ρ k = -1+2 √ 3+3k 11+12k
. The average number of letters in an expression of size n is given by

[z n ]L k (z) [z n ]R k (z)
.

Using equations ( 7) and ( 8), one obtains, asymptotically,

|α| Σ ∼ 3kρ k √ 3 + 3k ||α|| ----→ k→∞ 1 2 ||α||. (9)
The number of intersections in the RE ∩ -expressions under consideration can be computed as follows. Consider the bivariate generating function

I k (u, z) = m,n ι mn u m z n ,
where ι mn is the number of RE ∩ -expressions with m intersection symbols and size n. From (1), and using the symbolic method, we can write

I k (u, z) = (k + 1)z + 2zI k (u, z) 2 + uzI k (u, z) 2 + zI k (u, z).
Solving this for I k (u, z), differentiating the result w.r.t. u, and making u = 1, we obtain an expression for the generating function for the cumulative number of intersection symbols in all RE ∩ -expressions of size n:

I k (z) = 1 18z q k (z) + (k + 1)z 3 q k (z) + z -1 18z , (10)
where q k (z) = 1 -2z -(11 + 12k)z 2 , from which one obtains, using the same methods,

[z n ]I k (z) ∼ 1 6 √ π (k + 1) √ ρ k 4 √ 3 + 3k √ n - 4 √ 3 + 3k 3 √ ρ k n 3/2 ρ -n k . (11)
The average number of symbols ∩ in an expression of size n is given by

[z n ]I k (z) [z n ]R k (z) .
Using equations ( 7) and [START_REF] Champarnaud | From Mirkin's prebases to Antimirov's word partial derivatives[END_REF], one obtains, asymptotically,

|α| ∩ ∼ (k + 1)ρ k √ 3 + 3k ||α|| ----→ k→∞ 1 6 ||α||. (12)

Average Size of π

Let P k (z) denote the generating function for the size of π(α) for expressions without ∅. From Definition 2 it follows that, given an expression α, an upper bound, p(α), for the number of elements3 in the set π(α) satisfies:

p(ε) = 0, p(a) = 1, for a ∈ Σ, p(α ) = p(α), p(α + β) = p(α) + p(β), p(αβ) = p(α) + p(β), p(α ∩ β) = p(α)p(β).
From this, we directly get

P k (z) = kz + 4zP k (z)R k (z) + zP k (z) + zP k (z) 2 ,
from which we obtain the following closed expression

P k (z) = 1 -z + 2 q k (z) -p k (z) + 4(1 -z) q k (z) 6z , (13)
where

p k (z) = 5 -10z -(43 + 84k)z 2 . ( 14
)
One now needs to determine the dominant singularity of P k (z) which can either be a root of q k (z) or a root of r k (z) = p k (z) + 4(1 -z) q k (z). We need to know which of the two expressions r k (z) or q k (z) has the smallest positive zero. Because this is not trivial (note that one needs to decide this for all k), one will do it indirectly using the method expounded in the following paragraphs.

Observing that r k (0) = 9 is positive and

r k (ρ k ) = 12 13 -14k -24k 2 + (8k -4) √ 3 + 3k (11 + 12k) 2 < 0,
by Bolzano theorem, r k (z) must have a positive zero smaller than ρ k . This conclusion could be achieved, directly, from the fact that the absolute value of the negative zero of q k (z) is smaller than its positive zero, and thus, by Pringsheim theorem [START_REF] Flajolet | Analytic Combinatorics[END_REF], another smaller positive singularity of P k (z) necessarily exists that can only be due to r k (z).

(0) = 1 < r k (0) = 9, and r k (x) = s k (x) only at the end points of [ρ k , ρ k ] it follows that s k (x) < r k (x) in ]ρ k , ρ k [. Considering the four real zeros of the polynomial r k (z)s k (z)
, given what we just said, we conclude that the two more distant zeros from the origin are the roots of r k (z). In fact, we can obtain an explicit expression for the zeros of r k (z)s k (z) by noticing that

p k (z) ± 4(1 -z) q k (z) = 1 -z ± 2 q k (z) 2 -36kz 2 = 1 -z ± 2 q k (z) -6 √ kz 1 -z ± 2 q k (z) + 6 √ kz ,
and thus, solving the equations resulting of nulling those factors, we obtain the four zeros of r k (z)s k (z):

η k = 4 √ 2k + 1 + 2 √ k -1 28k + 4 √ k + 15 , η k = - 4 √ 2k + 1 + 2 √ k + 1 28k -4 √ k + 15 , η k = 4 √ 2k + 1 -2 √ k -1 28k -4 √ k + 15 , η k = - 4 √ 2k + 1 -2 √ k + 1 28k + 4 √ k + 15 . (15)
It is possible to verify that η k and η k are the roots of r k (z) and the other two the roots from s k (z). Therefore, one has 16)

r k (z)s k (z) = (7056k 2 + 7416k + 2025)(z -η k )(z -η k )(z -η k )(z -η k ). (
From ( 13) one has

6zP k (z) = 1 -z -r k (z) + 2 q k (z), (17)
and we split the study of the coefficients of the series of P k (z) into the study of the coefficients of 1 -z -r k (z) and of 2 q k (z). For the first one, we use that

r k (z) = 7056k 2 + 7416k + 2025 s k (z) η k (η k -z)(η k -z)(η k -z) 1 - z η k ,
and the fact that given a complex function f , defined in a neighbourhood of η such that lim z→η f (z) = a, one has, for all r ∈ R, f (z)(1 -z/η) r = a(1 -z/η) r + o((1 -z/η) r ), together with Proposition 18, to obtain

[z n ] 1 -z -r k (z) ∼ λ k η -n k n -3 2 ,
where

λ k = (7056k 2 + 7416k + 2025)(η k -η k )(η k -η k )(η k -η k )η k 2πs k (η k ) 1 2 . ( 18
)
For the last summand one has, similarly, 2 q k (z) = 4

4 √ 3 + 3k ρ 1 2 k (ρ k -ρk ) 1 2 (1 -z/ρ k ) 1 2 + o (1 -z/ρ k ) 1 2
, from which it follows, [z n ]2 q k (z) ∼ -µ k ρ -n k n -3 2 , where

µ k = 2π -1 2 ρ 1 2 k 4 √ 3 + 3k. ( 19
)
Summing up, we get that

[z n ]P k (z) ∼ 1 6 λ k η -(n+1) k -µ k ρ -(n+1) k n -3 2 . ( 20
)
In order to see what this result entails for the average case when compared with the worst case result, expressed in Proposition 5, attend to the following. Considering the estimates given in ( 9) and ( 12), the worst-case upper bound 2 |α| Σ -|α|∩-1 from Proposition 5 leads to an upper bound for the average case roughly of 3 √ 2 ||α|| , for α large enough. As 3 √ 2 ∼ 1.25992, the result just obtained shows that the upper bound for the average complexity is significantly smaller than the one for the worst case.

Conclusions

The conversion of a regular expression with intersection α to NFA is in the worstcase 2 Ω(||α||) [START_REF] Gelade | Succinctness of regular expressions with interleaving, intersection and counting[END_REF][START_REF] Gruber | Finite automata, digraph connectivity, and regular expression size[END_REF][START_REF] Gruber | On the descriptional and algorithmic complexity of regular languages[END_REF]. This fact leads to the assumption that, although succinct, these expressions are not useful in practical applications. Here we show that, asymptotically, an upper bound for the average-state complexity of A pd (α) is exponential but with a base only slightly above 1. Actually, experimental results using a uniform distribution suggest that the average-state complexity of A pd (α) may even be polynomial [START_REF] Bastos | Manipulation of Extended Regular Expressions with Derivatives[END_REF].

n+1 .

 n+1 Thus |π(r 0 )| = 2 and |π(r n )| = |π(r 0 )| n+1 = 2 n+1 . Note that |r n | Σ = 2n + 2 and

  This definition is extended to words w ∈ Σ by ∂ ε (α) = {α}, ∂ wa (α) = αi∈∂w(α) ∂ a (α i ), and ∂ w (R) = αi∈R ∂ w (α i ), where R ⊆ RE ∩ . It follows easily that L(∂ w (α)) = w -1 L(α). The set of partial derivatives of an expression α is ∂(α) = w∈Σ ∂ w (α). We also define ∂ + (α) = w∈Σ + ∂ w (α).

Example 12 .

 12 Consider again α 1 = (b+ab+aab+abab)∩(ab) . We have∂ + (α 1 ) = {bab ∩ b(ab) , ab ∩ b(ab) , b ∩ b(ab) , ab ∩ (ab) , ε ∩ (ab) }. Now, with β = (b + ab + aab + abab), one has ∂ + (β) ∩ • ∂ + ((ab) ) ={bab ∩ b(ab) , ab ∩ b(ab) , b ∩ b(ab) , ε ∩ b(ab) , bab ∩ (ab) , ab ∩ (ab) , b ∩ (ab) , ε ∩ (ab) }.Thus, we conclude that ∂ + (α 1 ) ⊂ ∂ + (b + ab + aab + abab) ∩ • ∂ + ((ab) ).

Example 17 .

 17 For n ≥ 0 let the regular expression s n ∈ RE ∩ be inductively defined by s 0 = (a + b) b(a + b) and s n = ((a + b)s n-1 (a + b)) ∩ ((a + b) (a + b)), for n ≥ 1. The alphabetic length of s n is |s n | Σ = 5 + 8n and |s n | ∩ = n. The cardinality of the support of s n is given by: |π(s 0 )| = 2, |π(s 1 )| = 6 and |π(s n

[Proposition 19 .

 19 z n ]P k (z) [z n ]R k (z) Setting γ k = ρ k η k ,this means that, on average, |π(α)| ∼ γ ||α|| k . One has γ 2 ∼ 1.01655, γ 10 ∼ 1.04137, γ 100 ∼ 1.For large values of k and n an upper bound for the average number of states of A pd is (1.056 + o(1)) n .

  (z) has also two real zeros in the same interval, and since r k (z)s k (z) is a fourth degree polynomial, it follows that r k (z) has exactly two zeros, η k and η k , which are real. Since s k

		Letting
		ρk =	-1 -2 √ 11 + 12k 3 + 3k	,
	and observing that
	r k (ρ k ) = -	12 -13 + 14k + 24k 2 + (8k -4) (11 + 12k) 2	√	3 + 3k	< 0,
	one concludes that r

k (z) has necessarily two real zeros in its domain,

[ρ k , ρ k ]. Analogously, s k (z) = p k (z) -4(1 -z) q k

As is the case, for instance, for Brzozowski DFA or Caron et al approach.

This upper bound corresponds to the case where all unions in π(α) are disjoint.

This work was partially supported by CMUP (UID/MAT/00144/2013), which is funded by FCT (Portugal) with national (MEC) and european structural funds through the programs FEDER, under the partnership agreement PT2020.