Chris Keeler
email: keeler@cs.queensu.ca

Kai Salomaa
email: ksalomaa@cs.queensu.ca

Branching Measures and Nearly Acyclic NFAs

To get a more comprehensive understanding of the branching complexity of nondeterministic finite automata (NFA), we introduce and study the string path width and depth path width measures. The string path width on a string w counts the number of all complete computations on w, and the depth path width on an integer counts the number of complete computations on all strings of length . We give an algorithm to decide the finiteness of the depth path width of an NFA. Deciding finiteness of string path width can be reduced to the corresponding question on ambiguity. An NFA is nearly acyclic if any computation can pass through at most one cycle. The class of nearly acyclic NFAs consists of exactly all NFAs with finite depth path width. Using this characterization we show that the finite depth path width of an m-state NFA over a k-letter alphabet is at most (k + 1) m-1 and that this bound is tight. The nearly acyclic NFAs recognize exactly the class of constant density regular languages.

Introduction

Finite automata are a fundamental model of computation that has been extensively studied since the 1950s. The last decades have seen much work on the descriptional complexity, or state complexity, of regular languages [START_REF] Goldstine | Descriptional Complexity of Machines with Limited Resources[END_REF][START_REF] Holzer | Descriptional and Computational Complexity of Finite Automata -A Survey[END_REF][START_REF] Yu | Regular languages[END_REF].

The degree of ambiguity of a nondeterministic finite automaton (NFA) A on a string w is the number of accepting computations of A on w. Ravikumar and Ibarra [START_REF] Ravikumar | Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation[END_REF] have first studied systematically the size-trade-offs between NFAs of different degrees of ambiguity. Leung [START_REF] Leung | Separating Exponentially Ambiguous Finite Automata From Polynomially Ambiguous Finite Automata[END_REF] has shown that general NFAs can be exponentially more succinct than polynomially ambiguous NFAs, and Hromkovič and Schnitger [START_REF] Hromkovič | Ambiguity and communication[END_REF] have established a descriptional complexity separation between polynomially ambiguous and finitely ambiguous NFAs.

The degree of ambiguity is defined in terms of the number of accepting computations, and does not directly limit the total amount of nondeterminism in a computation. The computation of an unambiguous NFA may include an unbounded number of nondeterministic steps, as long as at each nondeterministic step, only one choice can lead to acceptance. The tree width1 (a.k.a. leaf size) measure counts the number of leaves of the computation tree [START_REF] Hromkovič | Communication Complexity Method for Measuring Nondeterminism in Finite Automata[END_REF][START_REF] Palioudakis | State Complexity of Finite Tree Width NFAs[END_REF][START_REF] Palioudakis | Quantifying Nondeterminism in Finite Automata[END_REF]. Other measures of nondeterminism for finite automata have also been considered [6-8, 10, 18].

We study a measure called string path width that counts the number of complete accepting and non-accepting computations of an NFA on a given string. The string path width can be viewed as a blending between the tree width measure and the degree of ambiguity. For certain NFAs, the string path width is the same as tree width, and for others the same as ambiguity. In fact, Goldstine et al. [START_REF] Goldstine | On the relation between ambiguity and nondeterminism in finite automata[END_REF] have defined 'ambiguity' as the number of complete computations, which coincides with our notion of string path width. The degree automata [START_REF] Kintala | Concise Representations of Regular Languages by Degree and Probabilistic Finite Automata[END_REF] extend these notions by considering the ratio of the number accepting computations and the number of all computations on a given string.

To get a more comprehensive understanding of the degree of branching2 of an NFA, we introduce the depth path width measure, which counts the total number of complete computations on all inputs of a given length. We establish necessary and sufficient conditions for an NFA to have infinite depth path width. These conditions are based on the existence of cycles satisfying certain requirements. This characterization yields a polynomial time algorithm to decide whether or not the depth path width of an NFA is bounded. Finiteness of string path width can be decided with existing algorithms from the literature [START_REF] Weber | On the Degree of Ambiguity of Finite Automata[END_REF].

It is well known that acyclic finite automata characterize exactly the finite languages. We characterize regular languages having bounded depth path width by an extension of acyclic NFAs, called nearly acyclic NFAs. An NFA A is said to be nearly acyclic if A, roughly speaking, it does not contain two distinct cycles where a state of one cycle is reachable from the other cycle.

We show that there exists an m-state nearly acyclic NFA over a k-letter alphabet having depth path width (k + 1) m-1 , and that this is an upper bound for all m-state NFAs over a k-letter alphabet having finite depth path width. Finally, we show that nearly acyclic NFAs recognize exactly the regular languages of bounded density [START_REF] Shallit | Numeration Systems, Linear Recurrences, and Regular Sets[END_REF]. For nearly acyclic DFAs we have a stronger correspondence: any DFA recognizing a bounded density language must be nearly acyclic.

Preliminaries

Here we recall and introduce some notation and definitions. More information on finite automata can be found e.g. in [START_REF] Shallit | Second Course in Formal Languages and Automata Theory[END_REF][START_REF] Yu | Regular languages[END_REF]. The set of strings over a finite alphabet Σ is Σ * , and ε is the empty string. The cardinality of a finite set F is denoted |F | and N is the set of non-negative integers.

A nondeterministic finite automaton (NFA) is a tuple A = (Q, Σ, δ, q 0 , F ) where Q is the finite set of states, Σ is the input alphabet, δ : Q × Σ → 2 Q is the transition function, q 0 ∈ Q is the initial state and F ⊆ Q is the set of final states.
The transition function δ is in the usual way extended as a function Q×Σ * → 2 Q , and the language recognized by A is

L(A) = {w ∈ Σ * | δ(q 0 , w) ∩ F = ∅}. If |δ(q, b)| ≤ 1 for all q ∈ Q
and b ∈ Σ, the automaton A is a deterministic finite automaton (DFA). Note that we allow NFAs and DFAs to have undefined transitions. Our definition does not allow multiple start states or ε-transitions. Unless otherwise mentioned, we always assume that an NFA does not have any unreachable states.

A (state) path of the NFA A with underlying string

w = b 1 b 2 • • • b k , b i ∈ Σ, i = 1, . . . , k, k ≥ 0,
is a sequence of states (p 0 , p 1 , . . . , p ), where p j ∈ δ(p j-1 , b j ), j = 1, . . . , and either = k, or, < k and δ(p , b +1 ) = ∅. That is, the path must read the entire underlying string unless it encounters an undefined transition. Two paths are equal if and only if they have the same sequence of states and underlying string.

A path beginning in the start state q 0 , is a computation of A on the underlying string w. A computation (q 0 , p 1 , . . . , p ) is a complete computation on a string b

1 b 2 • • • b k if = k.
An accepting computation is a complete computation that ends in an accepting state of F . The set of all (not necessarily complete) computations of A on the string w is denoted comp A (w).

Intuitively, a computation of A on a string w is a sequence of states that A reaches when started with the initial state and the symbols of w are read one by one. A complete computation ends with a state reached after consuming all symbols of w. An incomplete computation ends with a state where the transition on the next symbol of w is undefined.

The length of a path

C 1 = (p 0 , p 1 , . . . , p ) is |C 1 | = (the number of tran- sitions). The catenation of C 1 and a path C 2 = (p , p 1 , . . . p m ) is C 1 • C 2 = (p 0 , . . . , p , p 1 , . . . p m ). That is, paths C 1 and C 2 can be catenated if C 1 ends with the first state of C 2 . A path (p 0 , p 1 , . . . , p k ), k ≥ 1, with underlying string b 1 b 2 • • • b k is a cycle if p 0 = p k .
A cycle with one transition from a state to itself is called a self-loop. (A path of length zero with no transitions is not a cycle.) An NFA with no cycles is called an acyclic NFA (aNFA).

Cycles that are obtained from each other by a cyclical shift are said to be equivalent: For 0 < i < k, the above cycle (with

p 0 = p k ) is equivalent to the cycle (p i , . . . , p k , p 1 , . . . p i-1 , p i ) having underlying string b i+1 • • • b k b 1 • • • b i .
We define path trees that represent all computations of an NFA on all strings of a given length. Note that this is different than the notion of computation trees [START_REF] Hromkovič | Communication Complexity Method for Measuring Nondeterminism in Finite Automata[END_REF][START_REF] Palioudakis | State Complexity of Finite Tree Width NFAs[END_REF], which represent all computations of an NFA on a given string w.

For ∈ N, the path tree of an NFA A = (Q, Σ, δ, q 0 , F ) of depth , T A, , is a finite tree where the nodes are labelled by elements of Q and the edges are labelled by elements of Σ, defined inductively as follows:

-T A,0 consists of a single node labelled by q 0 . -Consider ≥ 1 and let leaf( -1) be the set of leaf nodes of T A, -1 having distance -1 from the root. If an x ∈ leaf( -1) is labelled by q ∈ Q, then for each c ∈ Σ and q ∈ δ(q, c), in the tree T A, we add to node x a child y labelled by q , and the edge between x and y is labelled with c.

The pruned path tree of depth , T p A, , is obtained from T A, by recursively removing all leaf nodes which have distance smaller than from the root node.

The degree of ambiguity of an NFA A on a string w, da(A, w) [START_REF] Goldstine | Descriptional Complexity of Machines with Limited Resources[END_REF][START_REF] Ravikumar | Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation[END_REF], is the number of accepting computations of A on w, and the tree width of A on w, tw(A, w) [START_REF] Hromkovič | Communication Complexity Method for Measuring Nondeterminism in Finite Automata[END_REF][START_REF] Palioudakis | State Complexity of Finite Tree Width NFAs[END_REF], is the number of (not necessarily complete) computations of A on w. Note that Hromkovič et al. [START_REF] Hromkovič | Communication Complexity Method for Measuring Nondeterminism in Finite Automata[END_REF] call this "leaf size". Tree width is usually defined as the number of leaves of the computation tree of A on w. This quantity is identical to the cardinality of the set comp A (w).

For ≥ 0, the degree of ambiguity (respectively, tree width) of A on strings of length is defined as da(A, ) = max{da(A, w) | w ∈ Σ } (respectively, tw(A, ) = max{tw(A, w) | w ∈ Σ }). Strictly speaking, using common practice, we use da(A, •) (and tw(A, •)) to denote two different functions where one takes a string and the other an integer as argument.

The ambiguity (respectively, the tree width) of the NFA A is said to be finite if the above values are bounded for all ∈ N, and in this case, the degree of ambiguity (respectively, the tree width) of A is denoted da sup (A) (respectively, tw sup (A)).

String Path Width and Depth Path Width

We consider measures that count the number of complete computations on a given string and on all strings of given length, respectively. In the following, A = (Q, Σ, δ, q 0 , F ) is always an NFA. The string path width of A on a string w ∈ Σ * , SPW(A, w), is defined as the number of complete computations of A on w. For ∈ N, the string path width of A on strings of length is SPW(A, ) = max{SPW(A, w) | w ∈ Σ }, and when this value is bounded, the string path width of A is denoted SPW sup (A).

Example 1. For the NFA A 1 given in Figure 1:

-SPW(A 1 , ab) = 2, complete computations {(0, 1, 0), (0, 1, 2)} -SPW(A 1 , aaaa) = 1, complete computations {(0, 1, 0, 1, 0)} -Generally, SPW(A 1 , (ab) x ) = x + 1, x ∈ N 0 1 2 a a,b b a,b Fig. 1. NFA A1
In fact, Goldstine et al. [START_REF] Goldstine | On the relation between ambiguity and nondeterminism in finite automata[END_REF] have defined 'ambiguity' as the number of complete computations, which coincides with our notion of string path width. The string path width can be viewed as a blend between ambiguity and tree width in the sense of the following lemma. Since string path width counts only complete computations while tree width counts all computations, the string path width of an NFA A on a string w will always be at most the tree width of A on w.

Lemma 1. Consider an NFA

A = (Q, Σ, δ, q 0 , F ) and let w ∈ Σ * . (i) da(A, w) ≤ SPW(A, w) ≤ tw(A, w). (ii) If A has no undefined transitions, that is, δ(q, b) = ∅ for all q ∈ Q, b ∈ Σ, then SPW(A, w) = tw(A, w). (iii) If all states of A are final, then SPW(A, w) = da(A, w).
Since string path width is, in the sense of Lemma 1 (iii), a special case of degree of ambiguity, from algorithms and bounds for ambiguity we get corresponding results for string path width. This is established using the transformation of the following lemma. In general, the transformed automaton is not equivalent to the original. Note that Lemma 1 (ii) gives a correspondence between string path width and tree width, but this cannot be used in a similar way because the corresponding transformation changes the string path width of the NFA.

Lemma 2. Given an NFA A = (Q, Σ, δ, q 0 , F ), we can construct in linear time an NFA A such that da(A , w) = SPW(A, w) for all strings w ∈ Σ * .

Using Lemma 2, and the results by Weber and Seidl [START_REF] Weber | On the Degree of Ambiguity of Finite Automata[END_REF], we get: Corollary 1 ( [START_REF] Weber | On the Degree of Ambiguity of Finite Automata[END_REF]). Let A = (Q, Σ, δ, q 0 , F ) be an NFA. Also, it is known that for a fixed k and a given NFA A it can be decided in polynomial time whether da sup (A) (and consequently whether SPW sup (A)) is at least k, but the question for degree of ambiguity becomes PSPACE-complete if k is part of the input [START_REF] Chan | On the finite valuedness problem for sequential machines[END_REF].

Next we introduce the depth path width of an NFA as the number of all complete computations of a given length. This metric can be viewed as a broader version of the string path width; while the string path width counts the number of computations on a specific string, the depth path width considers all strings of the same length.

Consider an NFA A = (Q, Σ, δ, q 0 , F ) and let ∈ N. The depth path width of A on strings of length is

DPW(A, ) = w∈Σ SPW(A, w).
The depth path width of the NFA A is defined as DPW sup (A) = sup ∈N (DPW(A, )).

Example 2. For the DFA A 2 = (Q, Σ, δ, q 0 , F ) given in Figure 2: -Generally, DPW(A 2 , ) = + 1, ∈ N.

Directly from the definition it follows that for NFAs over a unary alphabet, the notion of depth path width coincides with string path width.

We give the necessary and sufficient conditions for an NFA to have unbounded depth path width. For this we use the correspondence between depth path width and the number of leaves in path trees (defined in section 2). Lemma 3. Consider an NFA A and ∈ N. The value DPW(A, ) is equal to the number of leaves of the pruned path tree T p A, . Intuitively, the conditions of Theorem 1 mean that q 1 and q 2 belong to a cycle and the state q 1 has another transition to a state q 3 such that the computations originating from q 3 are defined on infinitely many strings. Here q 3 may or may not belong to the same cycle as q 1 and q 2 . If q 2 = q 3 , then the alphabet symbols a and b must be distinct.

Theorem 1. Consider an NFA A = (Q, Σ, δ, q 0 , F ). The depth path width of A is unbounded if and only if the following holds:

There exist q 1 , q 2 , q 3 ∈ Q and a, b ∈ Σ, where q 2 = q 3 or a = b, such that (i) q 2 ∈ δ(q 1 , a) and state q 1 is reachable from q 2 , and, (ii) q 3 ∈ δ(q 1 , b) and the language of the NFA A = (Q, Σ, δ, q 3 , Q) is infinite.

Proof. First assume that conditions (i) and (ii) hold. Let C 1 be a computation from q 0 to q 1 (recall that we assume that NFAs have no unreachable states). Let C 2 be a cycle from q 1 back to q 1 that begins with the transition on a to q 2 .

To show that DPW sup (A) is infinite, it is sufficient to show that for all M ∈ N there exists such that DPW(A, ) ≥ M . By condition (ii) there exists a path C M having length M • |C 2 | that begins in q 1 with the transition on b to q 3 . Now

A has M different computations of length |C 1 | + M • |C 2 |: C 1 • C i 2 • D i , i = 0, 1, . . . , M -1, where D i is an initial part of the path C M having length (M -i) • |C 2 |.
Note that the above are all distinct computations because the transitions from q 1 to q 2 on a and from q 1 to q 3 on b are distinct.

We sketch the proof in the "only if" direction: If DPW sup (A) is infinite, using Lemma 3 we see that the number of leaves of the pruned path tree T p A, can be chosen arbitrarily large for sufficiently large . When some state of A repeats on a path from the root to a leaf, we get a cycle and states satisfying conditions (i) and (ii).

The conditions of Theorem 1 yield a polynomial time algorithm to test whether the depth path width of an NFA is infinite. 3: Create a distance matrix M , where M [q, q ] is the minimum distance from state q ∈ Q to state q ∈ Q. 4: infinityCondition = False 5: for all q1 ∈ Q do 6:

for all q2 ∈ δ(q1, a) and q3 ∈ δ(q1, b) such that (q2 = q3 or a = b) do 7:

if

M [q2, q1] = ∞ then 8:
Set initial state of A to be q3 9:

if L(A ) is infinite then 10: infinityCondition = True 11:

end if 12:

end if 13:

end for 14: end for 15: return infinityCondition the NFA A takes Θ(m + |δ|) time. Creating the adjacency matrix takes Θ(m 3 ) time and Θ(m 2 ) space using the Floyd-Warshall algorithm [START_REF] Cormen | Introduction to Algorithms[END_REF]. The two for all statements multiply the inner complexity by Θ(m 3 ), as there are m 3 triples of the form (q 1 , q 2 , q 3 ). Checking whether L(A ) is infinite takes O(m + |δ|) time using Tarjan's Strongly Connected Components algorithm [START_REF] Tarjan | Depth-First Search and Linear Graph Algorithms[END_REF]. So the worstcase runtime is O(m

+ |δ| + m 3 + m 3 • (m + |δ|)) which simplifies to O(|Σ| • m 5 ).

Depth Path Width of Nearly Acyclic NFAs

We want to derive an upper bound for the finite depth path width of an m-state NFA. First we develop bounds for the depth path width measure of acyclic NFAs where the depth path width is naturally guaranteed to be finite. .

Note that the result of Proposition 1 indicates that the largest possible depth path width of an m-state aNFA is obtained by strings of length, roughly, m divided by two.

We now extend the result for arbitrary alphabet sizes.

Theorem 3. Let A be an m-state aNFA. Then

DPW sup (A) ≤ sup m-1 2 ≤ ≤m-1 k • m -1 .
The upper bound can be improved for acyclic DFAs (aDFA).

Corollary 2. For an aDFA D with m states and k alphabet characters, the depth path width of D is at most k m-1 .

It is easy to verify that an NFA A does not satisfy the conditions of Theorem 1 if and only if A does not have two non-equivalent cycles where one is reachable from the other. (Two cycles are equivalent if they are obtained from each other by a cyclical shift, see section 2.) This condition forms the basis for the following definition.

Definition 1. An NFA A is nearly acyclic (naNFA) if it does not have two non-equivalent cycles, C 1 and C 2 , such that a state of C 2 is reachable from a state of C 1 . An naNFA with a deterministic transition function is called a nearly acyclic DFA (naDFA).

By Theorem 1, Definition 1 gives the most general class of NFAs that have finite depth path width. The influence of cycles that are reachable from one another is considered in a more general way by Msiska and van Zijl [START_REF] Msiska | Interpreting the Subset Construction using Finite Sublanguages[END_REF].

The limitation on the reachability between cycles implies a limitation on the number of (non-equivalent) cycles in a nearly acyclic NFA. Lemma 4. An m-state naNFA has at most (m -1) cycles.

The naNFAs with a maximal number of acyclic transitions and one self-loop on the initial state turn out to be useful for obtaining bounds for depth path width.

Definition 2. An m-state initial self-loop maximal nearly acyclic NFA, an imax-naNFA, over an alphabet Σ has the set of states {0, 1, . . . , m -1} where 0 is the start state, there exists a transition on each alphabet symbol from i to j for all 0 ≤ i < j ≤ m -1, and 0 has a self-loop.

The transitions of an imax-naNFA are uniquely determined, except for the self-loop on the initial state, which can be on an arbitrary element of Σ. (If needed we could specify the symbol labelling the self-loop.) Also, for purposes of depth path width, the set of final states can be arbitrary. In Figure 3 illustrating an m-state imax-naNFA, we use m -1 as the only final state.

We calculate the depth path width of imax-naNFAs as a function of the number of states and alphabet size. Since acyclic DFAs are a special case of nearly acyclic DFAs, we can use the value acquired in Corollary 2 as a lower limit on the upper bound for the depth path width of an naDFA. Lemma 5 gives the depth path width of imax-naNFAs. From Lemma 4 we recall that an naNFA can have multiple cycles, however, it seems plausible that an m-state imax-naNFA could have maximal depth path width among all mstate naNFAs. This is established in the following lemmas. Lemma 6. Let A be an naNFA with (one or more) cycles of length at least two. Then there exists an naNFA A with the same number of states over the same alphabet where all cycles are self-loops and DPW sup (A ) ≥ DPW sup (A).

Consider an m-state naNFA B where all cycles are self-loops. We can define an injective mapping from the set of computations of B having length to the length computations of an m-state imax-naNFA A. This then implies that the depth path width of B is at most that of A, and the observation is the basis for the following lemma. Proof. By Lemma 6, A can be converted to an m-state naNFA A over the same alphabet without decreasing the depth path width where all cycles in A are self-loops. Let B imax be an m-state imax-naNFA over the same alphabet. Now

DPW sup (A) ≤ DPW sup (A ) ≤ DPW sup (B imax ) = (k + 1) m-1 ,
where the second inequality follows from Lemma 7 and the equality from Lemma 5. The equality also establishes the second claim of the theorem.

Languages recognized by naNFAs

Acyclic NFAs recognize the family of finite languages and, similarly, the nearly acyclic NFAs recognize a proper subfamily of the regular languages. The density of a language L ⊆ Σ * is defined as the function d [START_REF] Shallit | Numeration Systems, Linear Recurrences, and Regular Sets[END_REF]) The density of a regular language L over Σ is bounded, that is d L ( ) ∈ O(1), if and only if L can be represented as a finite union of regular expressions xy * z, where x, y, z ∈ Σ * .

L ( ) = |L ∩ Σ |, ∈ N. Proposition 2. (Shallit
The nearly acyclic NFAs recognize exactly the constant density languages. Theorem 6. A regular language L has constant density if and only if L is recognized by a nearly acyclic NFA.

Proof. Suppose that L ⊆ Σ * is recognized by an m-state naNFA A. We show that d L ( ) ≤ m3 • |Σ| m for all ∈ N. For ≤ m -1 there is nothing to prove.

Consider then strings of length ≥ m. For each w ∈ Σ accepted by A, fix one accepting computation C w . Since A is nearly acyclic and ≥ m, the computation C w must pass through exactly one cycle. Thus, we can write w = w pref w cyc w suf where w cyc is the maximal substring of w that in the computation C w is "processed" by transitions of the cycle, and |w pref • w suf | ≤ m -1. The number of strings of length at most m -1 is upper bounded by |Σ| m . In a string of length at most m -1 the cycle can occur in at most m locations and, according to Lemma 4, A has at most m cycles and, furthermore, each cycle (equivalence class) can be started in at most m positions. 3 Once a particular cycle and its position in the "acyclic part" of the computation (consuming the prefix w pref and suffix w suf ) are chosen, the length of the computation in the cycle is determined by the total length . Thus, the number of accepted strings of length is upper bounded by the constant m 3 • |Σ| m .

Conversely, if L has constant density then, by Proposition 2, L can be represented as a finite union of regular expressions of the form xy * z, x, y, z ∈ Σ * . An naNFA with one cycle recognizes xy * z, and the languages recognized by naNFAs are clearly closed under union.

By considering unary regular languages it is easy to see that a constant density language can be recognized by an NFA that is not nearly acyclic. However, for DFAs, we get the implication also in the converse direction.

Theorem 7. Any DFA recognizing a constant density language must be nearly acyclic.

As a corollary, we get that determinizing an naNFA must result in a nearly acyclic DFA. This could of course also be seen using a direct construction but it would require some effort. Corollary 3. Let A be an naNFA and let D be the DFA obtained from A using the subset construction. Then D is nearly acyclic.

Conclusion

We have given an algorithm to decide whether the depth path width of an NFA is unbounded, and characterized automata with bounded depth path width as the class of nearly acyclic NFAs. We have given an upper bound for the finite depth path width of an m-state NFA over an alphabet of size k and shown that this bound is tight.

Nearly acyclic NFAs extend the class of acyclic NFAs that characterize the class of finite languages. A tight state complexity bound for determinizing acyclic NFAs is known [START_REF] Salomaa | NFA to DFA Transformation For Finite Languages over Arbitrary Alphabets[END_REF]. From Corollary 3 we know that determinizing a nearly acyclic NFA always results in a nearly acyclic DFA. Establishing the worstcase size blow-up of determinizing a nearly acyclic NFA is a topic for future research. The size blow-up is at least as great as the exponential lower bound for determinizing unary (nearly acyclic) NFAs having cycles of different prime lengths [START_REF] Chrobak | Finite Automata and Unary Languages[END_REF].

Minimization of NFAs is PSPACE-complete [START_REF] Holzer | Descriptional and Computational Complexity of Finite Automata -A Survey[END_REF] and remains NP-hard even for restricted subclasses of acyclic NFAs [START_REF] Björklund | The Tractability Frontier for NFA Minimization[END_REF]. A linear time minimization algorithm for acyclic DFAs is given by Bubenzer [START_REF] Bubenzer | Cycle-Aware Minimization of Acyclic Deterministic Finite-State Automata[END_REF] and incremental minimization techniques for acyclic NFAs have been considered e.g. by Lamperti et al. [START_REF] Lamperti | Determinization and minimization of finite acyclic automata by incremental techniques[END_REF]. A topic for future work could be also to extend such methods for nearly acyclic NFAs.

5 |Q| 2 •

 52 (i) In time O(|Q| 6 • |Σ|), a random-access-machine can decide whether or not SPW sup (A) is finite, and in the positive case, SPW sup (A) ≤ |Q| |Q| . (ii) The growth rate of SPW(A, ) is either bounded by a constant, polynomial in , or exponential in . If the growth rate is polynomial, the degree of the polynomial can be decided in O(|Q| 6 • |Σ|) time. (iii) It can be decided in O(|Q| 4 • |Σ|) time whether or not the growth rate of SPW(A, ) is exponential.

Fig. 2 .

 2 Fig. 2. DFA A2

Theorem 2 .

 2 If A is an NFA with m states over an alphabet Σ, we can decide in time O(|Σ| • m 5 ) whether or not the depth path width of A is infinite. Proof. Algorithm 1 checks the conditions of Theorem 1. Creating the copy of Algorithm 1 Deciding if an NFA has infinite depth path width 1: Let A = (Q, Σ, δ, q0, F ) be an NFA where |Q| = m. 2: Create a copy of A and call it A , where all states of A are final.

Proposition 1 .

 1 Let A be an m-state unary aNFA. Then DPW sup (A) ≤ m-1 m-1 2

Lemma 5 .Fig. 3 .

 53 Fig. 3. An m-state imax-naNFA with alphabet {c1, . . . , c k }.

Theorem 4 .

 4 For m ∈ N, there exists an m-state nearly acyclic DFA over a k-letter alphabet having depth path width k m-1 .

Lemma 7 .Theorem 5 .

 75 Let A be an m-state imax-naNFA over alphabet Σ and let B be an m-state naNFA over Σ where all cycles are self-loops. Then DPW sup (B) ≤ DPW sup (A). Now we get a tight upper bound for the depth path width of an m-state naNFA. If A is an m-state naNFA over a k-letter alphabet, then DPW sup (A) ≤ (k + 1) m-1 . For each m, k ≥ 1, there exists an m-state naNFA B imax over a kletter alphabet such that DPW sup (B imax ) = (k + 1) m-1 .

Note that this is not the same as the graph theory notion of tree width.

Here and in the title of the paper by "branching" we mean an informal notion of path expansion in computations. A specific technical notion called branching is considered by Goldstine et al.[START_REF] Goldstine | On Measuring Nondeterminism in Regular Languages[END_REF].

This is a conservative upper bound chosen to keep the argument simple. If A were to have m cycles, the length of the cycles naturally could not be m.

Acknowledgments

Research supported by NSERC grant OGP0147224. Full version of the work can be found in [12].


Kitti Gelle
email: kgelle@inf.u-szeged.hu

Szabolcs Iván

Recognizing Union-Find trees built up using union-by-rank strategy is NP-complete

Disjoint-Set forests, consisting of Union-Find trees, are data structures having a widespread practical application due to their efficiency. Despite them being well-known, no exact structural characterization of these trees is known (such a characterization exists for Union trees which are constructed without using path compression) for the case assuming union-by-rank strategy for merging. In this paper we provide such a characterization by means of a simple push operation and show that the decision problem whether a given tree (along with the rank info of its nodes) is a Union-Find tree is NP-complete, complementing our earlier similar result for the union-by-size strategy.

Introduction

Disjoint-Set forests, introduced in [START_REF] Galler | An improved equivalence algorithm[END_REF], are fundamental data structures in many practical algorithms where one has to maintain a partition of some set, which supports three operations: creating a partition consisting of singletons, querying whether two given elements are in the same class of the partition (or equivalently: finding a representative of a class, given an element of it) and merging two classes. Practical examples include e.g. building a minimum-cost spanning tree of a weighted graph [START_REF] Thomas | Introduction to Algorithms[END_REF], unification algorithms [START_REF] Knight | Unification: A multidisciplinary survey[END_REF] etc.

To support these operations, even a linked list representation suffices but to achieve an almost-constant amortized time cost per operation, Disjoint-Set forests are used in practice. In this data structure, sets are represented as directed trees with the edges directed towards the root; the create operation creates n trees having one node each (here n stands for the number of the elements in the universe), the find operation takes a node and returns the root of the tree in which the node is present (thus the same-class(x, y) operation is implemented as find(x) == find(y)), and the merge(x, y) operation is implemented by merging the trees containing x and y, i.e. making one of the root nodes to be a child of the other root node (if the two nodes are in different classes).

In order to achieve near-constant efficiency, one has to keep the (average) height of the trees small. There are two "orthogonal" methods to do that: first, during the merge operation it is advisable to attach the "smaller" tree below the "larger" one. If the "size" of a tree is the number of its nodes, we say the trees are built up according to the union-by-size strategy, if it's the depth of a tree, then we talk about the union-by-rank strategy. Second, during a find operation invoked on some node x of a tree, one can apply the path compression method, which reattaches each ancestor of x directly to the root of the tree in which they are present. If one applies both the path compression method and either one of the union-by-size or union-by-rank strategies, then any sequence of m operations on a universe of n elements has worst-case time cost O(mα(n)) where α is the inverse of the extremely fast growing (not primitive recursive) Ackermann function for which α(n) ≤ 5 for each practical value of n (say, below 2 65535 ), hence it has an amortized almost-constant time cost [START_REF] Endre | Efficiency of a good but not linear set union algorithm[END_REF]. Since it's proven [START_REF] Fredman | The cell probe complexity of dynamic data structures[END_REF] that any data structure maintaining a partition has worst-case time cost Ω(mα(n)), the Disjoint-Set forests equipped with a strategy and path compression offer a theoretically optimal data structure which performs exceptionally well also in practice. For more details see standard textbooks on data structures, e.g. [START_REF] Thomas | Introduction to Algorithms[END_REF].

Due to these facts, it is certainly interesting both from the theoretical as well as the practical point of view to characterize those trees that can arise from a forest of singletons after a number of merge and find operations, which we call Union-Find trees in this paper. One could e.g. test Disjoint-Set implementations since if at any given point of execution a tree of a Disjoint-Set forest is not a valid Union-Find tree, then it is certain that there is a bug in the implementation of the data structure (though we note at this point that this data structure is sometimes regarded as one of the "primitive" data structures, in the sense that it is possible to implement a correct version of them that needs not be certifying [START_REF] Mcconnell | Certifying algorithms[END_REF]). Nevertheless, only the characterization of Union trees is known up till now [START_REF] Cai | The recognition of Union trees[END_REF], i.e. which correspond to the case when one uses one of the unionby-strategies but not path compression. Since in that case the data structure offers only a theoretic bound of Θ(log n) on the amortized time cost, in practice all implementations imbue path compression as well, so for a characterization to be really useful, it has to cover this case as well.

In this paper we show that the recognition problem of Union-Find trees is NP-complete when the union-by-rank strategy is used, complementing our earlier results [START_REF] Gelle | Recognizing Union-Find trees is NP-complete[END_REF] where we proved NP-completeness for the union-by-size strategy. The proof method applied here resembles to that one, but the low-level details for the reduction (here we use the Partition problem, there we used the more restricted version 3-Partition as this is a very canonical strongly NP-complete problem) differ greatly. This result also confirms the statement from [START_REF] Cai | The recognition of Union trees[END_REF] that the problem "seems to be much harder" than recognizing Union trees. As (up to our knowledge) in most of the actual software libraries having this data structure implemented the union-by-rank strategy is used (apart from the cases when one quickly has to query the size of the sets as well), for software testing purposes the current result is more relevant than the one applying union-by-size strategy.

Related work.

There is an increasing interest in determining the complexity of the recognition problem of various data structures. The problem was considered for suffix trees [START_REF] Tomohiro | Inferring strings from suffix trees and links on a binary alphabet[END_REF][START_REF] Starikovskaya | A suffix tree or not a suffix tree?[END_REF], (parametrized) border arrays [START_REF] Tomohiro | Verifying and enumerating parameterized border arrays[END_REF][START_REF] Lu | Verifying a border array in linear time[END_REF][START_REF] Duval | Border array on bounded alphabet[END_REF][START_REF] Tomohiro | Counting parameterized border arrays for a binary alphabet[END_REF][START_REF] Tomohiro | Verifying and enumerating parameterized border arrays[END_REF], suffix arrays [START_REF] Bannai | Inferring strings from graphs and arrays[END_REF][START_REF] Duval | Words over an ordered alphabet and suffix permutations[END_REF][START_REF] Kucherov | On the combinatorics of suffix arrays[END_REF], KMP tables [START_REF] Duval | Efficient validation and construction of border arrays and validation of string matching automata[END_REF][START_REF] Gawrychowski | Validating the Knuth-Morris-Pratt failure function, fast and online[END_REF], prefix tables [START_REF] Clément | Reverse engineering prefix tables[END_REF], cover arrays [START_REF] Crochemore | Cover array string reconstruction[END_REF], and directed acyclic word-and subsequence graphs [START_REF] Bannai | Inferring strings from graphs and arrays[END_REF].

Notation

A (ranked) tree is a tuple t = (V t , root t , rank t , parent t ) with V t being the finite set of its nodes, root t ∈ V t its root, rank t : V t → N 0 mapping a nonnegative integer to each node, and parent t : (V t -{root t }) → V t mapping each nonroot node to its parent (so that the graph of parent t is a directed acyclic graph, with edges being directed towards the root). We require rank t (x) < rank t (parent t (x)) for each nonroot node x, i.e. the rank strictly decreases towards the leaves.

For a tree t and a node x ∈ V t , let children(t, x) stand for the set {y ∈ V t : parent t (y) = x} of its children and children(t) stand as a shorthand for children(t, root t ), the set of depth-one nodes of t. Also, let x t y denote that x is a (non-strict) ancestor of y in t, i.e. x = parent k t (y) for some k ≥ 0. For x ∈ V t , let t| x stand for the subtree (V x = {y ∈ V : x t y}, x, rank t | Vx , parent t | Vx ) of t rooted at x. As shorthand, let rank(t) stand for rank t (root t ), the rank of the root of t.

Two operations on trees are that of merging and collapsing. Given two trees t = (V t , root t , rank t , parent t ) and s = (V s , root s , rank s , parent s ) with V t and V s being disjoint and rank(t) ≥ rank(s), then their merge merge(t, s) (in this order) is the tree (V t ∪ V s , root t , rank, parent) with parent(x) = parent t (x) for x ∈ V t , parent(root s ) = root t and parent(y) = parent s (y) for each nonroot node y ∈ V s of s, and

rank(root t ) = rank(t) if rank(s) < rank(t), rank(t) + 1 otherwise, and rank(x) = rank t (x), rank s (x) resp. for each x ∈ V t -{root r }, x ∈ V s resp.
Given a tree t = (V, root, rank, parent) and a node x ∈ V , then collapse(t, x) is the tree (V, root, rank, parent ) with parent (y) = root if y is a nonroot ancestor of x in t and parent (y) = parent(y) otherwise. For examples, see Figure 1.

Observe that both operations indeed construct a ranked tree (e.g. the rank remains strictly decreasing towards the leaves).

We say that a tree is a singleton tree if it has exactly one node, and this node has rank 0.

The class of Union trees is the least class of trees satisfying the following two conditions: every singleton tree is a Union tree, and if t and s are Union trees with rank(t) ≥ rank(s), then merge(t, s) is a Union tree as well.

Analogously, the class of Union-Find trees is the least class of trees satisfying the following three conditions: every singleton tree is a Union-Find tree, if t and

s: r 2 1 1 1 1 0 0 0 0 x z t: 0 0 2 y (a) Trees s and t r 3 1 1 1 1 0 0 0 0 x z 0 0 2 y (b) t = merge(s, t) r 3 1 1 1 1 0 0 0 0 x z 0 0 2 y (c) t = push(t , x, y) r 3 1 1 1 1 0 0 0 0 x z 0 0 2 y (d) t = collapse(t , z)
Fig. 1: Merge, collapse and push.

s are Union-Find trees with rank(t) ≥ rank(s), then merge(t, s) is a Union-Find tree as well, and if t is a Union-Find tree and x ∈ V t is a node of t, then collapse(t, x) is also a Union-Find tree. We say that a node x of a tree t satisfies the Union condition if

{rank t (y) : y ∈ children(t, x)} = {0, 1, . . . , rank t (x) -1}.
Then, the characterization of Union trees from [START_REF] Cai | The recognition of Union trees[END_REF] can be formulated in our terms as follows: Theorem 1. A tree t is a Union tree if and only if each node of t satisfies the Union condition.

Note that the rank of a Union tree always coincides by its height. (And, any subtree of a Union tree is also a Union tree.) In particular, the leaves are exactly those nodes of rank 0.

Structural characterization of Union-Find trees

Suppose s and t are trees on the same set V of nodes, with the same root root and the same rank function rank. We write s t if x s y implies x t y for each x, y ∈ V .

Clearly, is a partial order on any set of trees (i.e. is a reflexive, transitive and antisymmetric relation). It is also clear that s t if and only if parent s (x) t x holds for each x ∈ V -{root} which is further equivalent to requiring parent s (x) t parent t (x) since parent s (x) cannot be x.

Another notion we define is the (partial) operation push on trees as follows: when t is a tree and x = y ∈ V t are siblings in t, i.e. have the same parent, and rank t (x) < rank t (y), then push(t, x, y) is defined as the tree (V t , root t , rank t , parent ) with

parent (z) = y if z = x, parent t (z) otherwise,
that is, we "push" the node x one level deeper in the tree just below its former sibling y. (See Figure 1.) We write t t when t = push(t, x, y) for some x and y, and as usual, * denotes the reflexive-transitive closure of . Proposition 1. For any pair s and t of trees, the following conditions are equivalent: (i) s t, (ii) there exists a sequence t 0 = s, t 1 , t 2 , . . . , t n of trees such that for each i = 1, . . . , n we have t i = push(t i-1 , x, y) for some depth-one node x ∈ children(t i-1 ), moreover, children(t n ) = children(t) and t n | x t| x for each x ∈ children(t), (iii) s * t.

Proof. i)⇒ii). It is clear that

is equality on singleton trees, thus implies * for trees of rank 0. Assume s t for the trees s = (V, root, rank, parent) and t = (V, root, rank, parent ) and let X stand for the set children(s) of the depth-one nodes of s and Y stand for children(t). Clearly, Y ⊆ X since by s t, any node x of s having depth at least two has to satisfy parent(x) t parent (x) and since parent(x) = root for such nodes, x has to have depth at least two in t as well. Now there are two cases: either root = parent(x) = parent (x) for each x ∈ X, or parent(x) ≺ t parent (x) for some x ∈ X.

If parent (x) = root for each x ∈ X, then X = Y and we only have to show that s| x t| x for each x ∈ X. For this, let u, v ∈ V (s| x ) with u s|x v. Since s| x is a subtree of s, this holds if and only if x s u s v. From s t this implies x t u t v, that is, u t|x v, hence s| x t| x . Now assume parent(x) ≺ t parent (x) for some x ∈ X. Then parent (x) = root, thus there exists some y ∈ Y with y t parent (x). By Y ⊆ X, this y is a member of X as well, and rank s (y) = rank t (y) > rank t (x) = rank s (x), thus s = push(s, x, y) is well-defined. Moreover, s t since parent s (z) t z for each z ∈ V : either z = x in which case parent s (z) = parent(z) t z by s t, or z = x and then parent s (z) = y t parent (x) t x = z also holds. Thus, there exists a tree s = push(s, x, y) for some x ∈ children(s) with s t; since children(s ) = X -{x}, by repeating this construction we eventually arrive to a tree t n with |children(t

n )| = |Y |, implying children(t n ) = Y by Y ⊆ children(t n ).
ii)⇒iii). We apply induction on rank(s) = rank(t). When rank(s) = 0, then s is a singleton tree and the condition in ii) ensures that t is a singleton tree as well. Thus, s = t and clearly s * t.

Now let assume the claim holds for each pair of trees of rank less than rank(s) and let t 0 , . . . , t n be trees satisfying the condition. Then, by construction, s * t n . Since rank(t n | x ) < rank(t n ) = rank(s) for each node x ∈ children(t n ), by t n | x t| x we get applying the induction hypothesis that t n | x * t| x for each depth-one node x of t n , thus t n * t, hence s * t as well. iii)⇒ i). For * implying it suffices to show that implies since the latter is reflexive and transitive. So let s = (V, r, rank, parent) and x = y ∈ V be siblings in s with the common parent z, rank(x) < rank(y) and let t = push(s, x, y). Then, since parent s (x) = z = parent t (y) = parent t (parent t (x)), we get parent s (x) t x, and by parent s (w) = parent t (w) for each node w = x, we have s t.

The relations and * are introduced due to their intimate relation to Union-Find and Union trees (similarly to the case of the union-by-size strategy [START_REF] Gelle | Recognizing Union-Find trees is NP-complete[END_REF], but there the push operation itself was slightly different): Theorem 2. A tree t is a Union-Find tree if and only if t * s for some Union tree s.

Proof. Let t be a Union-Find tree. We show the claim by structural induction. For singleton trees the claim holds since any singleton tree is a Union tree as well. Suppose t = merge(t 1 , t 2 ). Then by the induction hypothesis, t 1 * s 1 and t 2 * s 2 for the Union trees s 1 and s 2 . Then, for the tree s = merge(s 1 , s 2 ) we get that t * s. Finally, assume t = collapse(t , x) for some node x. Let x = x 1 x 2 . . . x k = root t be the ancestral sequence of x in t . Then, defining t 0 = t, t i = push(t i-1 , x i , x i+1 ) we get that t * t k-2 = t and t * s for some Union tree s applying the induction hypothesis, thus t * s also holds. Now assume t * s (equivalently, t s) for some Union tree s. We show the claim by induction on the height of t. For singleton trees the claim holds since any singleton tree is a Union-Find tree. Now assume t = (V, root, rank, parent) is a tree and t * s for some Union tree s. Then by Proposition 1, there is a set X = children(s) ⊆ children(t) of depth-one nodes of t and a function f : Y → X with Y = {y 1 , . . . , y } = children(t) -X such that for the sequence t 0 = t, t i = push(t i-1 , y i , f (y i )) we have that t | x s| x for each x ∈ X. As each s| x is a Union tree (since so is s), we have by the induction hypothesis that each t | x is a Union-Find tree. Now let X = {x 1 , . . . , x k } be ordered nondecreasingly by rank; then, as s is a Union tree and X = children(s), we get that {rank(x i )} = {0, 1, . . . , rank(root) -1} by Theorem 1. Hence for the sequence t i defined as t 0 being a singleton tree with root root and for each i ∈ {1, . . . , k}, t i = merge(t i-1 , t | xi ), we get that t = t k is a Union-Find tree. Finally, we get t from t by applying successively one collapse operaton on each node in Y , thus t is a Union-Find tree as well.

Complexity

In order to show NP-completeness of the recognition problem, we first make a useful observation.

Proposition 2. In any Union-Find tree t there are at least as many rank-0 nodes as nodes of positive rank.

Proof. We apply induction on the structure of t. The claim holds for singleton trees (having one single node of rank 0). Let t = merge(t 1 , t 2 ) and suppose the claim holds for t 1 and t 2 . There are two cases.

-Assume rank(t 1 ) = 0. Then, since rank(t 1 ) ≥ rank(t 2 ) we have that rank(t 2 ) is 0 as well, i.e. both t 1 and t 2 are singleton trees (of rank 0). In this case t has one node of rank 1 and one node of rank 0. -If rank(t 1 ) > 0, then (since root t1 is the only node in V t = V t1 ∪ V t2 whose rank can change at all, in which case it increases) neither the total number of rank-0 nodes nor the total number of nodes with positive rank changes, thus the claim holds.

Let t = collapse(s, x) and assume the claim holds for s. Then, since the collapse operation does not change the rank of any of the nodes, the claim holds for t as well.

In order to define a reduction from the strongly NP-complete problem Partition we introduce several notions on trees:

An apple of weight a for an integer a > 0 is a tree consisting of a root node of rank 2, a depth-one node of rank 0 and a depth-one nodes of rank 1.

A basket of size H for an integer H > 0 is a tree consisting of H +4 nodes: the root node having rank 3, H + 1 depth-one children of rank 0 and one depth-one child of rank 1, which in turn has a child of rank 0.

A flat tree is a tree t of the following form: the root of t has rank 4. The immediate subtrees of t are:

a node of rank 0, having no children; a node of rank 1, having a single child of rank 0; a node of rank 2, having two children: a single node of rank 0 and a node of rank 1, having a single child of rank 0; an arbitrary number of apples, and an arbitrary number of baskets for some fixed size H. (See Figure 2.) At this point we recall that the following problem Partition is NP-complete in the strong sense [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]: given a list a 1 , . . . , a m of positive integers and a value k > 0 such that the value B = m i=1 ai k is an integer, does there exist a partition B = {B 1 , . . . , B k } of the set {1, . . . , m} satisfying i∈Bj a i = B for each 1 ≤ j ≤ k?

(Here "in the strong sense" means that the problem remains NP-complete even if the numbers are encoded in unary.) Proposition 3. Assume t is a flat tree having k basket children, each having the size H, and m apple children of weights a 1 , . . . , a m respectively, satisfying

H • k = 1≤i≤m a i .
Then t is a Union-Find tree if and only if the instance (a 1 , . . . , a m , k) is a positive instance of the Partition problem.

Proof. (For an example, the reader is referred to Figure 3.) Suppose I = (a 1 , . . . , a m , k) is a positive instance of the Partition problem. Let H stand for the target sum ai k . Let B = {B 1 , . . . , B k } be a solution of I, i.e., i∈Bj a i = H for each j = 1, . . . , k. Let x 1 , . . . , x k ∈ children(t) be the nodes corresponding to the baskets of t and let y 1 , . . . , y m ∈ children(t) be the nodes corresponding to the apples of t.

We define the following sequence t 0 , t 1 , . . . , t m of trees: t 0 = t and for each i = 1, . . . , m, let t i = push(t i-1 , y i , x j ) with 1 ≤ j ≤ k being the unique index with i ∈ B j . Then, children(t m ) consists of x 1 , . . . , x k and the three additional nodes having rank 0, 1 and 2. Note that the subtrees rooted at the latter three nodes are Union trees. Thus, if each of the trees t m | xj is a Union-Find tree, then so is t.

Consider a subtree t = t m | xj . By construction, t is a tree whose root has rank 3 and has -H + 1 children of rank 0, a single child of rank 1, having a child of rank 0, and several (say, ) apple children with total weight H.

We give a method to transform t into a Union tree. First, we push a i rank-0 nodes to each apple child of weight a i . After this stage t has one child of rank 0, one child of rank 1 and "filled" apple children, having a root of rank 2, thus the root of the transformed t satisfies the Union condition. We only have to show that each of these "filled" apples is a Union-Find tree.

Such a subtree has a root node of rank 2, a i depth-one nodes of rank 1 and a i + 1 depth-one nodes of rank 0. Then, one can push into each node of rank 1 a node of rank 0 and arrive to a tree with one depth-one node of rank 0, and a i depth-one nodes of rank 1, each having a single child of rank 0, which is indeed a Union tree, showing the claim by Theorem 2.

For an illustration of the construction the reader is referred to Figure 4.

For the other direction, suppose t is a Union-Find tree. By Theorem 2 and Proposition 1, there is a subset X ⊆ children(t) and a mapping f : Y → X with Y = {y 1 , . . . , y } = children(t) -X such that for the sequence t 0 = t, t i = push(t i-1 , y i , f (y i )) we have that each immediate subtree of t is a Union-Find tree and moreover, the root of t satisfies the Union condition.

The root of t has rank 4, t has to have at least one child having rank 0, 1, 2 and 3 respectively. Since t has exactly one child with rank 0 and rank 1, these nodes has to be in X. This implies that no node gets pushed into the apples at this stage (because the apples have rank 2). Thus, since the apples are not Union-Find trees (as they have strictly less rank-0 nodes than positive-rank nodes, cf. Proposition 2), all the apples have to be in Y . Apart from the apples, t has exactly one depth-one node of rank 2 (which happens to be a root of a Union tree), thus this node has to stay in X as well. Moreover, we cannot push the baskets as they have the maximal rank 3, hence they cannot be pushed.

Thus, we have to push all the apples, and we can push apples only into baskets (as exactly the baskets have rank greater than 2). Let x ∈ X be a basket node, let t stand for t | x and let {y 1 , . . . , y j } ⊆ Y be the set of those apples that get pushed into x during the operation. Then, the total number of nodes having rank 0 in t is H + 2 + j (j of them coming from the apples and the other ones coming from the basket) while the total number of nodes having a positive rank is 2 + j + A where A is the total weight of the apples in {y 1 , . . . , y j }. Applying Proof. By Proposition 3 we get NP-hardness. For membership in NP, we make use of the characterization given in Theorem 2 and that the possible number of pushes is bounded above by n 2 : upon pushing x below y, the depth of x and its descendants increases, while the depth of the other nodes remains the same. Since the depth of any node is at most n, the sum of the depths of all the nodes is at most n 2 in any tree. Hence, it suffices to guess nondeterministically a sequence t = t 0 t 1 . . . t k for some k ≤ n 2 with t k being a Union tree (which also can be checked in polynomial time).

Conclusion, future directions

We have shown that unless P = NP, there is no efficient algorithm to check whether a given tree is a valid Union-Find tree, assuming union-by-rank strategy, since the problem is NP-complete, complementing our earlier results assuming union-by-size strategy. A very natural question is the following: does there exist a merging strategy under which the time complexity remains amortized almost-constant, and at the same time allows an efficient recognition algorithm? Although this data structure is called "primitive" in the sense that it does not really need an automatic run-time certifying system, but we find the question to be also interesting from the mathematical point of view as well. It would be also an interesting question whether the recognition problem of Union-Find trees built up according to the union-by-rank strategy is still NP-complete if the nodes of the tree are not tagged with the rank, that is, given a tree without rank info, does there exist a Union-Find tree with the same underlying tree?

Fig. 2 :

 2 Fig. 2: A flat tree.

Fig. 3 :

 3 Fig. 3: The initial flat tree t corresponding to the Partition instance (1, 2, 3, 4, 4, k = 2). The size of each basket is (1 + 2 + 3 + 4 + 4)/k = 7.

  Apples of size 3 and 4 are pushed into the first basket, apples of size 1, 2 and 4 are pushed into the second basket.

  The apples get filled from the baskets' surplus rank-0 leaves.

  The filling of the apples is pushed a level deeper and we have a Union tree.

Fig. 4 :Theorem 3 .

 43 Fig. 4: Pushing t of Figure 3 into a Union tree according to the solution 3 + 4 = 1 + 2 + 4 of the Partition instance.

Research was supported by the NKFI grant no. 108448.


Jürgen Dassow
email: dassow@iws.cs.uni-magdeburg.de

Descriptional Complexity and Operations -Two Non-Classical Cases

For a language family L, a syntactic complexity measure K defined on languages of L, a number n ≥ 1, and an n-ary operation • under which L is closed, we define g K • (m1, m2, . . . , mn) as the set of all integers r such that there are n languages Li, 1 ≤ i ≤ n, with

In this paper we study these sets for the operation union, catenation, star, complement, set-subtraction, and intersection and the measure number of accepting states (defined for regular languages) as well as for reversal, union, catenation, and star and the measures number of nonterminals, productions, and symbols (defined for context-free languages). Moreover, we discuss the change of these sets if one restricts to finite languages, unary languages, and finite unary languages.

Introduction

The state complexity sc(L) of a regular language L is defined as the minimal number of states that are sufficient and necessary for a deterministic finite automaton to accept L. The study of the state complexity of regular languages is a central topic in theoretical computer science, but it has also large importance in applied fields. The first important results by Lupanov, Moore, Meyer, Fischer and others date back to the sixties and seventies, i. e., to the beginning of theoretical computer science.

In the last three decades the following problem was intensively investigated: Given a binary regularity preserving operation • and two numbers m and n, determine the maximal number k (denoted by f sc • (m, n)) such that there are languages L m and L n with sc(L m ) = m, sc(L n ) = n and sc(L m • L n ) = k (we have introduced the concept for binary operations, but the concept can be used for unary, ternary etc. operations as well). Summaries on the study of f sc

• can be found in the papers [START_REF] Yu | State complexity of regular languages[END_REF] and [START_REF] Gao | A review on state complexity of individual operations[END_REF].

As for other problems concerning the state complexity, one has noticed that the behaviour of the complexity under operations can considerably change if one restricts to finite or unary or finite unary languages. This can be seen from the following table. We mention that there are also many papers where other subfamilies of the family of regular languages have been studied, e. g., star-free languages, unionfree languages, languages closed under certain subword operations. Examples for such results can be found in [START_REF] Han | State complexity of basic operations on suffix-free regular languages[END_REF] and [START_REF] Jirásková | Complexity in prefix-free regular languages[END_REF].

There are also some results where instead of the maximal number f sc

• the set g sc

• of all numbers k such that there are languages L m and L n with sc(L m ) = m, sc(L n ) = n, and sc(L m • L n ) = k is determined. We mention here three such results.

-Complement:

g sc C (m) = {m} for m ≥ 1, -Union: ([20]) g sc ∪ (m, n) = {1, 2, . . . , mn} for m ≥ 2 and n ≥ 2 -Kleene star: ([21]) g sc * (m) = {1, 2} for m = 1 {1, 2, . . . , 2 m-1 + 2 m-2 } for m ≥ 2 .
Obviously, the problem of the behaviour of syntactic measures of complexity under operations can be discussed in other cases, too, where one can change the complexity measure and/or the considered type of automaton. We mention here the following approaches.

The most natural extension of deterministic finite automata are nondeterministic finite automata. The operational behaviour of the (nondeterministic) state complexity is studied in [START_REF] Holzer | State complexity of basic operations on nondeterministic automata[END_REF] and summarized in [START_REF] Holzer | nondeterministic finite automata -recent results on the descriptional and computational complexity[END_REF].

The number of transitions is not of interest for complete deterministic finite automata, but the situation changes if one allows incomplete finite automata. In the papers [START_REF] Gao | Transition complexity of incomplete dfas[END_REF] and [START_REF] Maia | Incomplete operational transition complexity of regular languages[END_REF], one can find results on the behaviour of the number of transitions under operations.

In order to cover XML structures one has to extend usual finite automata and comes to nested word automata or visibly pushdown automata or input-driven pushdown automata. The state complexity of these automata under operations is studied in the papers [START_REF] Alur | Visibly pushdown languages[END_REF], [START_REF] Piao | Operational state complexity of nested word automata[END_REF], and [START_REF] Okhotin | State complexity of operations on input-driven pushdown automata[END_REF].

Another natural extension of finite automata over strings is given by tree automata. There are also some results for their operational state complexity (see [START_REF] Piao | State complexity of the concatenation of regular tree automata[END_REF] and [START_REF] Piao | State complexity of projection and quotient of unranked trees[END_REF]).

In this paper we summarize results on the behaviour of some further nonclassical measures of descriptional complexity under operations.

First we consider the number of accepting states instead of the number of (all) states. For a regular language L, the number asc(L) is defined as the minimal number of accepting states that are sufficient and necessary for a deterministic finite automaton to accept L. We mention two points of interest in this measure:

-It was shown that, for two languages L m and L n with sc(L m ) = m and sc(

L n ) = n, the relation sc(L m • L n ) ≤ m2 n -asc(L m ) • 2 n-1 holds for
m ≥ 2 and n ≥ 1, and that the bound is optimal. For the Kleene-closure and the cut-operation, the complexity of the resulting language also depends on the number of accepting states (see [START_REF] Gao | A review on state complexity of individual operations[END_REF] and [START_REF] Drewes | Tight bounds for cutoperations on deterministic finite automata[END_REF]). -The complexity of algorithms for the minimization of Büchi automata and for model checking based on Büchi automata depend on the number of accepting states of the Büchi automaton (see [START_REF] Champarnaud | Büchi automata reduction by means of left and right trace inclusion preorder[END_REF] and [START_REF] Edelkamp | Large scale directed model checking LTL[END_REF]). We determine the sets g asc

•

for union, complement, set-subtraction, Kleene star, catenation, and intersection. Furthermore, we discuss variants of g asc • where we restrict the sets L m and L n to be finite sets or regular unary sets and or finite unary sets. The comparison shows that, for most operations, the situation is similar for arbitrary regular, finite sets, and regular unary sets, whereas finite unary sets show a completely different behaviour.

Some of these results were already published in [START_REF] Dassow | On the number of accepting states of finite automata[END_REF].

Furthermore, we consider context-free languages and define their syntactic complexity as the minimal number of nonterminals or productions or symbols which is necessary to generate the language by context-free grammars. These measures were introduced and studied by Gruska in [START_REF] Gruska | Some Classifications of Context-Free Languages[END_REF] and [START_REF] Gruska | On the Size of Context free Grammars[END_REF]. We summarize some results obtained in cooperation with Ralf Stiebe and Ronny Harbich (see [START_REF] Dassow | Nonterminal complexity of some operations on context-free languages[END_REF], [START_REF] Dassow | Descriptional complexity of union and star on contextfree languages[END_REF], and [START_REF] Harbich | Regel-und Symbolkomplexität kontextfreier Sprachen unter ausgewählten Operationen[END_REF]) for the operational behaviour of these measures for arbitrary context-free languages under reversal, union, catenation, and star. Moreover, we add results for the case of finite, unary context-free, and finite unary languages. For the number of variables, there is a large difference which comes from the fact that the complexity for finite and unary context-free languages is bounded by one or two. For the number of productions, it seems that the difference between arbitrary and finite sets is essentially that we miss one or two "large" values.

Definitions and Notations

We assume that the reader is familiar with the basic notions of theory of automata and formal languages; for details we refer to [START_REF]Handbook of Formal Languages[END_REF]. Essentially, we give some notations and define the complexity measures of regular and context-free languages which are considered in this paper.

By card(M ), we denote the cardinality of a set M . The empty word is denoted by λ. By N, we denote the set of all positive integers. If L is a language, then we define the complement C(L) of L as the set of all words w ∈ V * which are not contained in L, where V is the minimal set (with respect to inclusion) with L ⊆ V * .

We specify a (deterministic) finite automaton as a tuple A = (Q, X, q 0 , F, δ) where Q and X are finite sets of states and inputs, respectively, q 0 ∈ Q is a distinguished state (the initial state), F is a subset of Q (the set of accepting states), and δ is a function from Q × X into Q. The language accepted by A is denoted by L(A).

For a finite automaton A = (Q, X, q 0 , F, δ) and a regular language L, we set

asc(A) = card(F ), asc(L) = min{asc(A) | L(A) = L}.
A context-free grammar is specified as a quadruple G = (N, T, P, S) where N and T are two finite and disjoint sets, P is a finite subset of N × (v ∪ N ) * , and S is a distinguished element of N . The elements of N , T , and P are called nonterminals, terminals, and productions, respectively, and S is called the axiom. We write A → w instead of (A, w) ∈ P . By L(G), we denote the language generated by G.

For a context-free grammar G = (N, T, P, S), we set

Var(G) = card(N ), Prod(G) = card(P ), and
Symb(G) = A→w∈P (|w| + 2).
Let K ∈ {Var, Prod, Symb}. For a context-free language L, we set

K(L) = min{K(G) | L(G) = L}.
For a language family L, a syntactic complexity measure K defined on languages of L, a number n ≥ 1, and an n-ary operation • under which L is closed, we define g K

• (m 1 , m 2 , . . . , m n ) as the set of all integers r such that there are

n languages L i , 1 ≤ i ≤ n, with K(L i ) = m i for 1 ≤ i ≤ n and K(•(L 1 , L 2 , . . . , L n )) = r.
If we additional require that the languages L i , 1 ≤ i ≤ n, are finite or unary or finite unary, we use the notations g K,f

• (m 1 , m 2 , . . . , m n ), g K,u • (m 1 , m 2 , . . . , m n ), and g K,f,u • (m 1 , m 2 , . . . , m n ).

Number of Accepting States

In this section we only consider regular languages; therefore we omit the adjective "regular".

With respect to the measure number of accepting states, we consider the operations complement, union, set-substraction, catenation, star, and intersection.

We start with complement.

Theorem 1. The following relations hold for the operation complement:

g asc C (m) = g asc,u C    {1} for m = 0 {0} ∪ N for m = 1 N for m ≥ 2 g asc,f C (m) = g asc,f,u C (m) = {1} for m ∈ {0} N for m ≥ 2 .
We see that the only difference is that 0 is not in g asc,f

C

(1) and not in g asc,f,u C (1). This difference comes from the following observations: asc(∅) = 0 holds, and asc(L) ≥ 1 iff L is not empty.

-the complement of the empty set is the non-finite set V * of all words (and asc(V * ) = 1). We now give the results for union, set-subtraction, and star and compare them afterwards.

Theorem 2. The following relations hold for the operation union:

g asc ∪ (m, n) = g asc,u ∪ (m, n) =    {m} for n = 0, m ≥ 0 {n} for m = 0, n ≥ 0 N for m ≥ 1, n ≥ 1 , g asc,f ∪ (m, n) =        {m} for n = 0, m ≥ 0 {n} for m = 0, n ≥ 0 N for m = n = 1 N \ {1} for m ≥ 1, n ≥ 1, m + n ≥ 3 , g asc,f,u ∪ (m, n) = {max{m, n}, max{m, n} + 1, . . . , m + n}.
Theorem 3. The following relations hold for the operation set-subtraction:

g asc \ (m, n) = g asc,u \ =    {0} for m = 0, n ≥ 0 {m} for n = 0, m ≥ 0 N ∪ {0} for m ≥ 1, n ≥ 1 , g asc,f \ (m, n) =        {0} for m = 0, n ≥ 0 {m} for n = 0, m ≥ 0 {0, 1} for m = 1, n ≥ 1, N ∪ {0} for m ≥ 2, n ≥ 1 , g asc,f,u \ (m, n) = {m, m -1, . . . , m -n}.
Theorem 4. The following relations hold for the operation star:

g asc * (m) = g asc,u * (m) = {1} for m = 0 N for m ≥ 1 , g asc,f * (m) = g asc,f,u * (m) = {1} for m ∈ {0, 1} N for m ≥ 2 .
First we mention that, for all these three operations union, set-subtraction, and star, there is no difference between the situations for arbitrary sets and arbitrary unary sets.

Moreover, for all these three operations, a difference between allowing arbitrary sets and restricting to finite sets only occurs for m = 1. In all cases, essentially, it comes from the following lemma.

Lemma 1. Let L be a finite language. Then asc(L) = 1 if and only if L is prefix-free (i. e., no prefix of w ∈ L, which is different from w, is in L).

If we now assume that asc(L ∪ L ) = 1, then L m ∪ L n is prefix-free, and consequently L m and L n are prefix-free, too, which gives asc(L) = asc(L ) = 1.

Moreover, if asc(L) = 1 and thus L is prefix-free, we get that L \ L is prefix-free for all languages L . Therefore, we get

asc(L \ L ) = 0 if L ⊆ L 1 otherwise .
However, we see that there are differences between the situations for finite sets and finite unary sets at one hand and arbitrary unary sets and finite unary sets at the other hand. These differences come from the fact that, for a unary finite set L with n elements, we have asc(L) = n, from which the statements for finite unary sets follow.

We now turn to catenation where we have no results -except for some trivial cases -for unary sets.

Theorem 5. The following relations hold for the operation catenation:

g asc • (m, n) = g asc,u • (m, n) = {0} for min{m, n} = 0 N for m ≥ 1, n ≥ 1 , g asc,f • (m, n) = {0} for min{m, n} = 0 g asc,f • (m, n) ⊇ {n + k | k ≥ 0} for m ≥ 2, n ≥ 1 g asc,f,u • (m, n) = {0} for min{m, n} = 0 {k | m + n -1 ≤ k ≤ m • n} for m ≥ 1, n ≥ 1 .
Note that we do not know whether there is a difference for arbitrary and finite sets, since g asc,f . is not completely determined.

For all the preceding operations •, g asc • (m, n) was almost the set of all positive integers. This changes completely, if we consider intersection. Let L and L be two regular sets accepted by the finite automata A and A , respectively. Then the standard construction of an automaton B accepting L ∩ L gives an upper bound asc(A) • asc(A ) for asc(L ∩ L ). Hence g asc ∩ (m, n) contains only numbers ≤ m • n. Theorem 6. The following relation holds for the operation intersection: For m ≥ 0 and n ≥ 0,

g asc ∩ (m, n) ⊇ {(m -k)(n -l) + s | 0 ≤ k ≤ m, 0 ≤ l ≤ n, 0 ≤ s ≤ min{k, l}}.
We mention some easy consequences: -g asc ∩ (0, n) = g asc ∩ (m, 0) = {0} for m ≥ 0 and n ≥ 0, -m • n ∈ g asc ∩ (m, n) for m ≥ 0 and n ≥ 0, -for m ≥ 0, we have g asc ∩ (m, m) ⊇ {r | 0 ≤ r ≤ 4m 9 }, i. e., a large section of small numbers is in g asc ∩ (m, m). For the unary case and intersection, we have the following statements: Theorem 7. The following relation holds for the operation intersection: For m ≥ 0 and n ≥ 0,

g asc,u ∩ (m, m) ⊇ {(m -k)(m -k) + s | 0 ≤ k ≤ m, 0 ≤ s ≤ k} (1)
and g asc,f,u ∩ (m, n) = {0, 1, . . . , min{m, n}}.

By the proof of (1), one can give an extension for m = n and numbers k and l with 0 ≤ k ≤ m and 0 ≤ l ≤ n, but one has to use in the formulation min{m, n} and min{k, l} which makes the formulae a little bit hard to read.

We have no useful result for g asc,f ∩ (m, n).

We have seen above that there are differences if we considered in general case or the unary case. Thus it is a natural question if there are further differences if we restrict the size of the underlying alphabet, i. e., if we consider the binary, ternary etc. case. We mention that all results presented above for arbitrary regular languages and finite languages already hold for alphabets with at least two letters. Therefore it is not necessary to distinguish by the size of the alphabet.

Syntactic Complexity Measures for Context-Free Languages

In this section we only consider context-free languages; therefore we omit the adjective "context-free. We start with the remark that, Var(L) ≤ 1 for any finite language L (the set consisting of the words w 1 , w 2 , . . . , w n is generated by a grammar with the rules S → w 1 , S → w 2 , . . . S → w n ) and Var(L) ≤ 2 for any unary contextfree language (L = {a n1 , a n2 , . . . , a ns } ∪ a p {a m1 , a m2 , . . . , a mt } is generated by a grammar with the rules S → a n1 , S → a n2 , . . . , S → a ns , S → S , S → a p S , S → a m2 S → a m1 , . . . , S → a mt ). Thus, the sets g Var,f

• (m, n) are not defined if m ≥ 2 or n ≥ 2, and the sets g Var,u

• (m, n) are not defined if m ≥ 3 or n ≥ 3. We now present the results for the reversal operation. Theorem 8. For K ∈ {Var, Prod, Symb} and all permissible m ∈ N ∪ {0},

g K R (m) = {m}, g K,f R (m) = {m}, g K,u R (m) = {m}, g K,f,u R (m) = {m}.
From commutativity of union and Theorem 8, it follows that, for the measures K ∈ {Var, Prod, Symb},

g K ∪ (m, n) = g K ∪ (n, m) and g K • (m, n) = g K • (n, m)
and the corresponding relations also hold if we restrict to finite languages, unary languages, and finite unary languages. Therefore we can assume without loss of generality that m ≥ n, if we discuss union or product.

We have the following results concerning operations and the number of variables. Theorem 10. The behaviour of Var under catenation is shown in Figure 2. We see that there is a large difference between arbitrary regular languages on the one side and finite or unary sets on the other hand, but the difference only originates from the restricted domain of g Var,f

arbitrary g Var ∪ (m, n) = {1, 2, . . . , m + n + 1} for m ≥ 1, n ≥ 1 finite g Var,f ∪ (1, 0) = g Var,f ∪ (0, 1) = g Var,f ∪ (1, 1) = {1}, g Var,f ∪ (0, 0) = {0} unary g Var,u ∪ (m, n) = {1, 2} for 1 ≤ m ≤ 2, 1 ≤ n ≤ 2 g Var,u ∪ (1, 0) = g Var,u ∪ (0, 1) = {1}, g Var,u ∪ (0, 0) = {0} finite unary g Var,f,u ∪ (1, 0) = g Var,f,u ∪ (0, 1) = g Var,f,u ∪ (1, 1) = {1}, g Var,f,u ∪ (0, 0) = {0}
arbitrary g Var • (m, n) ⊇ {1} ∪ {max{m, n}, max{m, n} + 1, . . . , m + n + 1} for m ≥ 1, n ≥ 1 finite g Var,f ∪ (1, 1) = {1}, g Var,f • (1, 0) = g Var,f • (0, 1) = g Var,f ∪ (0, 0) = {0} unary g Var,u • (m, n) = {1, 2} for 1 ≤ m ≤ 2, 1 ≤ n ≤ 2 g Var,u • (1, 0) = g Var,u • (0, 1) = g Var,u • (0, 0) = {0} finite unary g Var,f,u ∪ (1, 1) = {1}, g Var,f,u • (1, 0) = g Var,f,u • (0, 1) = g Var,f,u ∪ (0, 0) = {0}
• and g Var,u

• . Between finite and finite unary sets, there is no difference.

We now consider the number of productions.

Theorem 12. Let m ≥ n ≥ 2.
i) The number 1 and all numbers k with k > m+n+2 are not in g Prod

∪ (m, n). ii) If n ≥ 7, then {k | 6 ≤ k ≤ m + n + 2} ⊆ g Prod ∪ (m, n). iii) If n ∈ {5, 6}, then {k | 4 ≤ k ≤ m + n + 2} ⊆ g Prod ∪ (m, n). iv) If n = 4, then {2} ∪ {k | 4 ≤ k ≤ m + n + 2} ⊆ g Prod ∪ (m, n). v) If n ∈ {2, 3}, then {k | 2 ≤ k ≤ m + n + 2} = g Prod ∪ (m, n).
(m, n). ii) If m ≥ n ≥ 1, then {m, m + 1, . . . , m + n} ⊆ g Prod,f ∪ (m, n). iii) If m ≥ n ≥ 3, then {n, n + 1, . . . m + n} ⊆ g Prod,f ∪ (m, n). iv) If m ≥ 6 and m ≥ n ≥ 4, then {6, 7, . . . , m + n} ⊆ g Prod,f ∪ (m, n).
Theorem 15. i) For all numbers m ≥ 1 and n ≥ 1, the number 1 and all numbers k with k > m + n + 2 are not in g Prod,u

∪ (m, n). ii) If m ≥ n ≥ 1, then {m, m + 1, . . . m + n} ⊆ g Prod,u ∪ (m, n). iii) If m ≥ n ≥ 3, then {n, n + 1, . . . m + n} ⊆ g Prod,u ∪ (m, n).
The essential differences between the cases of arbitrary, finite, and unary sets are:

-If we restrict to finite sets, then m+n+1 and m+n+2 are not in g P rod,f ∪ (m, n) and not in g P rod,f,u ∪ (m, n).

-If we restrict to the unary case we only know that the numbers k ≥ min{m, n} are in g P rod,u ∪ (m, n) and g P rod,f,u ∪ (m, n); for "small" numbers we miss constructions. For the star operation, we have the following results.

Theorem 16. The following relations hold:

i) g Prod * (0) = g Prod,f * (0) = {1}, ii) g Prod * (1) = g Prod,f * (1) = {1, 2}, iii) For n ≥ 2, g Prod * (n) = {2, 3, . . . , n + 2} and g Prod,f * (n) = {2, 3, . . . , n + 1}.
We see that the only difference between arbitrary context-free and finite sets is that n + 2 is not contained in g Prod,f * (n). We do not have non-trivial results for g Prod,u * and g Prod,f,u * . We now discuss the concatenation and restrict to the general case, because all our proofs require infinite languages and languages over an alphabet with at least two letters (i. e., we cannot present results on g Prod,f

• , g Prod,u

• , and g Prod,f,u • ).

Theorem 17. i) For all numbers m ≥ n ≥ 1, the number 0 and all numbers k

with k ≥ m + n + 1 are not in g Prod • (m, n). Moreover, if m ≥ 2, then m + 2 / ∈ g Prod • (m, 1) and 1 / ∈ g Prod • (m, n). ii) We have {1} = g Prod • (1, 1). iii) We have {2, 3, 4, 5} = g Prod • (2, 2) and {m, m+1, m+2, m+3} ⊆ g Prod • (m, 2) for m ≥ 2. iv) We have {m + n -1, m + n, m + n + 1} ⊆ g Prod • (m, n) for m, n ∈ {3, 4}. v) We have {n + 2, n + 3, . . . m + n + 1} ⊆ g Prod • (m, n) for m ≥ n ≥ 5.
With respect to the number of symbols the situation is not very clear for small numbers n and m. We only give the results for "large" numbers; for a proof and further facts we refer to [START_REF] Harbich | Regel-und Symbolkomplexität kontextfreier Sprachen unter ausgewählten Operationen[END_REF]. ii) For all numbers m ≥ 8 and n ≥ 5 with m ≥ n we have

{k | k ≥ m + n + 5} ∩ g Symb • (m, n) = ∅ and {n + 4, n + 5 . . . , m + n -2} ∪ {m + n + 4} ⊆ g Symb • (m, n).
iii) For all numbers m ≥ 10, we have

{k | k ≥ m + 7} ∩ g Symb * (m) = ∅

Conclusion

We have presented a summary of result concerning the operational complexity of the number of accepting states for regular languages and of the number of nonterminals, productions, and symbols for context-free languages.

For the number of accepting states and the operations union, set-subtraction, complement, and star, the results are complete, and we see that there are -essentially -no differences between arbitrary, finite, and unary sets. However, the finite unary sets behave completely differently. With respect to catenation, the situation can be the same, but, for a proof, a complete determination of g asc,f

• is necessary (and missing at present). For the intersection, we have not enough information in order to make a statement on the comparison.

The situation is different for the syntactic measures of context-free languages. Concerning the number of nonterminals, we have a difference between arbitrary context-free languages and the restricted versions, but it comes from the very limited domain (of the variables m and n in the case of restrictions). If we restrict to "large" arguments (say m ≥ n ≥ 50, which can be justified by practical reasons), we have a good situation for the number of productions with respect to union and star since the difference between arbitrary context-free sets and finite sets is only in two or one "large" values. For the comparison of unary and finite unary languages, we need more information.

In order to get a more complete picture, it is necessary to determine the sets g Prod,f • , g Prod,u

• , and all sets with a restriction and the measure Symb. Finally, we mention that it remains open to determine the sets g asc • and their restricted versions for further operations as reversal (L R ) or squaring (L 2 ), quotients, etc. as well as the sets g K

• with K ∈ {Var, Prod, Symb} for operations as squaring, quotients, etc.

  fin. unary Union mn mn -(m + n) ∼ mn max{m, n} Intersection mn mn -3(m + n) + 12 ∼ mn min{m, n} Complement m

Fig. 1 .

 1 Fig. 1. Behaviour of the number of variables under union

Fig. 2 .

 2 Fig. 2. Behaviour of the number of variables under catenation

Fig. 3 .

 3 Fig. 3. Behaviour of the number of variables under star

Theorem 18 .

 18 i) For all numbers m ≥ 23 and n ≥ 23, we have {k | k ≥ m + n + 7} ∩ g Symb ∪ (m, n) = ∅ and {23, 24, . . . , n} ∪ {n + 3, n + 4, . . . , m + n -2} ∪ {m + n + 6} ⊆ g Symb ∪ (m, n).

  and {10, 11, . . . , m} ∪ {m + 6} ⊆ g Symb * (m).