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

Ivana Krajňáková
email: krajnakova@saske.sk

NFA-to-DFA Trade-Off for Regular Operations

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

Introduction

The state complexity of a regular language L, sc(L), is the smallest number of states in any deterministic finite automaton (DFA) recognising L. The state complexity of a k-ary regular operation • is a function from N k to N given by (n 1 , n 2 , . . . , n k ) → max{sc(•(L 1 , L 2 , . . . , L k )) | sc(L i ) ≤ n i for i = 1, 2, . . . , k}.

The first results on the state complexity of basic regular operations have been obtained by Maslov [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF], Birget [START_REF] Birget | Intersection and union of regular languages and state complexity. Inform[END_REF], and Yu et al. [15]. Holzer and Kutrib [START_REF] Holzer | Nondeterministic descriptional complexity of regular languages[END_REF] considered the representation of regular languages by nondeterministic finite automata (NFAs) and defined and studied the nondeterministic state complexity of regular languages and operations in an analogous way. Jirásek Jr. et al. [START_REF] Jirásek | Operations on self-verifying finite automata[END_REF]9] investigated operational state complexity using representation of regular languages by self-verifying and unambiguous finite automata. Notice that in all of the above mentioned cases, the arguments and the results of regular operations are represented by the same computational model.

In this paper, we consider the NFA-to-DFA trade-off for regular operations, that is, we assume that the arguments of an operation are represented by NFAs, while the resulting language is required to be represented by a DFA. Our motivation comes from the following two streams of research.

While investigating operational state complexity on self-verifying or unambiguous automata, which are nondeterministic, the NFA-to-DFA trade-off provides an upper bound on the complexity of the corresponding operation since every DFA is self-verifying as well as unambiguous. As shown in [START_REF] Jirásek | Operations on self-verifying finite automata[END_REF]9], these upper bounds are tight for several operations.

Our second motivation comes from the research on the state complexity of combined operations that began with the paper by Salomaa et al. [START_REF] Salomaa | State complexity of combined operations. Theoret[END_REF]. If a combined operation does not contain complementation, we can perform all the included operations using NFAs. Then, the NFA-to-DFA trade-off for the outermost operation can be used to get an upper bound on the desired complexity of a given combined operation.

We examine the NFA-to-DFA trade-off for complementation, intersection, union, difference, symmetric difference, reversal, star, concatenation, shuffle, and left and right quotient. For each of these operations, we get tight upper bound on its NFA-to-DFA trade-off. To describe witnesses, we use either binary or quaternary alphabets. The binary alphabet is always optimal in the sense that the corresponding upper bounds cannot be met by any unary languages.

To conclude this introduction, let us mention that the trade-offs between different models of finite automata have been studied for the forever operator defined as L → (Σ * L c ) c by Birget [START_REF] Birget | The state complexity of Σ * L and its connection with temporal logic. Inform[END_REF] and Hospodár et al. [START_REF] Hospodár | Descriptional complexity of the forever operator[END_REF].

Preliminaries

We assume that the reader is familiar with basic notions in formal languages and automata theory. For details and all unexplained notions, the reader may refer to [START_REF] Yu | Chapter 2: Regular languages[END_REF].

Let Σ be a finite non-empty alphabet. Then Σ * denotes the set of all words over Σ including the empty word ε. If u, v, w ∈ Σ * and w = uv, then u is prefix of w. Moreover, if u = w, then u is a proper prefix of w. A language over an alphabet Σ is any subset of Σ * .

If K and L are languages over Σ, then the complement of L is L c = Σ * \ L. The intersection, union, difference, and symmetric difference of K and L are defined as for arbitrary sets. Next, we consider the following regular operations:

concatenation KL = {uv | u ∈ K and v ∈ L}, star L * = i≥0 L i where L 0 = {ε} and L i+1 = L i L, reversal L R = {w R | w ∈ L}, shuffle K ¡ L = {u 1 v 1 u 2 v 2 • • • u k v k | u i , v i ∈ Σ * , u 1 u 2 • • • u k ∈ K, v 1 v 2 • • • v k ∈ L}, right quotient KL -1 = {x ∈ Σ * | xy ∈ K for some y ∈ L}, and left quotient L -1 K = {x ∈ Σ * | yx ∈ K for some y ∈ L}.
A nondeterministic finite automaton (NFA) is a 5-tuple A = (Q, Σ, •, s, F ), where Q is a finite non-empty set of states, Σ is a finite input alphabet, s ∈ Q is the starting (or initial) state, F ⊆ Q is the set of final (or accepting) states, and • : Q × Σ → 2 Q is the transition function which can be extended to the domain 2 Q × Σ * in the natural way. The language recognised by the NFA A is the set of words

L(A) = {w ∈ Σ * | s • w ∩ F = ∅}.
An NFA A is a deterministic finite automaton if |q • a| = 1 for each q ∈ Q and a ∈ Σ. In such a case we write q •a = q instead of q •a = {q }, and use q a -→ q to denote that q • a = q . Sometimes we permit non-deterministic automata to have more initial states; in such a case we use an abbreviation NNFA from [START_REF] Yu | Chapter 2: Regular languages[END_REF].

A subset S of Q is reachable in an NNFA A = (Q, Σ, •, I, F ) if S = I • w for some w ∈ Σ * , and it is co-reachable if it is reachable in the reversed automaton A R obtained from A by reversing all its transitions and swapping the roles of the initial and final states.

Every NNFA A = (Q, Σ, •, I, F ) has an equivalent deterministic finite automaton

D(A) = (2 Q , Σ, •, I, {T ⊆ Q | T ∩ F = ∅}). The DFA D(A) is called the subset automaton of A.
The following observation provides a sufficient condition that guarantees distinguishability of all states in a subset automaton. We use this lemma throughout the paper.

Lemma 1 (Distinguishability). Let A be an NFA such that for every state q of A the singleton set {q} is co-reachable in A. Then every two distinct states of the subset automaton D(A) are distinguishable.

Proof. Let us take two distinct subsets S and T of D(A). Without loss of generality, let q ∈ S \ T . Since the set {q} is co-reachable in A, there is a word w q that is accepted by A from the state q and rejected from every other state. It follows that in D(A), the word w q is accepted from S and rejected from T . Hence S and T are distinguishable in D(A).

The next lemma shows that every subset of the state set of the NFA from Fig. 1 is reachable in the corresponding subset automaton. It also shows that to reach every non-empty subset, the final state n -1 may be visited only in the very last steps. This is an important property which is used later the get the results for concatenation.

Lemma 2 (Reachability). Let A = ({0, 1, . . . , n -1}, {a, b}, •, 0, {n -1}) be the NFA from Fig. 1. where i

• a = {i + 1} if 0 ≤ i ≤ n -2, and i • b = {0, i}.
Then for each subset S of {0, 1, . . . , n -1}, there exists a word u S ∈ {a, b} * such that 0 Proof. In the subset automaton D(A), each singleton set {i} is reached from the initial subset {0} by a i and the empty set is reached from {n -1} by a. Each set {i 1 , i 2 , . . . , i k } of size k, where 2 ≤ k ≤ n and 0

• u S = S. Moreover, (1) if S = ∅ and n -1 / ∈ S, then n -1 / ∈ 0 • u for each prefix u of u S ; (2) if n -1 ∈ S and 0 / ∈ S, then n -1 / ∈ 0 • u for each proper prefix u of u S , (3) if n -1 ∈ S and 0 ∈ S, then u S = u b and n -1 / ∈ 0 • u for each proper prefix u of u , 0 1 2 . . . n -2 n -
≤ i 1 < i 2 < • • • < i k ≤ n -1, is reached from the set {i 2 -i 1 , i 3 -i 1 , . . . , i k -i 1 } of size k -1 by ba i1
. This proves the reachability of all subsets of {0, 1, . . . , n -1} by induction. Hence for each S ⊆ {0, 1, . . . , n -1}, there is a word u S ∈ {a, b} * such that 0 • u S = S. By a careful analysis of the proof above, we get the properties (1), (2), and (3).

Complementation, Reversal, Star, and Concatenation

In this section we examine the NFA-to-DFA trade-off for basic unary operations and concatenation. We start with complementation. Its state complexity is n while its non-deterministic state complexity is 2 n [START_REF] Jirásková | State complexity of some operations on binary regular languages[END_REF]. The next theorem shows that its NFA-to-DFA trade-off is 2 n as well.

Theorem 3 (Complementation). Let L be a language over Σ recognised by an n-state NFA. Then sc(L c ) ≤ 2 n , and the bound is tight if |Σ| ≥ 2.

Proof. Since sc(L c ) = sc(L), the upper bound follows from the upper bound on determinization. For tightness, let L be the language recognised by the NFA A shown in Fig. 1 on page 3. By Lemma 2, every subset of {0, 1, . . . , n-1} is reachable in the subset automaton D(A). Since every singleton set is co-reachable in A via a word in a * , all states of D(A) are pairwise distinguishable by Lemma 1.

Notice that the binary alphabet used in the previous proof is optimal since every unary n-state NFA can be simulated by a DFA of 2 O( √ n ln n) states as shown by Chrobak [START_REF] Chrobak | Finite automata and unary languages[END_REF]. Let us continue with the reversal operation. Note that it is enough to take the reversal of any DFA with one final state meeting the upper bound 2 n on the state complexity of reversal. Such a binary DFA was described by Šebej [START_REF] Šebej | Reversal of regular languages and state complexity[END_REF]. Here we describe a different witness with significantly simpler proof.

Theorem 4 (Reversal). Let L be a language over Σ recognised by an nstate NFA, where n ≥ 2. Then sc(L R ) ≤ 2 n , and the bound is tight if |Σ| ≥ 2.

Proof. Let L be accepted by an n-state NFA A = (Q, Σ, •, s, F ). By reversing all the transitions in A and taking F as the set of starting states and {s} as set of final states we obtain an n-state NNFA that accepts L R . It follows that L R is accepted by a DFA with at most 2 n states.

To prove tightness, consider the binary language L recognised by the nstate NFA N = ({0, 1, . . . , n -1}, {a, b}, •, 0, {0, 1, . . . , n -1}) shown in Fig. 2 where i

• a = {i + 1 mod n}, i • b = {i} if i ≥ 1. By reversing NFA N we get an NNFA N R that recognises L R .
The set of initial state of N R is {0, 1, . . . , n -1} and its unique final state is 0. Notice that each subset of the state set of N R can be shifted cyclically by one by reading a, and the state 0 can be eliminated from every set containing 0 by reading b. It follows that every subset of {0, 1, . . . , n -1} can be reached from the initial subset {0, 1, . . . , n -1} in the subset automaton D(N R ). Next, every set {i} is co-reachable in N R via a word in a * and using Lemma 1 we get that every two distinct states of the D(N R ) are distinguishable.

The binary alphabet used in the previous theorem is optimal for the same reason as in the case of complementation. We continue with the star operation. While its state complexity is 3 4 2 n [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF] and its nondeterministic state complexity is n + 1 [START_REF] Jirásková | State complexity of some operations on binary regular languages[END_REF], we show that the NFA-to-DFA trade-off for star is 2 n . Theorem 5 (Star). Let n ≥ 2. Let L be a language over an alphabet Σ recognised by an n-state NFA. Then sc(L * ) ≤ 2 n , and the bound is tight if |Σ| ≥ 2.

Proof. Let L be recognised by an n-state NFA A = (Q, Σ, •, s, F ). Construct an NNFA N recognising L * from A as follows. First, for each transition (p, a, q) in A with q ∈ F , add the transition (p, a, s). Next, if s / ∈ F , then add a new initial and final state q 0 to accept the empty word. Consider the subset automaton D(N ). The only reachable set in D(N ) containing the state q 0 is the initial subset {s, q 0 }. All the remaining reachable sets are subsets of Q. Moreover, if a reachable set contains a final state of A, then it also contains the state s. If A has a final state different from s, then at least 2 n-2 sets are unreachable in D(N ), so the upper bound is 1 + (3/4)2 n in this case. If F = {s}, then the construction above results in the same automaton, so L * = L. In such a case, the upper bound is 2 n .

To prove tightness, consider the binary language L recognised by the nstate NFA A = ({0, 1, . . . , n -1}, {a, b}, •, 0, {0}) shown in Fig. 3 where for each state i, i

• a = {i + 1 mod n}, i • b = {0, i} if i ≥ 1. Then L * = L.
In the subset automaton D(A), the empty set is reached from the initial subset {0} by b. The reachability of all non-empty subsets is proved exactly the same way as in the proof of Lemma 2. Since every singleton set is co-reachable in A via a word in a * , all the states of D(A) are pairwise distinguishable by Lemma 1.

The witness from the previous proof is described over a binary alphabet. It is impossible to meet the upper bound 2 n in the unary case since every unary nstate NFA can be simulated be a DFA with 2 O( √ n ln n) states. The unary language recognised by the NFA from Fig. 4 provides a lower bound (n -1) 2 + 2; notice that this NFA is not unambiguous. We conjecture that this lower bound is tight. Our computations support this conjecture. We conclude this section with the concatenation operation the state complexity of which is m2 n -2 n-1 [START_REF] Maslov | Estimates of the number of states of finite automata[END_REF] and nondeterministic complexity is m + n [START_REF] Holzer | Nondeterministic descriptional complexity of regular languages[END_REF]. The next theorem shows that NFA-to-DFA trade-off for concatenation is 3 4 2 m+n , that is, it is exponential in both m and n.

Theorem 6 (Concatenation). Let K and L be non-empty languages over an alphabet Σ recognised by an m-state and n-state NFA, respectively, with m, n ≥ 3. Then sc(KL) ≤ 3 4 2 m+n , and the bound is tight if |Σ| ≥ 4. For each transition (p, a, q) in NFA A with q ∈ F A , add the transition (p, a, s B ). The set of initial states of

Proof. Let A = (Q A , Σ, • A , s A , F A ) and B = (Q B , Σ, • B , s B , F B )
N is {s A } if s A / ∈ F A , or {s A , s B } if s A ∈ F A . The set of final states of N is F B .
The following condition holds in the subset automaton D(N ): each reachable subset containing a state from F A must contain the state s B . It follows that at least 2 m+n-2 are unreachable in D(N ), and the upper bound follows.

For tightness, let Σ = {a, b, c, d} and K and L be the languages over Σ recognised by the NFAs A = ({q 0 , q 1 , . . . , q m-1 }, Σ, • A , q 0 , {q m-1 }) and B = ({0, 1, . . . , n -1}, Σ, • B , 0, {n -1}) shown in Fig. 5. Notice that transitions on a and b in A are the same as in the NFA in Fig. 1 and perform the identity function in B. The roles of the transitions on c and d in B are the same as the roles of a and b in A. Therefore, it follows from Lemma 2 that for every subset S of {q 0 , q 1 , . . . , q m-1 }, there is a word u S in {a, b} * such that q 0 • A u S = S, and for every subset T of {0, 1, . . . , n -1}, there is a word v T in {c, d} * such that 0 • B v T = T . Moreover, the words u S satisfy the conditions (1), ( 2), (3) in Lemma 2.

To get an NFA N recognising KL from NFAs A and B, add the transitions (q m-2 , a, 0), (q m-1 , b, 0), and (q m-1 , c, 0). The initial state of N is {q 0 } and its unique final state is n -1. Let S ⊆ {q 0 , q 1 , . . . , q m-1 } and T ⊆ {0, 1, . . . , n -1} be two subsets such that if q m-1 ∈ S then 0 ∈ T . The following transitions use the words u S ∈ {a, b} * and v T ∈ {c, d} * given by Lemma 2 to show that the set S ∪ T is reachable in the subset automaton D(N ):

0 1 2 . . . n -2 n -1 a a a
{q 0 } a m-1 ---→ {q m-1 , 0} b - → {q 0 , q m-1 , 0} d -→ {q 0 , 0}; {q 0 , 0} v T --→ {q 0 } ∪ T u S --→ S ∪ T if S = ∅; {q 0 , 0} a -→ {q 1 , 0} d -→ {0} v T --→ T ;
let us emphasise that by Lemma 2, while reading u S , the final state q m-1 of A is not visited, except for the last step if q 0 / ∈ S and q m-1 ∈ S and when we must have 0 ∈ T , and for the last two steps if q 0 ∈ S and q m-1 ∈ S when u S ends with b that fixes the initial state 0 of B which must be in T . This proves the reachability of 3 4 2 m+n states in the subset automaton D(N ). To prove distinguishability, notice that each singleton set {j}, 0 ≤ j ≤ n -1 is co-reachable in N via a word in c * . Next, {q m-1 } is co-reachable by c n , and each {q i }, 0 ≤ i ≤ m -2 is co-reachable via a word in c n a * . By Lemma 1, all states of D(N ) are pairwise distinguishable.

The witness in the previous proof is defined over a quaternary alphabet. Consider binary languages K = (a + b) * a(a + b) m-2 and L = (a + b) n-1 recognised by an m-state and n-state NFA, respectively. Then KL = (a + b) * a(a + b) m+n-3 , the minimal DFA for which has 2 m+n-4 states. This gives the lower bound (1/16)2 m+n in the binary case which is asymptotically the same as the upper bound for quaternary case. In the unary case the upper bound is 2 O( √ (m+n) ln(m+n)) . A lower bound 1 + F (n -1) is given by languages K = {ε} and L equal to the witness for determinization in the unary case; here F (n) is Landau's function given by F

(n) = max{lcm(x 1 , . . . , x k ) | n = x 1 + • • • + x k }, and with F (n) ≈ 2 √ n ln n .
Proof. Let A be an m-state NFA recognising K and B be an n-state NFA recognising L. Consider the corresponding subset automata D(A) and D(B) with 2 m and 2 n states, respectively. Both of them have at least one rejecting sink state, namely, the empty set. Then all upper bounds follow from Lemma 7.

For tightness, let K and L by the languages recognised by NFAs A and B from Fig. 6. Notice that transitions on a and b in A are the same as in the NFA in Fig. 1 To prove distinguishability first consider union. Then (S, T ) is final in M ∪ if m -1 ∈ S or n -1 ∈ T . Let (S, T ) and (S , T ) be two distinct states of M ∪ . Then S = S or T = T . In the first case, without loss of generality let s ∈ S \ S . Consider the word a m-1-s c n . Notice that (S, T )

a m-1-s c n -------→ ({m -1} ∪ S 1 , ∅) for some S 1 ⊆ {0, 1, . . . , m -1}; (S , T ) a m-1-s c n -------→ (S 1 , ∅) where m -1 / ∈ S 1 .
It follows that a m-1-s c n is accepted by M ∪ from (S, T ) and rejected from (S , T ).

The case of T = T is symmetric. We can prove distinguishability for symmetric difference in the exact same manner. We can also find the appropriate words that distinguish the desired number of states in the product automaton for intersection and difference.

Notice that the upper bounds in the previous theorem cannot be met by unary languages. The cases of binary and ternary alphabets remain open. 5 Shuffle, Left and Right Quotient

0 A 1 2 . . . m -2 m -1 0 B 1 2 . . . n -2 n -1 a b, c
Here we consider three more binary operations. In all three cases the upper bound constructions are similar to the case when the operation inputs are given by DFAs. Our lower bound for shuffle is the same as the upper bound on its state complexity. The lower bound for left quotient is greater by one than its state complexity. For right quotient, the NFA-to-DFA trade-off is 2 m , while its (nondeterministic) state complexity is m.

Theorem 9 (Shuffle). Let K and L be languages over Σ recognised by an mstate and n-state NFA, respectively, where m, n ≥ 3. Then sc(K ¡ L) ≤ 2 mn , and the bound is tight if |Σ| ≥ 4.

Proof. Let A = (Q A , Σ, s A , • A , F A ) and B = (Q B , Σ, s B , • B , F B
) be an m-state and n-state NFAs recognising the languages K and L, respectively. Then the language K ¡ L is recognised by mn-state NFA

N = (Q A × Q B , Σ, •, (s A , s B ), F A × F B )
where for each (p, q) ∈ Q In the unary case the upper bound for shuffle is again 2 O( √ (m+n) ln(m+n)) .

A × Q B and a ∈ Σ, (p, q) • a = {(p, q ) | q ∈ q • B a} ∪ {(p , q) | p ∈ p • A a}.
Theorem 10 (Left and Right Quotient). Let K and L be languages over an alphabet Σ recognised by an m-state and n-state NFA, respectively, where m, n ≥ 2.

Then sc(L -1 K), sc(KL -1 ) ≤ 2 m , and the bounds are tight if |Σ| ≥ 2.

Proof. Let A = (Q A , Σ, s A , • A , F A ) be an m-state NFA recognising K. The language L -1 K is recognised by the m-state NFA N obtained from A by changing the set of initial states to {s A • A w | w ∈ L}. The language KL -1 is recognised by the m-state NFA N obtained from A by changing the set of final states to {q ∈ Q A | q • A w ∈ F A for some w ∈ L}. Hence sc(L -1 K), sc(KL -1 ) ≤ 2 m . For tightness, notice that {ε} -1 K = K{ε} -1 = K. Therefore, the upper bound 2 m is met in both cases by L = {ε} and K equal to the binary m-state witness NFA for determinization given by Lemma 2; for distinguishability, notice that each singleton set is co-reachable in this NFA.

The binary alphabet used in the theorem above is optimal since determinization in the unary case is in 2 O( √ n ln n) .

Fig. 1 .

 1 Fig. 1. A binary witness NFA for determinization and complementation.

Fig. 2 .

 2 Fig. 2. A binary witness NFA for reversal meeting the upper bound 2 n .

Fig. 3 .

 3 Fig. 3. A binary witness NFA for star meeting the upper bound 2 n .

  be NFAs recognising K and L, respectively, with |Q A | = m, |Q B | = n Construct an NNFA N for KL from NFAs A and B as follows.

Fig. 4 .Fig. 5 .

 45 Fig. 4. A possible unary witness for star meeting the bound (n -1) 2 + 2.

  and perform the identity function in B. The roles of the transitions on c and d in B are the same as the roles of a and b in A. Moreover c and d perform the identity function in A. It follows from Lemma 2 that for every S ⊆ {0, 1, . . . , m -1}, there is a word u S ∈ {a, b} * such that 0• A u S = S, and for every T ⊆ {0, 1, . . . , n-1}, there is a word v T ∈ {c, d} * such that 0• B v T = T . Let • ∈ {∪, ⊕, ∩, \}. Construct the product automaton M • from DFAs D(A) and D(B). The initial state of M • is ({0}, {0}). Let S ⊆ {0, 1, . . . , m -1} and T ⊆ {0, 1, . . . , n -1}. Then the state (S, T ) is reachable in M • from the initial state by the word u S v T . Hence each state of M • is reachable.

Fig. 6 .

 6 Fig. 6. Quaternary witnesses for Boolean operations.

  It follows that sc(K ¡ L) ≤ 2 mn . The m-state and n-state partial DFAs over {a, b, c, d, f } meeting this upper bound have been described in [4, Proof of Theorem 1]. Notice in that the role of c and d in that proof is to reach the set Q A × Q B in the subset automaton. The same goal can be achieved if we replace c and d by the transitions on letter e defined as follows: 0 • A e = {0, 1}, i • A e = {i + 1}, if 1 ≤ i ≤ m -2, and 0 • B e = {0, 1}, j • B e = {j + 1}, if 1 ≤ j ≤ n -2. As a result we get a quaternary witness for shuffle.

Table 1 .

 1 The NFA-to-DFA trade-off vs (nondeterministic) state complexity.

		SVFA	|Σ|	UFA	|Σ|
	complementation	n		1		n 2-≤ • ≤ 2 0.79n+log n	1
	reversal	2n + 1	2		n	1
	star concatenation union	3 4 • 2 n Θ(3 m 3 2 n ) 3 3 4 • 2 n + 1 m 3 + 2 n + 1 3 3 4 • 2 n 4 • 2 m+n -1 mn 2 mn + m + n ≤ • ≤ m + n2 0.79n+log n 4 3 7
	symmetric difference mn	2		?
	intersection	mn	2		mn	2
	difference	mn	2		?
	shuffle	?				2 mn -1	5
	left quotient	2 m -1	2 m + 1	2 m -1	2
	right quotient	3	m 3	3	m 3 + 2	2 m -1	2

Table 2 .

 2 Operational complexity for self-verifying and unambiguous automata.

Acknowledgement

We would like to kindly thank Michal Hospodár for his valuable notes and comments.

Research supported by grant VEGA 2/0132/19 and grant APVV-15-0091. This work was conducted as a part of PhD study of the second author at Comenius University in Bratislava.

Boolean Operations

Here we consider NFA-to-DFA trade-off for four binary Boolean operations. First, we recall some notions. We call a state q of a DFA A = (Q, Σ, •, s, F ) a sink state if q • a = q for every letter a ∈ Σ. The state q is called dead if reading every word from the state q results in a non-accepting state of A.

To get an automaton recognising union, intersection, difference, or symmetric difference of two languages we use the product construction as described below.

and a ∈ Σ, and

If the operation inputs are given by NFAs, we first apply the subset construction to get DFAs for those inputs. Then we construct the corresponding product automaton. Notice that every subset automaton has at least one rejecting sink state, namely, the empty set. The following lemma provides upper bounds for Boolean operations on DFAs considering the presence of the rejecting sink states. Lemma 7. Let K and L be languages over Σ accepted by DFAs with m and n states respectively. Assume that both DFAs have a rejecting sink state. Then sc(K ∪ L) ≤ mn, sc(K ⊕ L) ≤ mn, sc(K ∩ L) ≤ mn -m -n + 2, and sc(K \ L) ≤ mn -n + 1.

Proof. For each Boolean operation • ∈ {∪, ∩, \, ⊕}, the language K • L is recognised by the product automaton M • which has mn states. This gives the upper bounds for union and symmetric difference. Let d A and d B be the rejecting sink states of A and B, respectively. Then in the product automaton M ∩ recognizing K ∩ L, the states (d A , q) with q ∈ Q B and the states (p, d B ) with p ∈ Q A are dead and can be merged into one sink state. This gives the upper bound (m -1)(n -1) + 1 = mn -m -n + 2. In the product automaton M \ recognising K \L, the states (d A , p) with p ∈ Q B are dead, which gives the upper bound (m -1)n + 1 = mn -n + 1. Now we are ready to get tight upper bounds on NFA-to-DFA trade-off for Boolean operations. Theorem 8. Let K and L be languages over Σ recognised by an m-state and n-state NFA, respectively, where m, n ≥ 2. Then sc(K ∪ L), sc(K ⊕ L) ≤ 2 m+n , sc(K ∩ L) ≤ 2 m+n -2 m -2 n + 2, and sc(K \ L) ≤ 2 m+n -2 n + 1. All these bounds are tight if |Σ| ≥ 4.


Benedek Nagy
email: nbenedek.inf@gmail.com

Union-Freeness, Deterministic Union-Freeness and Union-Complexity

Union-free expressions are regular expressions without using the union operation. Consequently, union-free languages are described by regular expressions using only concatenation and Kleene star. The language class is also characterised by a special class of finite automata: 1CFPAs have exactly one cycle-free accepting path from each of their states. Obviously such an automaton has exactly one accepting state. The deterministic counterpart of such class of automata defines the deterministic union-free languages. A regular expression is in union (disjunctive) normal form if it is a finite union of union-free expressions. By manipulating regular expressions, each of them has equivalent expression in union normal form. By the minimum number of union-free expressions needed to describe a regular language, its union-complexity is defined. For any natural number n there are languages such that their union complexity is n. However, there is not known any simple algorithm to determine the union-complexity of any language. Regarding the deterministic union-free languages, there are regular languages such that they cannot be written as a union of finitely many deterministic union-free languages.

Introduction

The family of regular languages is one of the most known, most common and most applied class of languages. It is the smallest, the simplest class of the Chomsky hierarchy. The descriptions of the regular languages by regular expressions are widely used. They are generated by regular, by left-linear and by right-linear grammars. They are accepted by finite state automata: both nondeterministic and deterministic variants characterize this class of languages. Recently various classes of subregular languages play also importance [START_REF] Holzer | Structure and complexity of some subregular language families[END_REF]9].

In this paper we will consider special subclasses of the regular languages. The main topic is the class of union-free languages, they are defined by regular expressions without the union. They were first mentioned as star-dot regular languages in [2]. Later on, in [4], their description by equations were examined, and it was shown that this class cannot be axiomatized by a finite set of equations. Automata theoretical characterisation was given in [START_REF] Nagy | Union-free regular languages and 1-cycle-free-path-automata[END_REF] allowing to define the deterministic counterpart of the class, the family of deterministic union-free languages [START_REF] Brzozowski | Most complex deterministic union-free regular languages[END_REF][START_REF] Jirásková | Complexity in union-free regular languages[END_REF][START_REF] Jirásková | On union-free and deterministic union-free languages[END_REF].

It is also known [2,[START_REF] Nagy | A normal form for regular expressions[END_REF] that every regular language is a finite union of unionfree languages. The union-complexity of the regular languages is defined subsequently based on minimal decompositions [START_REF] Afonin | Minimal union-free decompositions of regular languages[END_REF][START_REF] Nagy | A normal form for regular expressions[END_REF][START_REF] Nagy | On union-complexity of regular languages[END_REF]. However, there are regular languages that cannot be obtained as a finite union of deterministic union-free languages [START_REF] Jirásková | On union-free and deterministic union-free languages[END_REF]. On the other hand allowing infinite unions one is able to describe every recursively enumerable language. Therefore infinite unions are usually not allowed when languages are described.

The structure of the paper is as follows. In the next section we define the union-free languages based on regular expressions, we show their characterisation by 1-cycle-free path automata, and we define deterministic union-free regular languages and a new class between the union-free and deterministic union-free class. In Section 3 some properties of the mentioned three language classes, e.g., closure properties are summarised. Section 4 is about the union decomposition of regular languages and the union-complexity.

The Union-Free Language Classes and Their Corresponding Automata Classes

In this section first we define the union-free languages and then we recall the corresponding class of finite automata. We assume that the reader is familiar with the basic concepts of formal languages and automata, thus for each unexplained concepts she/he is referred to any standard textbook on the topic, e.g., to [START_REF] Hopcroft | Introduction to Automata Theory, Languages and Computation[END_REF] or the Handbook chapter [START_REF] Yu | Regular languages[END_REF]. Here we show only specific notions closely related to the topic of this paper. The empty word is denoted by λ, V is a finite alphabet, while +, •, * are the regular operations on languages, i.e., the union, the concatenation and the Kleene star.

Definition 1 (Union-free expression, union-free language). A regular expression is union-free expression if only the operators concatenation and Kleene star are used in its description. A language is union-free if there is a union-free description that defines it.

A kind of related idea is to define and use star-free expressions, where only union and concatenation are allowed in regular expressions. They define exactly the class of finite languages. Since the class of finite languages has already their well-known name, in the literature, the terms of star-free expressions and languages usually refer to expressions which are defined by operations union, concatenation and complement, and the corresponding language family [START_REF] Yu | Regular languages[END_REF]. Similarly, in the literature sometimes a wider class of languages are called union-free, those which have a description by operations concatenation, Kleene star and complement [9]. However, in this paper, the above stricter concept is used.

The empty language is described as regular expression ∅. Each other regular expression can be written in a tree form, in which the leaves are representing elements of V ∪ {λ} and the other nodes are representing the regular operations. The language ∅ is very special, in the rest of the paper we assume that the language we consider is not the empty one. Definition 2. A 5-tuple A = (Q, S, V, δ, F ) is a non-deterministic finite automaton, with the finite set of states Q. Further, S ∈ Q is the initial state, V is the (input) alphabet and F ⊂ Q is the set of final (or accepting) states. The function δ : Q×(V ∪{λ}) → 2 Q is the transition function. A path is called accepting path of the word w if it is written as

(S = Q 0 )a 1 Q 1 a 2 Q 2 ...a n-1 Q n-1 a n Q n where Q i+1 ∈ δ(Q i , a i+1 ) for every 0 ≤ i < n with Q n ∈ F and w = a 1 a 2 ...a n (a i ∈ V ∪ {λ}).
A word is accepted by the finite automata if it has an accepting path.

A path Q 0 a 1 Q 1 a 2 Q 2 . . . a n-1 Q n-1 a n Q n is called a cycle if Q 0 = Q n (where n > 0). A path without any repeated state is called cycle-free path. Two cycle- free paths Q 0 a 1 . . . a n Q n and P 0 b 1 . . . b m P m are called alternative paths, if they are not identical, but Q 0 = P 0 and Q n = P m .
In this paper we use only automata with the following property: for each state Q i of the automaton there is an accepting path that contains Q i . Consequently, there is no useless and sink states and the automaton may not be fully determined, i.e., it may happen that for a state Q i and an input letter a the transition function assigns the empty set.

Definition 3 (1CFPA, d-1CFPA and n-1CFPA). A nondeterministic finite automaton A is a 1 cycle-free path automaton, a 1CFPA, for short, if there is a unique cycle-free accepting path from each of its states. Moreover, if the automaton A has no λ-transition, then it is an n-1CFPA, and if it is a deterministic, then it d-1CFPA. Figure 1 shows an example. As a consequence of the definition above, a 1CFPA has exactly one final state. From now on F will refer not only for the set of final states, but for its unique element as well. The following result is proven in [START_REF] Nagy | Union-free regular languages and 1-cycle-free-path-automata[END_REF].

Theorem 4. The family of languages which are described by union-free expressions and the family of languages recognized by 1CFPAs are exactly the same.

Proposition 5. Since from every state R there is exactly one transition is going to the direction of F (without cycle), the word which transfers the state R to F in cycle-free path is unique for each state. Definition 6 (backbone). The backbone of the automaton is the cycle-free path from the initial state (S) to the final state (F ). The other parts of the automaton are the loops, sub-loops etc. The word accepted by the backbone is called the backbone word.

In a directed graph there are two different concepts that are somewhat analogous to cycles in the undirected graphs. Cycles in undirected graph allow to visit a node more than once in a path, while they also allow to connect nodes in alternative paths. The directed cycles allow to return to an already visited node in a path (in a directed graph). Two alternative paths (as two halves of an undirected cycle) give the chance to reach the same target node from a start node in two different cycle-free way. Based on that we can compare the graphs of the classes of automata accepting the union-free and the finite languages. Proposition 7. Every union-free language is accepted by automata with graphs having no alternative paths. Every automaton with one final state and without alternative paths is accepting a union-free language. Every finite language is accepted by automata with no cycles. Cycle-free automata accept finite languages.

As we have already mentioned the class of finite languages is an important subclass of the class of regular languages. Both the classes of nondeterministic and deterministic variants of cycle-free finite state automata correspond to the class of finite languages. The classes of the union-free languages form a hierarchy as we describe here. The result of Theorem 4 allows us to call the language classes accepted by n-1CFPAs and d-1CFPAs as λ-free nondeterministic union-free and deterministic union-free, respectively. We also use the abbreviated names nunion-free and d-union-free for these classes of languages.

Properties of Union-Free Language Classes

Now we detail some properties of the languages defined above. Lemma 8. There are infinitely many non-comparable x-union-free languages with x ∈ {λ, n, d}. Lemma 9. A union-free language is infinite if and only if every regular expression contain Kleene star that describes it. Corollary 10. A union-free language is either infinite or contains at most one word.

Lemma 11. Let L be an infinite x-union-free language (x ∈ {λ, n, d}). There are infinitely many sequences of union-free languages starting with L, in which each language is a proper subset of the previous one.

The next proposition gives a necessary condition for a language to be unionfree.

Proposition 12. The shortest word of a union-free language L is unique and it is the backbone word. In a union-free language each word contains the backbone word in scattered way.

It is well-known that the Parikh images of regular languages coincide with the semi-linear sets. The Parikh images of the union-free languages form a special subset of the semi-linear sets, and at the same time, they form a special superset of the linear sets.

Definition 13 (Conditional-linear sets). A set of vectors W is conditionallinear if the following condition holds. Every vector α is in W if and only if it can be written in the form

α = α 0 + δ 1 n 1 α 1 + δ 2 n 2 α i + • • • + δ m n m α m ,
where n j are non-negative integers and α j are fixed vectors of non-negative integers, and δ i are conditional coefficients defined in the following way: δ 1 = 1, and if i > 1, then δ i is either without any condition and equals to 1, or depends on the coefficient of some α j with j < i, and in such a case it equals to 1 if δ j n j > 0 and to 0 if δ j n j = 0:

δ i = 1,
if there is no condition for α i ;

δ i = 1, if δ j n j > 0; 0, if δ j n j = 0;
if α i depends on the coefficient of α j .

Having δ i = 1 for all i without any conditions, the linear sets can be obtained. Thus conditional-linear sets are a kind of generalisations of linear sets. Moreover, all conditional linear sets are semilinear, i.e., they are finite unions of linear sets. However, there are semilinear sets that are not conditional linear. Theorem 14. Conditional-linear sets coincide with the Parikh images of unionfree languages.

Let L be a union-free language. Note that λ ∈ L if and only if the backbone word is the empty word. This implies that every terminal is under a Kleene star in the tree of the regular expression. Under these circumstances the language can be accepted by a 1CFPA with backbone word λ. If L is n-union-free and λ ∈ L, then S = F in the corresponding n-1CFPA. Since every 1CFPA (and thus d-1CFPA) has exactly one accepting state, languages which cannot be accepted by deterministic finite automata with only one final state are not d-union-free languages. Now, we are in the position to claim the theorem about the closure properties of union-free languages.

Theorem 15 (Closure properties of union-free languages). The family of union-free languages is closed under the operations concatenation and Kleene star. Further, it is closed under the following operations: reversal, homeomorphism, substitution by union-free expression, Kleene plus, and for any fixed natural number n it is closed under the n-th power.

The family of union-free languages is not closed under the following operations: union (of course), intersection, intersection with regular languages, complement, difference, symmetric difference, cyclic permutation, permutation, shuffle, inverse morphism and substitution by regular expression.

Corollary 16. The family of union-free languages is not a cone, not an AFL and not an anti-AFL.

On the other hand we have only anti-closure properties for the deterministic counterpart:

Theorem 17 (Closure properties of d-union-free languages). The class of deterministic union-free languages is not closed under union, complement, difference, intersection, intersection by regular languages, concatenation, square, Kleene star, reversal, cyclic shift, permutation, homomorphism, and inverse morphism.

We are turning to hierarchy results. On one hand it is clear by definition that all d-union-free languages are n-union-free languages and all n-union-free languages are union-free. The language a * b * is union-free. However, it is not nunion-free. The language (aa+ab+ba+bb) * is n-union-free, but not d-union-free. Thus, we can state the following:

Corollary 18. There is a proper hierarchy among the union-free classes: d-union free n-union-free union-free.

Union-Complexity of Regular Languages

We start this section by a decomposition result [2,10].

Definition 19. A regular expression is in union normal form if it is a finite union of union-free expressions.

Theorem 20. For each regular language there is a regular expression in union normal form that describes it.

Moreover, based on the following equivalences among regular expressions, 1.

(x + y) * can be written in the form (x * y * ) * , 2.

(x + y)z can be written in the form (xz + yz), 3.

x(z + v) can be written in the form (xz + xv), 4. (x + y)(z + v) can be written in the form (xz + xv) + (yz + yv), where x, y, z and v are arbitrary regular expressions, one can efficiently find an equivalent expression in union normal form for any regular expression.

And now we have some notes about the regular expressions containing the union operation, but describing union-free regular languages.

Let r be a regular expression. For the sake of simplicity assume that its tree is a binary tree, which means that all unions and concatenations have exactly two components, while the Kleene stars have exactly one.

Theorem 21. Let r be a regular expression. If every union operation is under a Kleene star operation in the tree form of r, then r defines a union-free regular language.

The class of union-free languages is an interesting class including several languages since we have:

Corollary 22. For each regular language L the language L * is union-free regular. Now, based on [START_REF] Nagy | A normal form for regular expressions[END_REF][START_REF] Nagy | On union-complexity of regular languages[END_REF] we are going to define the union-complexity of languages by specific decompositions.

A decomposition L = n i=1 L i is called proper, if there is no language L j such that L j ⊆ j-1 i=1 L i ∪ n i=j+1 L i .
(One needs all the languages L i to describe L, i.e., there is no useless member of the union.) A normal form is called proper normal form if it gives a proper decomposition.

Definition 23 (Union-complexity). L = n i=1 L i is a minimal decomposition of the language L if each L i is a union-free language and there is no m < n such that L = m i=1 L i , where each L i is union-free. Then, n is called the unioncomplexity of language L. Every minimal decomposition is a proper decomposition, but the converse does not hold, there are proper decompositions which are not minimal. Now we are showing special minimal decompositions: a minimal decomposition of L is given by maximal union-free languages, if there is no L i such that L i ⊃ L i and replacing L i with L i in the union, the resulted language L is the same as before.

Proposition 24. The minimal decomposition by maximal union-free languages of a regular language may not be unique.

Consider the language over V = {a, b} containing all words that do not contain bb as a consecutive substring. Its union-complexity is 2, but there are two minimal decompositions using maximal union-free languages: Let L n be the family of languages which can be written as union of n unionfree languages.

Theorem 25. The families L n and L m are in the following relation:

L n L m iff n > m.
The previous theorem presents an infinite hierarchy of regular languages, in which the union-free ones are the simplest ones. The planet of regular languages is shown in Fig. 2, where the "west pole" is the empty language, the west region contains the union-free languages, the south region contains the finite languages. The intersection of the classes of union-free and finite languages includes the empty language and all the singleton languages. A singleton contains exactly one word. The union-complexity grows to the east direction.

Regular languages

Finite languages

Unionfree languages Unioncomplex.

n-words

The empty language Fig. 2. The "planet" of regular languages.

We can summarise the known results about the union-complexity in the following theorem.

Theorem 26. The union-complexity of union-free languages is at most 1: it is 0 for the empty language and 1 for every nonempty union-free language. For every finite language, its union-complexity is exactly the cardinality of the language. A language is regular if and only if its union-complexity is finite. For each regular language L the union-complexity of L * is 1.

In [START_REF] Afonin | Minimal union-free decompositions of regular languages[END_REF] it has been proven that the union-complexity of regular languages is computable. However, the method is very complex and cannot be used in practical applications. Some lower and upper bound may be computed much faster, e.g., a union normal form of a regular language defines an upper bound for its union-complexity. On the other hand one can also obtain lower bounds by analysing the short words of the language: Proposition 27. Let L be a regular language. Fix a natural number n and let Z n = {w ∈ L | |w| ≤ n}. Consider any subset Z of Z n with maximal cardinality such that any of the elements of Z does not contain any other elements of Z in a scattered way. Then |Z| is a lower bound for the union-complexity of L.

While every regular language can be expressed as a union of a finite number of union-free languages, this is not true if we replace union-free languages by d-union-free languages.

Theorem 28. The language described by the regular expression ((a + b)(a + b)) * cannot be expressed as a union of a finite number of deterministic union-free languages.

As new subregular classes of languages, we may consider the finite unions of deterministic union-free languages [START_REF] Jirásková | On union-free and deterministic union-free languages[END_REF].

Definition 29. For every positive integer m, we define dL m as the family of languages that can be expressed as a union of m d-union-free languages. Furthermore, let

dL * = ∞ i=1 dL i .
The following result shows that the classes dL n define a proper infinite hierarchy similarly to the classes shown in Theorem 25.

Theorem 30. Let n and m be positive integers. The families dL n and dL m are in the following relation:

dL n dL m iff n > m.
Moreover, dL * dL m .

Conclusions

We examined in detail the classes of union-free and deterministic union-free languages, moreover we have defined a new class between them, namely the class of n-union-free languages. Various properties of these classes were shown. Since every regular language is a finite union of union-free languages, the unioncomplexity as a complexity measure of the regular languages was considered.

Although it is known that the union-complexity of the regular languages can be computed, there is not known any efficient algorithm to do it. It was also recalled that there is a union-free language which cannot be written as a finite union of d-union-free languages.

Fig. 1 .

 1 Fig. 1. An example for a 1-cycle-free-path-automaton.

(

  (ba) * a * ) * + ((ba) * a * ) * b((ab) * a * ) * , and ((ab) * a * ) * + ((ba) * a * ) * b((ab) * a * ) * .


Henning Fernau
email: fernau@uni-trier.de

Martin Vu

Regulated Tree Automata

Keywords: Regulated rewriting, graph control, tree automata, yield operation

Regulated rewriting is one of the classical areas in Formal Languages, as tree automata are a classical topic. Somewhat surprisingly, there have been no attempts so far to combine both areas. Here, we start this type of research, introducing regulated tree automata, proving in particular characterizations of the yields of such regulated automata.

Introduction

The area of regulated rewriting, still well-covered by the classical monograph of Dassow and Păun [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF], drew its main motivation from the idea to enrich contextfree grammars with certain control mechanisms in order to be able to model linguistic features that are not expressible with traditional context-free grammars, yet keeping at least some of the beauties of these. More specifically, programmed grammars, matrix grammars, and grammars with regular control were introduced and studied around 1970. It soon became clear that control involving so-called appearance checks tends to be too powerful in the sense that all recursively enumerable languages can be characterized this way. This somewhat counter-acts the idea of keeping some of the advantages of context-free grammars over, say, Turing machines. Therefore, we are mainly focusing on models without appearance checks in the following. Applications and motivations are also underlined in the relatively recent monograph by Meduna and Zemek [START_REF] Meduna | Regulated Grammars and Automata[END_REF].

Conversely, finite tree automata have been invented to allow for processing (mostly ordered) trees (as opposed to strings) in a simple manner. Trees not only showed up as a kind of intermediate data structure within compilers, but they are a ubiquitous data structure when it comes to processing semi-structured documents and also for working with natural languages [START_REF] Gécseg | Tree Automata[END_REF][START_REF] Comon | Tree Automata, Techniques and Applications[END_REF][START_REF] Kallmeyer | Parsing Beyond Context-Free Grammars[END_REF].

Recall the basic well-known link between context-free grammars and derivation trees, often established in practice via considering pushdown automata. However, it is not possible to go this way in connection with regulated rewriting, as already observed by Meduna and Kolar in [START_REF] Meduna | Regulated pushdown automata[END_REF]. The basic reason is that the work of pushdown automata rather corresponds to leftmost (or rightmost) derivations in a very strict sense (called leftmost-1 in [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF]). Yet, this strict interpretation does not increase the descriptive power of context-free languages, which counter-acts one of the basic motivations for considering regulated rewriting.

Rather, we are going to follow here the path pioneered by Doner, Thatcher (and also to Wright) [START_REF] Doner | Tree acceptors and some of their applications[END_REF][START_REF] Thatcher | Characterizing derivation trees of context-free grammars through a generalization of finite automata theory[END_REF] who showed that the context-free string languages are just the languages that can be obtained by mapping the tree language accepted by some finite tree automaton to its so-called yield, which means that, given an ordered tree, we read the labels of the leaves from left to right. We will obtain similar results for regulated tree grammars in this paper. As tree automata usually come in two working modes (top-down versus bottom-up), our studies also revive the question of generating versus accepting (or analyzing) grammars [START_REF] Bordihn | Accepting grammars with regulation[END_REF].

We are going to present basic results concerning regulated tree automata and their yields. Due to reasons of space, (straightforward) formal induction arguments are not given here. Most of these can be found in [START_REF] Vu | Regulierte Grammatiken und regulierte Baumautomaten. Bachelorarbeit, Informatikwissenschaften[END_REF].

Definitions

Classical Regulated Rewriting

There are several ways to introduce the basic control mechanisms of regulated rewriting. We are giving a simplified exposition now, basically following [START_REF] Fernau | Graph-controlled grammars as language acceptors[END_REF], adapted to the case of not allowing appearance checks.

A graph-controlled grammar is an 8-tuple G = (V N , V T , P, S, Γ, Σ, Φ, h) where -(V N , V T , P, S) define, as in a phrase structure grammar, the set of nonterminals, terminals, context-free core rules, and the start symbol, respectively; -Γ is a digraph, i.e., Γ = (U, E), with E ⊆ U × U ; -Σ ⊆ U are the initial vertices; -Φ ⊆ U are the final vertices; h : U → (2 P \ {∅}) relates vertices with rule sets.

We say that (x, u) ⇒ (y, v) holds in G with (x, u), (y, v)

∈ (V N ∪ V T ) * × U if, for some x 1 , x 2 , α, β ∈ (V N ∪ V T ) * , x = x 1 αx 2 , y = x 1 βx 2 , α → β ∈ h(u), and (u, v) ∈ E .
The reflexive transitive closure of ⇒ is denoted by * ⇒. The language generated by G (where P contains only context-free (generating, non-erasing) rules from

V N × (V N ∪ V T ) + ) is defined by L gen (G) = {x ∈ V * T | ∃u ∈ Σ ∃v ∈ Φ ((S, u) * ⇒ (x, v))} .
The corresponding language family is written L gen (G, CF-ε), as we do not allow ε-rules. If P contains only context-free (accepting) rules from (V N ∪ V T ) + × V N , then the language accepted by G is defined by

L acc (G) = {x ∈ V * T | ∃u ∈ Σ ∃v ∈ Φ ((x, u) * ⇒ (S, v))} ,
yielding the language family L acc (G, CF -ε).

We consider three special cases of graph-controlled grammars in the following.

-A grammar with regular control is a graph-controlled grammar where every vertex contains exactly one rule. Usually, these grammars are introduced via regular control languages, but the correspondance with automata graphs is obvious. By L gen (rC,CF -ε), the family of languages generated by contextfree grammars with regular control is denoted. -A programmed grammar is a grammar with regular control with no designated initial or final vertices, i.e., formally Σ = Φ = U . This means that it is possible to start a derivation in each vertex containing a rule whose left-hand side equals the start symbol S, and it is possible to stop anywhere when a terminal string has been derived. As language families, we obtain, e.g., L gen (P, CF -ε). -A matrix grammar is a grammar with regular control obeying the additional restriction:

• Initial and final vertices coincide. Only the initial vertices (not necessarily containing rules with left-hand side S) are allowed to have more than one in-going arc. Only predecessors of final vertices are allowed to have more than one out-going arc. Moreover, between every predecessor of a final vertex and every initial vertex, there is an arc. As language families, we obtain, e.g., L gen (M, CF -ε).

With literally the same restrictions, we can define, for instance, L acc (M, CF -ε). Recall that all language families introduced in this subsection coincide [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF][START_REF] Bordihn | Accepting grammars with regulation[END_REF].

Remark 1. The formalization of regular control is possibly most different from the one found in traditional textbooks. However, if Γ = (U, E) together with Σ, Φ, h defines the control graph structure, then we can relate a finite automaton A with state set U as follows: We have a transition (u, r, v) if h(u) = {r}; Σ is the set of initial states, and if u ∈ Φ and (u, v) ∈ E, then v is a final state of A. Now, if u 1 , u 2 , . . . , u n describes a directed path from u 1 ∈ Σ to u n ∈ Φ, then via {r i } = h(u i ) this corresponds to a sequence of rules r 1 r 2 . . . r n , which, when fed into A, will be accepted. Also the converse construction is possible. Hence, we can in particular assume that the automaton A that describes the set of permitted rule sequences is deterministic.

Tree Automata

Let N be the set of nonnegative integers and let (N * , •, ε) (or simply N * ) be the free monoid generated by N. For y, x ∈ N * , we write y ≤ x iff there is a z ∈ N * with x = y • z. "y < x" abbreviates: y ≤ x and y = x. As usual, |x| denotes the length of the word x.

We now give the necessary definitions for trees and tree automata. More details can be found, e.g., in [START_REF] Comon | Tree Automata, Techniques and Applications[END_REF], where also many examples can be found.

A ranked alphabet V is a finite set of symbols together with a finite relation called rank relation r

V ⊂ V × N. Define V n := {f ∈ V | (f, n) ∈ r V }.
Since elements in V n are often considered as function symbols (standing for functions of arity n), elements in V 0 are also called constant symbols. A tree over V is a mapping t : ∆ t → V , where the domain ∆ t is a finite subset of N * such that (1) if x ∈ ∆ t and y < x, then y ∈ ∆

t ; (2) if y • i ∈ ∆ t , i ∈ N, then y • j ∈ ∆ t for 1 ≤ j ≤ i. An element of ∆ t is also called a node of t, where the node ε is the root of the tree. Then t(x) ∈ V n whenever, for i ∈ N, x • i ∈ ∆ t iff 1 ≤ i ≤ n. If t(x) = A, A is the label of x. Let V t denote
the set of all finite trees over V . By this definition, trees are rooted, directed, acyclic graphs in which every node except the root has one predecessor and the direct successors of any node are linearly ordered from left to right. Interpreting V as a set of function symbols, V t can be identified with the well-formed terms over V . A frontier node in t is a node y ∈ ∆ t such there is no x ∈ ∆ t with y < x. If y ∈ ∆ t is not a frontier node, it is called interior node. The depth of a tree t is defined as depth(t) = max{|x| | x ∈ ∆ t }, whereas the size of t is given by |∆ t |. Letters will be viewed as trees of size one and depth zero.

We are now going to define a catenation on trees. Let $ be a new symbol, i.e., $ / ∈ V , of rank 0. Let V t $ denote the set of all trees over V ∪ {$} which contain exactly one occurrence of label $. By definition, only frontier nodes can carry the label $. For trees u ∈ V t $ and t ∈ (V t ∪ V t $ ), we define an operation # to replace the frontier node labelled with $ of u by t according to

u#t(x) = u(x), if x ∈ ∆ u ∧ u(x) = $, t(y), if x = z • y ∧ u(z) = $ ∧ y ∈ ∆ t . If U ⊆ V t $ and T ⊆ (V t ∪ V t $ ), then U #T := {u#t | u ∈ U ∧ t ∈ T }. For t ∈ V t and x ∈ ∆ t , the subtree of t at x, denoted by t/x, is defined by t/x(y) = t(x • y) for any y ∈ ∆ t/x , where ∆ t/x := {y | x•y ∈ ∆ t }. ST(T ) := {t/x | t ∈ T ∧x ∈ ∆ t }
is the set of subtrees of trees from T ⊆ V t . Furthermore, for any t ∈ V t and any tree language T ⊆ V t , the quotient of T and t is defined as:

U T (t) := {u ∈ V t $ | u#t ∈ T }, if t ∈ V t \ V 0 , t, if t ∈ V 0 .
Let V be a ranked alphabet and m be the maximum rank of the symbols in V . A (bottom-up) (finite-state) tree automaton over V is a quadruple A = (Q, V, δ, F ) such that Q is a finite state alphabet (disjoint with V 0 ), F ⊆ Q is a set of final states, and δ = (δ 0 , . . . , δ m ) is an m + 1-tuple of state transition functions, where δ 0 (a) = {a} for a ∈ V 0 and δ k :

V k × (Q ∪ V 0 ) k → 2 Q for k = 1, . . . , m.
In this definition, the constant symbols at the frontier nodes are taken as sort of initial states. Now, a transition relation (also denoted by δ) can be recursively defined on V t by letting

δ(f (t 1 , . . . , t k )) := {f }, if k = 0, qi∈δ(ti),i=1,...,k δ k (f, q 1 , . . . , q k ), if k > 0.
A tree t is accepted by A iff δ(t) ∩ F = ∅. The tree language accepted by A is denoted by L t (A). A is deterministic if each of the functions δ k maps each possible argument to a set of cardinality at most one. Deterministic tree automata can be viewed as algorithms for labelling the nodes of a tree with states. Analogously to the case of string automata, it can be shown that nondeterministic and deterministic bottom-up finite-state tree automata accept the same class of tree languages, namely the regular tree languages, at the expense of a possibly exponential state explosion. Rules are sometimes also written like f (q 1 , . . . , q k ) → q instead of saying that q ∈ δ k (f, q 1 , . . . , q k ). Sometimes, also ε-moves are allowed, written like q → q, i.e., no part of the tree is consumed, only the state is changed. As in the string case, finite tree automata with ε-moves only accept regular tree languages.

An alternative view on the work of tree automata is that of labelling a tree with states. To this end, we will formally view all symbols from Q as having rank zero, so that they may serve as labels of frontier nodes. Now, A (or more specifically, its transition function δ) defines a derivation relation δ on (V ∪ Q) t by s δ t if s = t and there are trees u

∈ (V ∪ Q) t $ , s = f (q 1 , . . . , q k ), t = q with s = u#s , t = u#t , f ∈ V k , q ∈ δ k (f, q 1 , . . . , q k ). Clearly, s ∈ V t is accepted by a tree automaton A = (Q, V, δ, F ) if s *
δ q f for some q f ∈ F . If we consider δ as a set of rules, it makes also sense to define s δ t for subsets of rules δ ⊆ δ. We will use this notation when defining regulated tree automata.

It is also possible to define tree automata A = (Q, V, δ, I) that work top-down. Rules are now of the form q → f (q 1 , . . . , q k ), and the derivation relation basically reverses the arrows. Hence, also finite top-down tree automata characterize the regular tree languages. However, deterministic finite top-down tree automata are a strictly weaker model.

We already informally recalled the Theorem of Doner, Thatcher (and also to Wright) [START_REF] Doner | Tree acceptors and some of their applications[END_REF][START_REF] Thatcher | Characterizing derivation trees of context-free grammars through a generalization of finite automata theory[END_REF]. To formally state it, we provide the necessary key notion: For t ∈ V t , we define the yield-operator Y as follows:

Y(t) = t(ε), if t(ε) ∈ V 0 Y(t/1) • • • Y(t/k), if t(ε) ∈ V k , k > 0
In words, the recursion means that the yield of a tree with a root with k children equals the concatenation of the yields of the trees whose roots are these children. The operator naturally extends to tree languages and tree language families. Theorem 2 (Doner, Thatcher, Wright). A string language is context-free if and only if it is the yield of a regular tree language.

Notice that the proof of this result makes use of the fact that for contextfree languages, we can assume that they are generated by some context-free grammar without erasing productions, neglecting the possibility to describe the empty word itself. As it is still an open problem whether or not we can get rid of erasing rules with regulated grammars as introduced in the previous subsection, we restricted our attention to regulated grammars without erasing rules there, as we strive for analogues of Theorem 2 in the following.

Regulated Tree Automata

We are now defining the central new notion of this paper, combining the two classical worlds so far introduced. Hence, a graph-controlled finite tree automaton is an 8-tuple A = (Q, V, δ, F, Γ, Σ, Φ, h) where -A = (Q, V, δ, F ) define a finite tree automaton; -Γ, Σ, Φ define the graph structure as in graph-controlled grammars; h : U → (2 δ \ {∅}) relates vertices with rule sets; notice that we consider δ as a set of rules here.

We say that (s, u)

|= (t, v) holds via A with (s, u), (t, v) ∈ (Q ∪ V ) t × U if s h(u) t and (u, v) ∈ E .
The reflexive transitive closure of |= is denoted by |= * . The tree language accepted by A (assuming that A works bottom-up) is defined by

L bu (A) = {t ∈ V t | ∃q ∈ F ∃u ∈ Σ ∃v ∈ Φ((t, u) |= * (q, v))} .
Similarly, we can define acceptance for top-down automata, yielding the language L td (A). This gives the tree language families L t (G, bu) and L t (G, td ), depending on whether bottom-up or top-down automata are considered. If we want to explicitly rule out ε-moves, we add -ε to our notations. As the notions of regular control, matrix and programmed have been introduced in Subsection 2.1 as simple syntactical restrictions of graph control, we can carry over them immediately to regulated finite tree automata, giving, e.g., the notion of a matrix finite tree automaton. This also gives language families such as L t (P, td , -ε).

Basic Results for Regulated Tree Automata

By the definitions themselves, we can conclude (also confer [START_REF] Freund | A general framework for regulated rewriting based on the applicability of rules[END_REF], but mind the partially different definitions):

Lemma 3. Let µ ∈ {bu, td }. Then, we have

L t (P, µ) ⊆ L t (rC, µ) ⊆ L t (G, µ) and L t (M, µ) ⊆ L t (rC, µ) .
Proposition 4. For C ∈ {G, P, rC, M}, L t (C, bu) = L t (C, td ).

Proof. Recall [START_REF] Comon | Tree Automata, Techniques and Applications[END_REF] that for any finite top-down tree automaton A td , one can construct an equivalent finite bottom-up automaton A bu by simply reversing the relation , plus exchanging initial and final states. Similarly, we can simulate A = (A td , Γ, Σ, Φ, h) by A = (A bu , Γ , Σ , Φ , h ), where Γ = (U , E ) is obtained from Γ = (U, E) by reversing the arcs, Σ = Φ, Φ = Σ, and h associates the reversed rule variants of h(u) to u ∈ U = U . Clearly, if (Γ, Σ, Φ, h) satisfies the restrictions imposed by C ∈ {G, P, rC, M}, then (Γ , Σ , Φ , h ) does so, as well. The converse inclusion is similarly seen.

Hence, we can from now on consider either the bottom-up or the top-down case, whatever is more convenient to us. We are going to present a sequence of technical lemmas that combine classical ideas from tree automata and from regulated rewriting. Illustrations by examples can be found in the Appendix.

Lemma 5. L t (G, bu) ⊆ L t (rC, bu). Lemma 10. Y(L t (G, bu)) ⊆ L acc (G, CF -ε).
Proof. Consider a graph-controlled finite tree automaton A = (Q, V, δ, F, Γ, Σ, Φ, h) with Γ = (U, E). We are going to construct a graph-controlled context-free grammar G A = (V N , V T , P, q f , Γ, Σ, Φ, h ) such that Y(L bu (A)) = L acc (G A ). As it is usually the case with nondeterministic automata, we can assume (without loss of generality) that A only one final (accepting) state, i.e., F = {q f }. We construct a simulating grammar G A as follows:

N = Q, T = V 0 , w → q ∈ h (u) if q ∈ Q, w = w 1 • • • w k , w j ∈ V 0 ∪ Q whenever g(w 1 , . . . , w k ) → q ∈ h(u) for some g ∈ V k (*).
Now, each derivation of A producing a certain yield can be simulated by G A , where the correct labels of inner nodes are guessed during the derivation due to (*). Conversely, these guesses according to (*) label the inner nodes of a derivation tree in a way corresponding to a tree that can be accepted by A.

A formal reasoning would be a relatively tedious exercise, based on the ideas originating from Doner, Thatcher and Wright in the late sixties, which can be also found in any textbook on tree languages. Therefore, we only sketch the basic idea of the inductive step of the proof in the following. Recall that the definition of transforms trees with leaf labels from (V 0 ∪ Q) into trees with leaf labels from (V 0 ∪Q); extending the definition of the yield operator Y accordingly, this means that sentential forms of G A are transformed. Notice that the graph control stays the same, which allows the induction to succeed.

Literally the same construction allows us to state:

Lemma 11. Y(L t (G, td )) ⊆ L gen (G, CF -ε).
For the converse direction, we need a normal form result for regulated contextfree grammars that might be of independent interest. A graph-controlled contextfree grammar G = (V N , V T , P, S, Γ, Σ, Φ, h) is called arity-deterministic if for each nonterminal A ∈ N , there exists a unique number α(A) (called the arity of A) such that any rule A → w ∈ P (in the generating case) or w → A ∈ P (in the accepting case) obeys |w| = α(A).

Theorem 12 (Arity-deterministic normal form). For any L ∈ L acc (G, CFε), there exists an arity-deterministic context-free ε-free graph-controlled contextfree grammar G accepting L. A similar statement holds for generating grammars.

As the induction proof given in [8, Theorem 2] can be easily adapted to our case, we omit it here. We only mention that similar results are also true for other forms of control, like matrix grammars.

Lemma 13. Y(L t (G, bu)) ⊇ L acc (G, CF -ε).
Proof.

[Sketch] Starting with an arity-deterministic graph-controlled contextfree grammar G, we can easily interpret its rules as transitions of a controlled finite tree automaton A G . More specifically, we can consider V N ∪ V T as a ranked alphabet V , with V 0 = V T . For any rule w → A, we introduce a rule δ i,k (A, w 1 , . . . , w k ) = {A }, where |w| = α(A) = k. Notice that we have to formally distinguish the nonterminal A of arity k from the state A that has, in a sense, arity zero. A G accepts derivation trees of G. Conversely, the yield of any tree that derives S (in A G ) corresponds to a sentential form that derives S (in G). For further details, we refer to [8, Lemma 2].

Lemma 14. Y(L t (G, td )) ⊇ L gen (G, CF -ε).
Together with the results from the previous section, we conclude a known fact: Theorem 15. Let µ M , µ P , µ rC , µ G ∈ {gen, acc}. Then, we have

L µ M (M, CF -ε) = L µ P (P, CF -ε) = L µ rC (rC, CF -ε) = L µ G (G, CF -ε) .
Remark 16. As the constructions presented in this section do not introduce chain rules (into context-free grammars) and as chain rules correspond to ε-moves for tree automata, the open questions formulated in the previous section easily translate into open questions in the more classical realm of regulated contextfree grammars as follows: Does there exist a normal form for regulated contextfree grammars (without erasing productions) that allows us to avoid chain-rules? Related to this is another open question in the more classical realm of regulated context-free grammars: Does there exist a Chomsky normal form result? Loosely speaking, this corresponds to an arity-bounded normal form for derivation trees.

Adding Appearance Checks

Appearance checks (or maybe better said applicability checks, see [START_REF] Freund | A general framework for regulated rewriting based on the applicability of rules[END_REF]) are one of the key features introduced within regulated rewriting. On the level of graph control, this corresponds to considering bicolored digraphs as control structure [START_REF] Fernau | Graph-controlled grammars as language acceptors[END_REF][START_REF] Wood | Bicolored digraph grammar systems[END_REF]. For reasons of space, we refrain from giving a formal definition in this extended abstract. Notice that there are two ways of interpreting appearance checks in connection with control by bicolored digraphs, with the choice interpretation that first selects a rule in the rule set h(u) and then checks for applicability of the selected tree rewriting rule, or with the interpretation that only considers h(u) to be not applicable if none of the rules in h(u) is applicable. We signal the choice interpretation by adding a c as a subscript. We can prove: Theorem 17. Let µ ∈ {bu, td }. Then, we have

L t (M, µ, ac) = L t (P, µ, ac) = L t (rC, µ, ac) = L t (G, µ, ac) = L t (G c , µ, ac).
We could state similar results as in Theorem 9 for the case when disallowing ε-moves. We have to distinguish more carefully between the bottom-up and the top-down cases due to the following results.

Theorem 18. Let µ ∈ {gen, acc}. Then, we have

L µ (M, CF-ε, ac) = L µ (P, CF- ε, ac) = L µ (rC, CF -ε, ac) = L µ (G, CF -ε, ac) = L µ (G c , CF -ε, ac) . Moreover, L gen (M, CF-ε, ac) = Y(L t (M, td , ac)) L acc (M, CF-ε, ac) = Y(L t (M, bu, ac)) .
Corollary 19. L t (M, td , ac) L t (M, bu, ac) .

Proof. The inclusion itself is seen as before; notice that we can simulate a rule q → f (q 1 , . . . , q k ) that is applied in appearance checking by some ε-move that checks for the presence of q. If the converse inclusion would hold, as well, then the yields of both tree language families would coincide, which contradicts known facts on regulated rewriting, see [START_REF] Bordihn | Accepting grammars with regulation[END_REF].

Conclusions

We started investigations on regulated tree automata in this paper. This new way of looking at trees and regulated rewriting opens up quite an ample ground of research. Apart from the concrete open problems mentioned throughout the paper, which mostly also extend to the case admitting appearance checks, we ask the following, more concrete research questions.

-So far, we completely neglected studying closure properties or algorithmic questions of (variants of) regulated tree automata. It seems to be the case that the standard constructions for showing certain closure properties of regular tree languages (see [START_REF] Comon | Tree Automata, Techniques and Applications[END_REF]) transfer to the regulated case, but, moreover, we conjecture positive closure results for (general) tree homomorphisms, to give one concrete open question in this area. -There are many relations between regulated rewriting and parallel rewriting; see [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF][START_REF] Fernau | Parallel grammars: A phenomenology[END_REF]. We are not aware of a theory of parallel tree automata. We would also expect (again) relations to the question of accepting versus generating grammars [START_REF] Fernau | Remarks on accepting parallel systems[END_REF]. Also, the area of grammar systems is barely touched [START_REF] Csuhaj-Varjú | Grammar Systems: A Grammatical Approach to Distribution and Cooperation[END_REF][START_REF] Fernau | Accepting multi-agent systems: the case of cooperating distributed grammar systems[END_REF][START_REF] Fernau | Cooperating distributed tree automata[END_REF]. Due to the connections between regulated rewriting and cooperating distributed grammar systems (CDGS), see [START_REF] Csuhaj-Varjú | Grammar Systems: A Grammatical Approach to Distribution and Cooperation[END_REF], these investigations might also stir some new interest in and even give some new proof ideas for some old open problems. For instance, it is still open whether (context-free) matrix languages can be characterized by CDGS working in = k-mode. Can results from tree automata be helpful here? We refer to [START_REF] Fernau | Cooperating distributed tree automata[END_REF] for results on cooperating distributed tree automata. -Operations on trees have been one of the cornerstones for developing practically useful mechanisms [START_REF] Kallmeyer | Parsing Beyond Context-Free Grammars[END_REF] for formalizing mild context-sensitivity. The relations between, for instance, tree adjoining languages and variants of regulated context-free grammars have been largely unexplored until today. Apart from this concrete question, we have the hope that combining tree processing with regulated rewriting mechanisms opens up new (practical) applications of regulated rewriting, also leading to new algorithmic questions.

Finally, we like to mention once more the various open problems in the area of classical regulated rewriting scattered throughout the paper. This should renew the interest of the Formal Language community and also shows that (by far) not all problems in that area are solved. We hope that the approach via considering tree languages might be a way to solve some of these problems. Common to all these questions is the quest for normal forms. Here, we like to point to random context grammars, where it was shown rather recently that there is a normal form result that gets rid of erasing productions [START_REF] Zetzsche | On erasing productions in random context grammars[END_REF].

Proof. We only sketch the construction. Consider a graph-controlled finite tree automaton is an 8-tuple A = (Q, V, δ, F, Γ, Σ, Φ, h). We derive an equivalent finite tree automaton with regular control A r = (Q, V, δ, F, Γ r , Σ r , Φ r , h r ) as follows. Let Γ = (U, E). Then, Γ r = (U r , E r ) with U r = u∈U {u} × h(u), E r = {((u, x), (v, y)) | (u, x), (v, y) ∈ U r , (u, v) ∈ E}, Σ r = u∈Σ {u} × h(u), Φ r = u∈Φ {u} × h(u), and h r ((u, x)) = {x} for (u, x) ∈ U r . By construction, |h r ((u, x))| = 1 for all (u, x) ∈ U r . Moreover, if (s, u) |= (t, v) holds via A, then s h(u) t and (u, v) ∈ E, so that for some x ∈ h(u), s {x} t, i.e., (s, (u, x)) |= (t, (v, y)) holds via A r for all y h(v). Induction shows the claim. Lemma 6. L t (rC, bu) ⊆ L t (P, bu).

Proof. We are modifying bottom-up tree automata with regular control step by step in order to obtain an equivalent programmed control. (i) We can assume that initial vertices (from Σ) have no in-going arcs and that there is only one final vertex (i.e., |Φ| = 1) that has no out-going arcs. This can be easily seen by keeping in mind the relation to regular languages and hence to finite string automata (as control devices) as recalled in Remark 1. (ii) Moreover, by using a shadow state alphabet Q , the finite tree automaton itself can check if the derivation control had started in some u i ∈ Σ and also that the corresponding rule was used only once. Namely, the starting rules (that have to process a terminal symbol at some leaf node of the tree) will lead to a primed state q (when it would go to q in the original automaton), and the fact that exactly one primed state was ever entered is then propagated to the root of the tree. Here, it is also necessary to split vertices of the control graph. More specifically, if vertex v contains a rule f (q 1 , . . . , q k ) → q, we create k many twins of v, say, v 1 , . . . , v k , and then v i contains the rule f (q 1 , . . . , q i-1 , q i , q i+1 , . . . , q k ) → q to properly propagate the prime information. This already shows that we can now let any vertex be initial in our control graph without changing the set of accepted trees. (iii) As a further step, we can introduce another shadow state alphabet F as a new set of final states and modify the rules associated to the control graph vertices so that (only and exactly) when moving to u f , with {u f } = Φ, such a final state q is entered. This step might involve splitting vertices v that are predecessors of u f into v and v, where v contains the rule introducing q, while v contains the rule introducing the corresponding state q. Otherwise, v and v have the same predecessors. However, u f is the only successor of v (and not a successor of v), while all other successor vertices that previously existed for v are still successor vertices of v (and not for v). Now, we can (formally) let every vertex be a final vertex without changing the accepted tree language. Again, the correctness of the construction is seen by induction.

Remark 7. For all statements made so far in this section, similar results hold when disallowing ε-moves. We refrain from making this explicit. However, this is no longer obvious for the following construction. This also gives a first open question in the area of regulated tree automata. Lemma 8. L t (P, bu) ⊆ L t (M, bu).

Recall that in the classical construction simulating programmed grammars by matrix grammars, the state information is maintained in a special nonterminal. We follow the same idea here, but with tree automata, this is technically more involved due to the absence of erasing rules. Proof. Consider a programmed automaton A = (Q, V, δ, F, Γ, Σ, Φ, h) with Γ = (U, E) and Σ = Φ = U . Now, we can also assume that the rules associated to start vertices are of the form a → q for some terminal a ∈ V 0 and some state q, this way specifying Σ ⊆ Σ. (a) We add rules by r = a → [q, u] and introduce a new vertex v, with h(v) = {r} and v ∈ Σ, for those u that are successors of v in Γ . More formally, this means that we introduce for each v ∈ Σ as many twins as there are successors of v in Γ . This also defines a new set of initial vertices Σ , with more vertices to be added. All these vertices v have outgoing arcs to all vertices from Σ . (b) For each q ∈ Q ∪ V 0 and each u, v ∈ U \ Σ with (u, v) ∈ E, we introduce a new rule [q, u] → [q, v] and a new vertex [q, u, v] into Γ hosting this new rule. All these vertices also belong to Σ . (c) Introduce an arc from each vertex [q, u, v] to the vertex u containing the rule h(u). All such vertices u have arcs to all vertices from Σ . (d) For each q ∈ Q∪V 0 and each u, v ∈ U \ Σ with (u, v) ∈ E and each 1 ≤ i ≤ k with h(u) = {f (p 1 , . . . , p k ) → p} such that p i = q, we introduce a new rule f (p 1 , . . . , p i-1 , [p i , u], p i+1 , . . . , p k ) → [p, v]; moreover, we create a vertex [q, i, u, v] containing exactly this newly created rule, put it into Σ and link it to all vertices from Σ . (e) For each q ∈ Q ∪ V 0 and each u, v ∈ U \ Σ with (u, v) ∈ E, if h(u) = {q → p}, i.e., u hosts an ε-move, then we introduce the new rule [q, u] → [p, v] and call the vertex hosting this rule [q, 1, u, v] for simplicity. Again, such vertices are put into Σ and linked to all vertices from Σ . To summarize, we described a new graph-controlled automaton A = (Q , V , δ , F , Γ , Σ , Φ , h ) with Γ = (U , E ), where Q ⊇ Q, V ⊇ V , δ ⊇ δ, Σ , U ⊇ U and E as specified above. As final state set F , we take F = F × U . The final vertices (from Φ ) contain U and all vertices from Σ introduced in steps (a), (d) and (e). Clearly, A is with matrix control. Again, the correctness of the construction is seen by induction.

We can summarize our results as follows.

Theorem 9. Let µ M , µ P , µ rC , µ G ∈ {bu, td }. Then, we have L t (M, µ M ) = L t (P, µ P ) = L t (rC, µ rC ) = L t (G, µ G ) and L t (M, µ M , -ε) ⊆ L t (P, µ P , -ε) = L t (rC, µ rC , -ε) = L t (G, µ G , -ε) .

This result gives rise to the following natural second open question: Is the trivial inclusion L t (G, td , -ε) ⊆ L t (G, td ) strict or not? Recall that for classical finite tree automata, we can dispose of ε-moves as a normal form.

Relation to String Languages

We already introduced the yield operator above that allows us to associate strings to trees and hence string languages to tree languages. Recall Theorem 2.