Optimal Simulations Between Unary Automata^{⋆}

Carlo Mereghetti and Giovanni Pighizzini

Dipartimento di Scienze dell’Informazione – Università degli Studi di Milano via Comelico 39 – 20135 Milano, Italy – {mereghc,pighizzi}@dsi.unimi.it

Abstract. We consider the problem of computing the costs — in terms of states — of optimal simulations between different kinds of finite automata recognizing unary languages. Our main result is a tight simulation of unary n–state two–way nondeterministic automata by O(e^{\sqrt{n ln n}})– state one–way deterministic automata. In addition, we show that, given a unary n–state two–way nondeterministic automaton, one can construct an equivalent O(n^{2})–state two–way nondeterministic automaton performing both input head reversals and nondeterministic choices at the endmarkers only. Further results on simulating unary alternating finite automata are pointed out. Our results give answers to some questions left open in the literature.

1 Introduction

Finite automata [RS59] are one of the simplest computational models. Many of their properties have been widely investigated. Notwithstanding their simplicity, some important questions concerning finite automata are still open. In particular, not all the costs of optimal simulations between different kinds of automata are known. For instance, we recall the problem, proposed in 1978 by W. Sakoda and M. Sipser [SS78], of proving the existence of a polynomial — with respect to the number of states — simulation of two–way nondeterministic finite automata (2nfa, for short) by two–way deterministic finite automata (2dfa). As pointed out by P. Berman and A. Lingas in [BL77], such a problem is not only interesting per se, but is tightly related to the DLOGSPACE = NLOGSPACE question.

On the other hand, the costs of other simulations have been precisely stated. Besides the optimal simulation of n–state one–way nondeterministic finite automata (1nfa) by 2^{n}–state one–way deterministic finite automata (1dfa), we can mention the optimal simulation of 2dfa’s by 1dfa’s (O(2^{n log n}) states), of 2nfa’s by 1dfa’s (O(2^{n^{2}}) states), and of one–way alternating finite automata (1afa) by 1dfa’s (O(2^{2^{n}}) states). (For lack of space, we do not provide credits for all these results. The reader can find precise references in [Chr86].)

It is important to stress that the optimality of such simulations has been established by witness languages built over alphabets of two or more symbols. As a matter of fact, the situation turns out to be quite different whenever we

⋆ This work is partially supported by Ministero dell’Università e della Ricerca Scientifica e Tecnologica (MURST).

restrict to unary automata, i.e., automata with a single letter input alphabet. For example, we know that O(e^{\sqrt{n ln n}}) states suffice in order to simulate a unary n– state 1nfa or 2dfa by a 1dfa. Furthermore, a unary n–state 1nfa can be simulated by a 2dfa having O(n^{2}) many states. All these results and their optimality have been proved in 1986 by M. Chrobak [Chr86].

In this paper, we further deepen the study of optimal simulations between different kinds of unary automata. The first part of the paper is devoted to study 2nfa’s. We closely analyze the structure of their computation paths. In particular, using number theoretical arguments, we show that, for sufficiently large inputs, it is possible to consider only computation paths in which states are repeated in a very regular way. This enables us to state our main result concerning the optimal simulation of unary 2nfa’s via 1dfa’s: each unary n–state 2nfa can be simulated by a 1dfa with O(e^{\sqrt{n ln n}}) states. Note that the complexity is the same as the above mentioned optimal simulations of 1nfa’s and 2dfa’s by 1dfa’s. Thus, the simultaneous elimination of both two–way motion and nondeterminism has the same cost as the elimination of either of them. As another consequence of our analysis of 2nfa’s, we are able to prove that each n–state unary 2nfa can be simulated by a 2nfa with O(n^{2}) states which reverses the input head direction and makes nondeterministic decisions only when the input head visits the left or the right end of the input. This result can be regarded as a further contribution to a better understanding of the 2nfa model. In particular, it could be useful in the investigation of the Sakoda–Sipser open question recalled above, at least for unary inputs.

In the second part of the paper, we study the relationships between unary 1afa’s and dfa’s, nfa’s. This problem was proposed in [Chr86], and partly solved in [Bir93], where it is proved that 2^{n} states are necessary for 2nfa’s to simulate n–state 1afa’s. We point out an optimal simulation of n–state unary 2nfa’s by O(\sqrt{n ln n})–state 1afa’s.

By combining our results with those in the literature, we are able to draw an almost complete description of the costs of optimal simulations between the different types of unary automata here considered. We do not list all the resulting optimal bounds, which can be better understood by observing Figure 1.

2 Preliminary definitions and results

In this section, we recall definitions and results used throughout the paper. Given an alphabet Σ, Σ^{∗} denotes the set of strings on Σ, with the empty string. Given a string x ∈ Σ^{∗}, |x| denotes its length. A language L ⊆ Σ^{∗} is said to be unary (or tally) whenever L is built over a single letter alphabet (usually, Σ = {1}). We assume that the reader is familiar with one–way/two–way, deterministic/nondeterministic finite automata (1dfa, 2dfa, 1nfa, 2nfa, for short). For a detailed exposition see, e.g., [HU79]. Moreover, we also assume familiarity with one–way/two–way alternating finite automata (1afa, 2afa, for short), as presented in [CKS81,FJY90]. We stipulate that input strings for two–way

[figure: 1afa; 2dfa; 1dfa; 1nfa; 2nfa; n; n; n; log n; e^{\sqrt{n ln n}}; n^{2}; \sqrt{n ln n}; n; e^{\sqrt{n ln n}}; e^{\sqrt{n ln n}}; n; \sqrt{n ln n}; e^{\sqrt{n ln n}}; ?; \sqrt{n ln n}; e^{\sqrt{n ln n}}; 2^{n}; 2^{n}; 2^{n}; 2^{n}]

Fig. 1. Costs of the optimal simulations between different kinds of unary automata. An arc labeled f(n) from a vertex x to a vertex y means that a unary n–state automaton of type x can be simulated by a O(f(n))–state automaton of type y.

devices are enclosed between a left and a right endmarker symbol. The left endmarker is contained in the 0th input square. A finite automaton is said to be unary whenever the input alphabet contains exactly one symbol. Our automata are assumed to be complete, i.e., their transition functions are total.

We need few notions of graph theory. A directed graph (digraph) G is strongly connected if there exists a directed path between any two vertices. A strongly connected component of G is a sub–graph of G which is strongly connected, and not contained in any other strongly connected sub–graph. Following [Ber85], we call elementary any cycle in which no vertex is encountered more than once (except, of course, the initial vertex which is also the terminal vertex). Our estimations on simulation costs rely on some number theoretical topics that are now to be quickly presented. First, some notation. We let Z^{+} (Z^{−}) the set of positive (negative) integers, and Z the set of whole integers. Natural numbers are denoted with N. For any z ∈ Z, |z| denotes its absolute value. For any z ∈ Z^{+}, ln z denotes the natural logarithm of z, while log z is the logarithm of z taken to the base 2. The greatest common divisor of a_{1}, …, a_{s} ∈ Z writes as gcd(a_{1}, …, a_{s}). Their least common multiple is denoted by lcm(a_{1}, …, a_{s}). Both gcd and lcm are, actually, meant to be taken on |a_{1}|, …, |a_{s}|.

In the simulation of unary automata, a crucial role is played by the function F (n) = max {lcm(x_{1}, …, x_{s}) | x_{1}, …, x_{s} ∈ Z^{+} and x_{1} + … + x_{s} = n}. Evaluating the growth of F (n) is known as Landau’s problem, and is addressed in [Chr86]. For our purposes, it is enough to know that

Lemma 1. F (n) = O(e^{\sqrt{n ln n}}).

The other arithmetical tool we shall make use of is the theory of linear Diophantine equations. We consider equations in the form a_{1}x_{1} +…+a_{s}x_{s} = z, where a_{1}, …, a_{s}, z ∈ Z, and x_{1}, …, x_{s} are variables. It is well–known that, whenever x_{1}, …, x_{s} range over Z, the set of integers in the form a_{1}x_{1} + … + a_{s}x_{s} coincides with the set of all integral multiples of gcd(a_{1}, …, a_{s}). Instead, whenever x_{1}, …, x_{s} range over N, one can prove the following

Lemma 2. Let a_{1}, …, a_{s} ∈ Z, with |a_{i}| ≤ n, and let

X = {a_{1}x_{1} + … + a_{s}x_{s} | x_{1}, …, x_{s} ≥ 0}.

Define X^{+} = X ∩ {z ∈ Z^{+} | z > n^{2}}, and X^{−} = X ∩ {z ∈ Z^{−} | z < −n^{2}}. Then, X^{+} ≠ ∅ (X^{−} ≠ ∅) if and only if there exists at least one positive (negative) a_{i}. Moreover, if X^{+} ≠ ∅ (X^{−} ≠ ∅), then it coincides with the set of positive (negative) multiples of gcd(a_{1}, …, a_{s}) greater than n^{2} (smaller than −n^{2}).

The proof of Lemma 2 easily follows from results presented in [Chr86, Sec. 3], where the reader can find more on linear Diophantine equations. Moreover, as a routine exercise, one can show that

Lemma 3. Let a_{1}, …, a_{s} ∈ Z^{+}, with a_{i} ≤ n, and let z ≥ 0. If the equation a_{1}x_{1} + a_{2}x_{2} + … + a_{s}x_{s} = z has a solution over the natural numbers, then it has a solution over natural numbers satisfying a_{2}x_{2} + … + a_{s}x_{s} ≤ 2n^{2}.

3 Computation paths of 2nfa’s and simulation by 1dfa’s

In this section, we focus on unary 2nfa’s. By discovering some regularities in the structure of their computation paths, we show that any unary language L accepted by a 2nfa with n states, forms a definitively periodic set of period p = O(e^{\sqrt{n ln n}}). More precisely, we find an integer \overline{k} = O(n^{2}) such that, for any k ≥ \overline{k}, 1^{k} ∈ L if and only if 1^{k+p} ∈ L. This immediately leads to a O(e^{\sqrt{n ln n}}) simulation of unary 2nfa’s via 1dfa’s. The optimality of such a simulation is a direct consequence of a result in [Chr86]. The results here obtained will be useful also in the next section, where we show that by just squaring the number of the states, it is possible to consider 2nfa’s with a very particular structure.

To state our results, we need some tools to examine computations over unary inputs. Specifically, we refer to three lemmas that V. Geffert proved in [Gef91] for two–way nondeterministic Turing machines accepting unary languages in sublogarithmic space. We are now going to reformulate these lemmas within the realm of unary 2nfa’s. Their validity in this new form comes straightforwardly from the originals.

¿From now on, we always refer to a unary 2nfa A with n states.

The first lemma says that each computation path of A beginning and ending at the same input square and visiting neither of the endmarkers, can be replaced by an equivalent computation path not moving the input head more than n^{2} positions to the right (or left).

Lemma 4. (U–Turn) Let m > 2n^{2}, and suppose there exists a computation path of A on input 1^{m} where (a) the first state is q_{1} with the input head at a position i, (b) the last state is q_{2} with the input head at the same position, and (c) the input head never moves to the left (right) of i, neither it visits the right (left) endmarker. Then, there also exists a computation path on input 1^{m} satisfying (a), (b) and (c), where the input head never moves farther than n^{2} positions to the right (left) of i.

The second lemma states that we can freely “shift” a computation path that never visits the endmarkers to any position of the input tape, provided both the initial and final input head positions lie sufficiently far from the endmarkers.

Lemma 5. (Position Independence) Let m > 2n^{2}, and suppose there exists a computation path of A on 1^{m} beginning in the state q_{1} with the input head at a position i, ending in the state q_{2} with the input head at the position i + ℓ, ℓ ≥ 0, and visiting neither of the endmarkers. Then, there also exists a computation path on input 1^{m} beginning in q_{1} with the input head at a position j, and ending in the state q_{2} with the input head at the position j +ℓ, for each n^{2} < j ≤ j +ℓ ≤ m − n^{2}. A similar condition can be formulated for moving to the left.

The next lemma defines the structure of the computation paths that traverse the entire input. We give a new proof of this result for unary 2nfa’s, relying on some properties of linear Diophantine equations. This approach enables us to reduce the O(n^{4}) upper bound on s_{1} and s_{2} given in [Gef91] to O(n^{2}). We point out that the same improvement has been obtained independently by Geffert, using a different argument [Gef97]. This improvement will be useful in the quadratic simulation stated in Theorem 13.

In the following, by loop of length ℓ, we mean a computation path beginning in a state p with the input head at a position i, and ending in the same state with the input head at the position i + ℓ.

Lemma 6. (Dominant Loop) Let m > 2n^{2}, and suppose the input 1^{m} is traversed from left to right by a computation path Π of A beginning in the state q_{1}, ending in the state q_{2}, and such that the endmarkers are visited only in q_{1} and q_{2}. Then, 1^{m} can be traversed by an equivalent computation path such that A, having traversed the left endmarker and s_{1} positions, gets into a loop of length ℓ, which starts in a state p and is repeated λ times, then traverses the remaining s_{2} input squares, and finally gets the right endmarker, for some s_{1}, s_{2}, ℓ satisfying 1 ≤ ℓ ≤ n, s_{1}, s_{2} ≥ n^{2}, and s_{1} + s_{2} ≤ 5n^{2}. (Note that m = s_{1} + λℓ + s_{2}.) The same result holds for computation paths traversing the input from right to left.

Proof. Define the digraph G = (Q, E), where (q′, q′′) ∈ E if and only if there is a computation path which passes through q′ with the input head at a position 0 ≤ i ≤ m, ends in q′′ with the input head at the position i + 1, and never visits either the endmarkers or the (i + 1)th input square in the intermediate steps. (Notice that, by Lemma 5, for sufficiently large inputs, the graph G does not depend on the input length.)

Let C be a path of length x in G, from q′ to q′′. By repeatedly eliminating from C elementary circuits of G, we finally obtain a circuit–free path from q′ to q′′ of length x_{0} ≤ n. Let {a_{1}, …, a_{t}} be the set of the lengths of those elementary circuits of G eliminated from C in the previous process. Notice that a_{i} ≤ n, for 1 ≤ i ≤ t. Then, x = x_{0} + a_{1}x_{1} + … + a_{t}x_{t}, where, for 1 ≤ i ≤ t, x_{i} > 0 is the number of times elementary circuits of length a_{i} has been eliminated from C.

By Lemma 3, there exist x′_{1}, …, x′_{t} ≥ 0 such that x = x_{0} + a_{1}x′_{1} + a_{2}x′_{2} + … + a_{t}x′_{t}, and a_{2}x′_{2} + … + a_{t}x′_{t} ≤ 2n^{2}. Hence, we can devise a new path C′ in G of length x, from q′ to q′′, containing a circuit of length a_{1} which is repeated x′_{1} times, and where the length of the sub–path of C′ outside such a circuit is x_{0} + a_{2}x′_{2} + … + a_{t}x′_{t} ≤ 2n^{2} + n. Using Lemma 5, it is easy to see that we can associate with C′ a computation path in A from the state q′ to the state q′′, which moves the input head from a certain position j to the position j + x, repeats x′_{1} consecutive times a loop of length a_{1}, and traverses no more than 2n^{2} + n input tape positions outside such a loop, provided that n^{2} < j < j + x ≤ m − n^{2}.

Now, consider the given computation path Π. For 0 ≤ i ≤ m+1, let p_{i} be the state of A when the input head visits the ith input square for the first time along Π. Thus, p_{0} = q_{1} and p_{m+1} = q_{2}. Notice that (p_{i}, p_{i+1}) ∈ E, for 0 ≤ i ≤ m.

Following the above reasoning, we can associate with the path in G which traverses vertices p_{n^{2}+1}, p_{n^{2}+2}, …, p_{m−n^{2}}, a computation path Π′ in A beginning in the state p_{n^{2}+1} with the input head on the (n^{2} + 1)th square, ending in the state p_{m−n^{2}} with the input head on the (m − n^{2})th square, where a loop of length ℓ(=a_{1}) from a state p is repeated λ(=x′_{1}) times, and where the input positions traversed outside this loop are at most 2n^{2} + n.

In conclusion, we can replace in the original path Π the part of the computation from state p_{n^{2}+1}, with the input head on the (n^{2} + 1)th square, to state p_{m−n^{2}}, with the input head on the (m − n^{2})th square, with Π′. We get a computation path of A that starts from q_{1} with the input head at the left endmarker, traverses the left endmarker and s_{1} ≥ n^{2} input squares, gets λ times into a loop of length 1 ≤ ℓ ≤ n, traverses s_{2} ≥ n^{2} input squares, and finally reaches the right endmarker in the state q_{2}. It is easy to see that s_{1} + s_{2} = 2n^{2} + x_{0} + a_{2}x′_{2} + … + a_{t}x′_{t} ≤ 5n^{2}. ⊓ ⊔

Now, we closely study loops in computation paths. Our goal is to show that we can focus only on some loops or, more precisely, only on some lengths. By weighted digraph, we mean a digraph where edges have weights from {−1, 0, 1}. The weight of a path is the sum of weights of the edges the path consists of.

Lemma 7. Let G = (V, E) be a strongly connected weighted digraph with |V | = n, and let {a_{1}, …, a_{s}} be the set of weights of the s elementary circuits in G. For each v ∈ V, define X_{v} as the set of weights of all circuits containing v. If there exists at least one a_{i} > 0 (a_{i} < 0) then the set X_{v} and the set of positive (negative) multiples of gcd(a_{1}, …, a_{s}) agree on the elements greater than 3n^{2} (less than −3n^{2}, respectively).

Proof. Since each circuit is the sum of elementary circuits, x ∈ X_{v} implies x = a_{1}x_{1} + … + a_{s}x_{s}, for some x_{1}, …, x_{s} ≥ 0. Then, x is an integral multiple of gcd(a_{1}, …, a_{s}).

Conversely, if x is a sufficiently large multiple of gcd(a_{1}, …, a_{s}), then, by Lemma 2, x = a_{1}x_{1} + … a_{s}x_{s}, for some x_{1}, …, x_{s} ≥ 0. This fact does not imply the existence of one circuit of weight x in the graph. For instance, if s = 3, x_{1} = 1, x_{2} = 0, x_{3} = 1, and the circuits of weight a_{1} and a_{3} are connected only via the circuit of weight a_{2}, then x_{1}, x_{2}, x_{3} define two disjoint circuits but cannot define a circuit in G.

In order to solve this problem, we shall prove the existence of a circuit of weight x which visits all vertices of G. To this aim, we first observe that it is easy to construct a circuit C_{0}, visiting all vertices of G, and such that its weight x_{0} satisfies |x_{0}| < 2n^{2}. Notice that x_{0} = a_{1}x_{1}+…+a_{s}x_{s}, for some x_{1}, …, x_{s} ≥ 0, and hence x_{0} = k_{0} gcd(a_{1}, …, a_{s}), for some k_{0} ∈ Z. Given x = k gcd(a_{1}, …, a_{s}), for a k ∈ Z, with |x| > 3n^{2}, let z = x − x_{0} = (k − k_{0}) gcd(a_{1}, …, a_{s}). Then |z| = |x − x_{0}| ≥ |x| − |x_{0}| > n^{2}. By Lemma 2, and by observing that, for 1 ≤ i ≤ s, |a_{i}| ≤ n, this implies that z = a_{1}z_{1}+…+a_{s}z_{s}, for some z_{1}, …, z_{s} ≥ 0. Finally, by padding the circuit C_{0} with a suitable amount of elementary circuits corresponding to coefficients z_{1}, …, z_{s}, we obtain a circuit of weight x in G. ⊓ ⊔

Let us now consider the weighted digraph A consisting of the digraph representing our automaton A, after removing transitions on the endmarkers, where with each edge is associated a weight representing the movement of the input head in the corresponding transition. Namely, the weight −1, 1, 0 is associated with each transition where the input head is moved one position left, right, or kept stationary, respectively. Notice that any circuit of weight ℓ in A represents a loop of length ℓ in the automaton A. By applying Lemma 7 to such a weighted digraph, we can easily obtain the following:

Lemma 8. Let p ∈ Q, and let g be the greatest common divisor of the weights of the circuits in the strongly connected component of A containing p. Let X_{p}^{+} the set of integers x ≥ 3n^{2} such that the automaton A, starting in the state p, with the input head at the ith input square can reach the (i+x)th input square in the same state p, without visiting the endmarkers, provided that i + x < m − n^{2}. If X_{p}^{+} ≠ ∅, then it coincides with the set of all integral multiples of g greater than 3n^{2}. A symmetrical result holds for the set X_{p}^{−} defined in the obvious way.

The following result is crucial in order to obtain our simulations:

Theorem 9. There exists a set {ℓ_{1}, …, ℓ_{s}} ⊆ {1, …, n} with ℓ_{1} + … + ℓ_{s} ≤ n, such that, for any m > 8n^{2}, if the input 1^{m} can be traversed from left to right by a computation path of A beginning in a state q_{1}, ending in a state q_{2}, and where the endmarkers are visited only in q_{1} and q_{2}, then there exists an index i ∈ \{1, …, s\} such that, for any μ > \frac{8n^{2}−m}{ℓ_{i}}, there is a computation path from q_{1} to q_{2} which traverses from left to right the input 1^{m+μℓ_{i}}.

Proof. Let {ℓ_{1}, …, ℓ_{s}} be the set of the greatest common divisors of the weights of circuits of all the strongly connected components of the digraph A. Thus, ℓ_{i} is bounded by the number of states of the ith strongly connected component, and, since strongly connected components are disjoint, ℓ_{1} + ℓ_{2} + … + ℓ_{s} ≤ n.

Now, consider s_{1}, s_{2}, ℓ, λ, p as in Lemma 6. Let ℓ_{i} ∈ {ℓ_{1}, …, ℓ_{s}} be the greatest common divisor of the weights of the circuits in the strongly connected component of A containing p. By Lemma 8, the set of integers x > 3n^{2} for which there is a path from p to itself that visits neither of the endmarkers and which moves the input head from the ith to the (i + x)th square, coincides with the multiples of ℓ_{i} greater than 3n^{2}. This leads us to conclude that for integers η > \frac{3n^{2}}{ℓ_{i}}, there exists a path traversing the whole input 1^{s_{1}+ηℓ_{i}+s_{2}} from q_{1} to q_{2}.

Now, given μ > \frac{8n^{2}−m}{ℓ_{i}} and η = μ + \frac{λℓ}{ℓ_{i}}, we have η > \frac{8n^{2}−s_{1}−λℓ−s_{2}+λℓ}{ℓ_{i}} ≥ \frac{3n^{2}}{ℓ_{i}}, and s_{1} + ηℓ_{i} + s_{2} = m + μℓ_{i}. Then, there exists a path traversing from left to right the whole input 1^{m+μℓ_{i}} from state q_{1} to state q_{2}. ⊓ ⊔

In the following theorem, we suitably adopt the well–known n → n + n! pumping technique. In the light of Theorem 9, we are able to state a bound on the length of the pumped part which enables us to show that unary languages accepted by n–state 2nfa’s form definitively periodic sets of period O(e^{\sqrt{n ln n}}):

Theorem 10. Let L be a unary language accepted by a n–state 2nfa. Then, there exists a constant ℓ bounded by O(e^{\sqrt{n ln n}}) such that, for any integer k > 8n^{2},

1^{k} ∈ L if and only if 1^{k+ℓ} ∈ L.

Proof. Let {ℓ_{1}, …, ℓ_{s}} as in Theorem 9, and let ℓ = lcm(ℓ_{1}, …, ℓ_{k}). By Lemma 1, ℓ is bounded above by O(e^{\sqrt{n ln n}}).

Suppose 1^{k+ℓ} ∈ L, and let C be an accepting computation path of A on 1^{k+ℓ}. Along C, consider r_{0}, r_{1}, … r_{p}, the sequence of all states in which the input head scans either of the endmarkers. For 1 ≤ j ≤ p, we have the following possibilities:

– In both r_{j−1} and r_{j}, the input head scans the left (right) endmarker. By Lemma 4, we can suppose that this can be done by visiting no more than n^{2} input squares to the right (left). Thus, the part of the computation from r_{j−1} to r_{j} can be simulated even on the input 1^{k}.

– In r_{j−1} the input head scans the left (right) endmarker, while in r_{j} it scans the right (left) endmarker. By Theorem 9, for some ℓ_{i}, we can replace the computation path from r_{j−1} to r_{j} on input 1^{k+ℓ}, with a computation path from r_{j−1} to r_{j} on input 1^{k+ℓ+μℓ_{i}}, provided that μ is greater than \frac{8n^{2}−(k+ℓ)}{ℓ_{i}}. Choose μ = μ_{i} = −\frac{ℓ}{ℓ_{i}}. Since k > 8n^{2}, μ_{i} satisfies the previous limitation. Thus, we obtain a computation path which, on input 1^{k}, traverses across the entire input from left to right (right to left).

From these observations, it is easy to conclude that A accepts even the input 1^{k}. The proof of the converse is similar. ⊓ ⊔

As an immediate consequence, we are able to state our main result:

Corollary 11. Each unary n–state 2nfa can be simulated by a O(e^{\sqrt{n ln n}})–state 1dfa.

It is possible to show that this simulation cannot be improved. Actually, a stronger result can be stated, which proves the optimality of all O(e^{\sqrt{n ln n}}) bounds in Figure 1:

Theorem 12. [Chr86, Th. 6.1] For each integer n, there exists a unary 2dfa with n states such that each equivalent 1nfa requires Ω(e^{\sqrt{n ln n}}) states.

The trivial simulations of cost n in Figure 1 are easily seen to be tight. For the optimal quadratic simulation of unary 1nfa’s by 2dfa’s see [Chr86, Sec. 6].

4 Bringing reversals and nondeterminism at the endmarkers

In [GI79,GI82], E. Gurari and O. Ibarra prove that each unary 2nfa can be transformed into an equivalent 2nfa performing input head reversals only at the endmarkers. Now, using the analysis in Section 3, we are able to strengthen this result. We show that not only reversals, but also nondeterminism can be brought at the endmarkers, by just squaring the number of states.

Theorem 13. Each unary n–state 2nfa A can be simulated by a O(n^{2})–state 2nfa A′, performing input head reversals and nondeterministic choices only when the input head scans either of the endmarkers.

Proof. First observe that, by adding one more state, we can assume that A accepts with the input head parked on the left endmarker. Now, we informally describe how A′ performs its computation on input 1^{m}.

In a first scan, A′ deterministically checks whether m ≤ 8n^{2} and, in this case, it immediately accepts if and only if 1^{m} is accepted by A. We can assume that at the end of this phase, which requires O(n^{2}) states, the input head is positioned again on the left endmarker. At this point, if m > 8n^{2}, the second part of the simulation starts from the initial state of A.

We briefly explain what happens when A′ simulates the behavior of A from a state q_{1}, with the input head scanning the left endmarker (a similar behavior can be described starting from the right endmarker). A′ nondeterministically chooses one of the following operations: (a) simulation of a “U–Turn” of A; (b) simulation of a left–to–right traversal of the input.

Since m > 8n^{2}, by Lemma 4 the simulation (a) does not depend on the input length. Hence, each U–Turn from the left endmarker can be “embedded” in the transition function of A′. Namely, it can be replaced by one stationary move. This part of the simulation does not require new states.

Now, we describe how to perform simulation (b). (By a mod b, we denote the remainder of the integer division of a by b.) Let {ℓ_{1}, …, ℓ_{s}} be the set introduced in Theorem 9, with respect to the automaton A. We observe that given an index i ∈ {1, …, s}, two integers m′, m′′ with 8n^{2} < m′ < m′′, m′ mod ℓ_{i} = m′′ mod ℓ_{i}, and two states q_{1}, q_{2} of A, there exists a computation path from q_{1} to q_{2} scanning the whole input 1^{m′} if and only if there exists a computation path from q_{1} to q_{2} scanning the whole input 1^{m′′}. In fact, m′ = h′ℓ_{i} + k, m′′ = h′′ℓ_{i} + k, for some 0 < h′ ≤ h′′ and 0 ≤ k < ℓ_{i}. Thus m′ = m′′ + μℓ_{i}, where μ = h′ − h′′ = \frac{m′−k−m′′+k}{ℓ_{i}} > \frac{8n^{2}−m′′}{ℓ_{i}}. Hence, by Theorem 9, from a path from q_{1} to q_{2} scanning the whole input 1^{m′′}, we can obtain a path from q_{1} to q_{2} scanning the whole input 1^{m′}. The proof of the converse is similar.

As a consequence of this observation, it turns out that, given the state q_{1} of A and the input length m, the set of states reachable by A after traversing from left to right the input depends only on the starting state q_{1} and on the set of pairs {(ℓ_{i}, m mod ℓ_{i}) | i = 1, …, s}. Hence, the simulation of the left–to–right traversal is performed as follows:

– A′ nondeterministically selects an index i ∈ {1, …, s};

– A′ scans the input tape, counting the input length m modulo ℓ_{i};

– when the input head reaches the right endmarker, A′ nondeterministically selects one of the states associated with the starting state q_{1} and the pair (ℓ_{i}, m mod ℓ_{i}).

Note that A′ makes nondeterministic choices only at the endmarkers. During the traversal, A′ should remember the starting state q_{1}, the index i ∈ {1, …, s} of the chosen loop, and an integer 0 ≤ k < ℓ_{i}, used to count modulo ℓ_{i}. Hence, for each starting state q_{1}, ℓ_{1} + … + ℓ_{s} ≤ n states suffice. Thus, this part of the simulation uses O(n^{2}) states. ⊓ ⊔

5 1afa’s versus other models

In this section, we analyze the cost of simulating unary 1afa’s by means of other models of automata, and the costs of converse reductions. We begin by considering the simulations between 1afa’s and 1dfa’s:

Theorem 14. The class of unary languages accepted by n–state 1afa’s coincides with the class of unary languages accepted by 2^{n}–state 1dfa’s.

Proof. See [Bir93, Thm. 2.1], and use the fact that x = x^{R}, for x ∈ {1}^{∗}.

As an immediate consequence, we get the following:

Corollary 15. Let L be a unary language, for which the minimum 1dfa has n states. Then, every 1afa accepting L requires at least ⌈log n⌉ states.

The simulation of 1afa’s via 1dfa’s, stated in Theorem 14, is optimal. Actually, a stronger result holds:

Theorem 16. [Bir93, Fact 3.2] For each integer n, there exists a unary 1afa with n states such that each equivalent 2nfa requires Ω(2^{n}) states.

Hence, as already shown in [Bir93], 1afa’s and 2dfa’s are not polynomially equivalent, as conjectured in [Chr86]. However, we can show that the converse simulation, namely 2dfa’s (and, more generally, 2nfa’s) via 1afa’s, is sublinear:

Theorem 17. Each unary n–state 2nfa A can be simulated by a O(\sqrt{n ln n})– state 1afa.

Proof. By Corollary 11, we get from A an equivalent 1dfa with O(e^{\sqrt{n ln n}}) states. By Theorem 14, there exists even an equivalent 1afa with O(\sqrt{n ln n}) states. ⊓ ⊔

The simulation in Theorem 17 is optimal, even in case of 1nfa’s and 2dfa’s:

Theorem 18. For each integer n, there exists a unary 1nfa and a unary 2dfa with n states such that each equivalent 1afa requires Ω(\sqrt{n ln n}) states.

Proof. By [Chr86, Th. 4.5], for each n there is a unary n–state 1nfa A such that each 1dfa recognizing L(A) requires Ω(e^{\sqrt{n ln n}}) states. By Corollary 15, this implies that each 1afa accepting L(A) has at least Ω(\sqrt{n ln n}) states. Furthermore, the language L(A) is accepted even by a unary n–state 2dfa [Chr86, Th. 5.2]. ⊓ ⊔

Acknowledgments. The authors wish to thank anonymous referees for helpful comments and remarks. In particular, a referee pointed out contribution [Bir93]. Moreover, authors kindly acknowledge Viliam Geffert for stimulating discussions.

References

[Ber85] C. Berge. Graphs and Hypergraphs. North–Holland, 1985.

[Bir93] J.-C. Birget. State-complexity of finite-state devices, state compressibility and incompressibility. Mathematical Systems Theory, 26:237–269, 1993.

[BL77] P. Berman and A. Lingas. On the complexity of regular languages in terms of finite automata. Technical Report 304, Polish Academy of Sciences, 1977.

[Chr86] M. Chrobak. Finite automata and unary languages. Theoretical Computer Science, 47:149–158, 1986.

[CKS81] A. Chandra, D. Kozen, and L. Stockmeyer. Alternation. Journal of the ACM, 28:114–133, 1981.

[FJY90] A. Fellah, H. Jürgensen, and S. Yu. Constructions for alternating finite automata. International J. Computer Math., 35:117–132, 1990.

[Gef91] V. Geffert. Nondeterministic computations in sublogarithmic space and space constructibility. SIAM J. Computing, 20:484–498, 1991.

[Gef97] V. Geffert, 1997. Private communication.

[GI79] E. Gurari and O. Ibarra. Simple counter machines and number–theoretic problems. Journal of Computer and System Sciences, 19:145–162, 1979.

[GI82] E. Gurari and O. Ibarra. Two–way counter machines and Diophantine equations. Journal of the ACM, 29:863–873, 1982.

[HU79] J. Hopcroft and J. Ullman. Introduction to automata theory, languages, and computation. Addison–Wesley, Reading, MA, 1979.

[RS59] M.O. Rabin and D. Scott. Finite automata and their decision problems. IBM J. Res. Develop, 3:114–125, 1959.

[SS78] W. Sakoda and M. Sipser. Nondeterminism and the size of two–way finite automata. In Proc. 10th ACM Symposium on Theory of Computing, pages 275–286, 1978.