Minimal strings and graphs accepted by automata
|
1 Introduction 3
2 Shortest accepted strings for two-way finite automata 7
2.1 Two-way finite automata 7
2.2 Shortest accepted strings for direction-determinate automata 9
2.3 Longer shortest strings for automata of the general form 13
2.4 Calculations 17
3 Minimal trees accepted by tree automata and tree-walking automata 20
3.1 Tree-walking and tree automata 20
3.2 Bounds on the size of the minimal accepted tree for a tree automaton ... 23
3.3 Transformation of a nondeterministic tree-walking automaton to a nonde-
terministic tree automaton 27
3.4 Upper bound on the size of the smallest tree accepted by a nondeterministic
tree-walking automaton 33
3.5 Lower bound on the size of the smallest tree accepted by a tree-walking
automaton 38
4 Complexity of the emptiness problem for graph-walking automata and
for tilings with star subgraphs 47
4.1 Graph-walking and star automata 48
4.2 The non-emptiness problem for signatures is in NP 50
4.3 Reducing a star automaton to a signature 56
4.4 Reducing a graph-walking automaton to a signature 58
4.5 Computational complexity of emptiness problems 63
5 Conclusion 73
2 Shortest accepted strings for two-way finite automata 7
2.1 Two-way finite automata 7
2.2 Shortest accepted strings for direction-determinate automata 9
2.3 Longer shortest strings for automata of the general form 13
2.4 Calculations 17
3 Minimal trees accepted by tree automata and tree-walking automata 20
3.1 Tree-walking and tree automata 20
3.2 Bounds on the size of the minimal accepted tree for a tree automaton ... 23
3.3 Transformation of a nondeterministic tree-walking automaton to a nonde-
terministic tree automaton 27
3.4 Upper bound on the size of the smallest tree accepted by a nondeterministic
tree-walking automaton 33
3.5 Lower bound on the size of the smallest tree accepted by a tree-walking
automaton 38
4 Complexity of the emptiness problem for graph-walking automata and
for tilings with star subgraphs 47
4.1 Graph-walking and star automata 48
4.2 The non-emptiness problem for signatures is in NP 50
4.3 Reducing a star automaton to a signature 56
4.4 Reducing a graph-walking automaton to a signature 58
4.5 Computational complexity of emptiness problems 63
5 Conclusion 73
A natural question about automata and related models of computation is how large can be the minimal object an automaton accepts.
The most well-known automata are finite automata that work on strings. A function mapping the size of such an automaton to the maximum length of the shortest accepted string, with the maximum taken over all automata of that size, is a certain complexity measure for a family of automata.
For one-way finite automata, this measure is trivial: the length of the shortest string accepted by a nondeterministic finite automaton (NFA) with n states is at most n — 1: this is the length of the shortest path to an accepting state. On the other hand, Ellul et al. proved that the length of shortest strings not accepted by an n-state NFA is exponential in n. Similar questions were studied for other models and some variants of the problem. Chistikov et al. investigated the length of shortest strings in counter automata. The length of shortest strings in formal grammars under intersections with regular languages was studied by Pierre, and recently by Shemetova et al.. Alpoge et al. investigated shortest strings in intersections of deterministic one-way finite automata (DFA).
The maximum length of shortest strings for deterministic two-way finite automata (2DFA) has been investigated in two recent papers. First of all, from the well-known proof of the PSPACE-completeness of the emptiness problem for 2DFA by Kozen it is understood that the length of the shortest string accepted by an n-state 2DFA can be exponential in n. There is also an exponential upper bound on this length, given by transforming a 2DFA to an NFA: the construction by Kapoutsis uses at most (n+i) = ®(v1™4n) states, and hence the length of the shortest string is slightly less than 4n. Overall, the maximum length of the shortest string is exponential, with the base bounded by 4.
The first attempt to determine the exact base was made by Dobronravov et al., who constructed a family of n-state 2DFA with shortest strings of length Q((-510)n) > Q(1.584n). The automata they have actually constructed belong to a special class of 2DFA: the direction-determinate automata. These are 2DFA with the set of states split into states accessible only by transitions from the right and states accessible only by transitions from the left: in other words, direction-determinate automata always remember the direction of the last transition in their state.
Later, Krymski and Okhotin extended the method of Dobronravov et al. to produce automata of a more general form, with longer shortest accepted strings. They constructed a family of non-direction-determinate 2DFA with shortest strings of length Q((p7)ra) > Q(1.626ra).
These bounds for two-way finite automata are improved in Chapter 2. First, the maximum length of the shortest string accepted by n-state direction-determinate 2DFA is determined precisely as (pj) — 1 = ©(^p= 2n). The upper bound on the length of the shortest string immediately follows from the complexity of transforming direction- determinate 2DFA to NFA, see Geffert and Okhotin. A matching lower bound is proved by a direct construction of a family of n-state automata.
The second result of Chapter 2 is that not remembering the direction helps to accept longer shortest strings: a family of n-state non-direction-determinate automata with shortest strings of length 4 • 2n — 1 is constructed. This is more than what is possible in direction-determinate automata.
Automata that work on strings have well-known generalizations to automata that work on trees with labelled nodes. Deterministic and nondeterministic one-way finite automata (DFA and NFA) become deterministic bottom-up tree automata (DTA) and nondeterministic tree automata (NTA). These are automata that compute states in nodes of a given tree from the leaves to the root. A state in a node is determined (deterministically for DTA and nondeterministically for NTA) by a label of this node and by states already chosen in the children of this node. If an automaton can choose states in all nodes of a tree in this way, then the tree is accepted.
Two-way finite automata are generalized to trees in a different way. They become deterministic and nondeterministic tree-walking automata (DTWA and NTWA). Such an automaton works on a tree by moving along its edges. At every moment, an automaton is in some state and stands at some node. It sees only the label of this node. Depending on its state and on the label of the node, it decides (deterministically or not) to move to one of the neighbouring nodes and changes its state. It can also decide to accept or reject.
It is known that nondeterministic tree automata are equal in power to deterministic bottom-up tree automata, like NFA are equal in power to DFA.
However, there are some differences between automata on strings and on trees. Bojanczyk and Colcombet proved that tree-walking automata are strictly weaker in power than tree automata, and deterministic tree-walking automata are strictly weaker than nondeterminic ones.
The size of minimal trees accepted by tree and tree-walking automata has not been studied yet. But it is known, that the emptiness problem for these automata (whether a given automaton accepts at least one tree) is decidable, and complexity classes for the emptiness problem were determined precisely for these models of computation. Veanes proved that the emptiness problem for nondeterministic tree automata is P-complete. It is proved by Bojanczyk that the emptiness problem for both deterministic and nondeterministic tree-walking automata is EXP-complete.
The size of minimal accepted trees for tree and tree-walking automata is investigated in Chapter 3. For nondeterministic tree automata, the maximum possible size of the minimal accepted tree is determined precisely as the last element in the inductively defined sequence of numbers. This element can be estimated from above as 2rn, where n is the number of states in an automaton, and r is the maximum number of children for a node. If r > 2, then the element can be estimated from below by the rn-th Fibonacci number. And the witness automata for the precise lower bound are bottom-up deterministic.
...
The most well-known automata are finite automata that work on strings. A function mapping the size of such an automaton to the maximum length of the shortest accepted string, with the maximum taken over all automata of that size, is a certain complexity measure for a family of automata.
For one-way finite automata, this measure is trivial: the length of the shortest string accepted by a nondeterministic finite automaton (NFA) with n states is at most n — 1: this is the length of the shortest path to an accepting state. On the other hand, Ellul et al. proved that the length of shortest strings not accepted by an n-state NFA is exponential in n. Similar questions were studied for other models and some variants of the problem. Chistikov et al. investigated the length of shortest strings in counter automata. The length of shortest strings in formal grammars under intersections with regular languages was studied by Pierre, and recently by Shemetova et al.. Alpoge et al. investigated shortest strings in intersections of deterministic one-way finite automata (DFA).
The maximum length of shortest strings for deterministic two-way finite automata (2DFA) has been investigated in two recent papers. First of all, from the well-known proof of the PSPACE-completeness of the emptiness problem for 2DFA by Kozen it is understood that the length of the shortest string accepted by an n-state 2DFA can be exponential in n. There is also an exponential upper bound on this length, given by transforming a 2DFA to an NFA: the construction by Kapoutsis uses at most (n+i) = ®(v1™4n) states, and hence the length of the shortest string is slightly less than 4n. Overall, the maximum length of the shortest string is exponential, with the base bounded by 4.
The first attempt to determine the exact base was made by Dobronravov et al., who constructed a family of n-state 2DFA with shortest strings of length Q((-510)n) > Q(1.584n). The automata they have actually constructed belong to a special class of 2DFA: the direction-determinate automata. These are 2DFA with the set of states split into states accessible only by transitions from the right and states accessible only by transitions from the left: in other words, direction-determinate automata always remember the direction of the last transition in their state.
Later, Krymski and Okhotin extended the method of Dobronravov et al. to produce automata of a more general form, with longer shortest accepted strings. They constructed a family of non-direction-determinate 2DFA with shortest strings of length Q((p7)ra) > Q(1.626ra).
These bounds for two-way finite automata are improved in Chapter 2. First, the maximum length of the shortest string accepted by n-state direction-determinate 2DFA is determined precisely as (pj) — 1 = ©(^p= 2n). The upper bound on the length of the shortest string immediately follows from the complexity of transforming direction- determinate 2DFA to NFA, see Geffert and Okhotin. A matching lower bound is proved by a direct construction of a family of n-state automata.
The second result of Chapter 2 is that not remembering the direction helps to accept longer shortest strings: a family of n-state non-direction-determinate automata with shortest strings of length 4 • 2n — 1 is constructed. This is more than what is possible in direction-determinate automata.
Automata that work on strings have well-known generalizations to automata that work on trees with labelled nodes. Deterministic and nondeterministic one-way finite automata (DFA and NFA) become deterministic bottom-up tree automata (DTA) and nondeterministic tree automata (NTA). These are automata that compute states in nodes of a given tree from the leaves to the root. A state in a node is determined (deterministically for DTA and nondeterministically for NTA) by a label of this node and by states already chosen in the children of this node. If an automaton can choose states in all nodes of a tree in this way, then the tree is accepted.
Two-way finite automata are generalized to trees in a different way. They become deterministic and nondeterministic tree-walking automata (DTWA and NTWA). Such an automaton works on a tree by moving along its edges. At every moment, an automaton is in some state and stands at some node. It sees only the label of this node. Depending on its state and on the label of the node, it decides (deterministically or not) to move to one of the neighbouring nodes and changes its state. It can also decide to accept or reject.
It is known that nondeterministic tree automata are equal in power to deterministic bottom-up tree automata, like NFA are equal in power to DFA.
However, there are some differences between automata on strings and on trees. Bojanczyk and Colcombet proved that tree-walking automata are strictly weaker in power than tree automata, and deterministic tree-walking automata are strictly weaker than nondeterminic ones.
The size of minimal trees accepted by tree and tree-walking automata has not been studied yet. But it is known, that the emptiness problem for these automata (whether a given automaton accepts at least one tree) is decidable, and complexity classes for the emptiness problem were determined precisely for these models of computation. Veanes proved that the emptiness problem for nondeterministic tree automata is P-complete. It is proved by Bojanczyk that the emptiness problem for both deterministic and nondeterministic tree-walking automata is EXP-complete.
The size of minimal accepted trees for tree and tree-walking automata is investigated in Chapter 3. For nondeterministic tree automata, the maximum possible size of the minimal accepted tree is determined precisely as the last element in the inductively defined sequence of numbers. This element can be estimated from above as 2rn, where n is the number of states in an automaton, and r is the maximum number of children for a node. If r > 2, then the element can be estimated from below by the rn-th Fibonacci number. And the witness automata for the precise lower bound are bottom-up deterministic.
...
In Chapter 2 the maximum length of the shortest accepted string for direction-determinate 2DFA has been determined precisely, whereas for 2DFA of the general form, a lower bound of the order 2n has been established. The known upper bound on this length is of the order 4n. It should be noted that the computed values reported in Section 2.4 exceed the theoretical lower bound | • 2n — 1 proved in Section 2.3, and are much less than the known upper bound (n2+J — 1. Thus, the bounds for 2DFA of the general form are still in need of improvement.
Another parameter to be rehned is the size of the alphabet of the construction. Both constructions in Chapter 2 use an alphabet of exponential size. For a hxed alphabet, the maximum known length of shortest strings is Q(1.275ra). Would it be possible to encode the construction in this thesis over a hxed alphabet to surpass this bound? What is the exact maximum length of shortest strings accepted by n-state 2DFAs over an m-symbol alphabet?
The maximum size of smallest accepted trees for tree automata was determined precisely in Chapter 3. But there is a gap between a lower bound 2Q(r'1-618") and an upper bound 2O(rra'3-572n) on the maximum number of nodes in the smallest accepted trees for tree-walking automata with n states, that work on trees with degree of a node at most r. What is an actual constant c in a bound like 20(r'cn) for tree-walking automata?
In Chapter 4, it has been shown that emptiness problems for star automata and for graph-walking automata are decidable. And the computational complexity classes for these problems were determined: the non-emptiness problem for star automata is NP-complete, whereas the non-emptiness problem for graph-walking automata is NEXP- complete. Table 5.1 compares these new results about automata on graphs with the previous results for similar automata on strings and on trees.
In Chapter 4, several upper bounds on the number of nodes in minimal accepted graphs have been obtained. Upper bounds have been proved for graph-walking automata (Corollary 5), and for star automata (Corollary 3). Lower bounds proved for tree-walking and for tree automata in Chapter 3 also apply to graphs. Perhaps it would be possible to prove some better lower bounds using more complicated graphs than trees. Also the upper bounds given in Chapter 4 could be improved.
Star automata in this thesis are a special case of elementary acceptors of Thomas, they are elementary acceptors without conditions on the number of occurrences of each star. Is the emptiness problem for elementary acceptors of Thomas also decidable?
Another parameter to be rehned is the size of the alphabet of the construction. Both constructions in Chapter 2 use an alphabet of exponential size. For a hxed alphabet, the maximum known length of shortest strings is Q(1.275ra). Would it be possible to encode the construction in this thesis over a hxed alphabet to surpass this bound? What is the exact maximum length of shortest strings accepted by n-state 2DFAs over an m-symbol alphabet?
The maximum size of smallest accepted trees for tree automata was determined precisely in Chapter 3. But there is a gap between a lower bound 2Q(r'1-618") and an upper bound 2O(rra'3-572n) on the maximum number of nodes in the smallest accepted trees for tree-walking automata with n states, that work on trees with degree of a node at most r. What is an actual constant c in a bound like 20(r'cn) for tree-walking automata?
In Chapter 4, it has been shown that emptiness problems for star automata and for graph-walking automata are decidable. And the computational complexity classes for these problems were determined: the non-emptiness problem for star automata is NP-complete, whereas the non-emptiness problem for graph-walking automata is NEXP- complete. Table 5.1 compares these new results about automata on graphs with the previous results for similar automata on strings and on trees.
In Chapter 4, several upper bounds on the number of nodes in minimal accepted graphs have been obtained. Upper bounds have been proved for graph-walking automata (Corollary 5), and for star automata (Corollary 3). Lower bounds proved for tree-walking and for tree automata in Chapter 3 also apply to graphs. Perhaps it would be possible to prove some better lower bounds using more complicated graphs than trees. Also the upper bounds given in Chapter 4 could be improved.
Star automata in this thesis are a special case of elementary acceptors of Thomas, they are elementary acceptors without conditions on the number of occurrences of each star. Is the emptiness problem for elementary acceptors of Thomas also decidable?
