The time complexity of 1-limited automata is investigated from a descriptional complexity view point. Though the model recognizes regular languages only, it may use quadratic time in the input length. We show that, with a polynomial increase in size and preserving determinism, each 1-limited automaton can be transformed into an halting lineartime equivalent one. We also obtain polynomial transformations into related models, including weight-reducing Hennie machines, and we show exponential gaps for converse transformations in the deterministic case.
? This work is an extended abstract of the conference paper [
Unfortunately, Hennie proved that it is undecidable, given a deterministic
one-tape Turing machine, to check whether it works in linear time over all input
strings, namely, whether it is actually a Hennie machine. To avoid this drawback,
Pr•†a proposed a variant of Hennie machine, called weight-reducing Hennie
machine, in which the time limitation is syntactic [
By contrast to Hennie machines, the d-limited automata (d-la) introduced
by Hibbard, restrict nondeterministic linear bounded automata by allowing
overwriting of each tape cell during its rst d visits only, for some xed d 0 [
Example 1. We consider the language
Ln = fx0x1
xk j k 2 N; xi 2 fa; bgn; #fi > 0 j xi = x0g is oddg.
A deterministic 1-la An may recognize Ln as follows. It rst overwrites the factor x0, replacing each input symbol with a marked copy. Then, An repeats a subroutine which overwrites a factor xi with some xed symbol ], while checking in the meantime whether xi equals x0 or not. This can be achieved as follows. Before overwriting the j-th symbol of xi, rst, An, with the help of a counter modulo n, moves the head leftward to the position j of x0 and stores the unmarked scanned symbol in its nite control; second, it moves the head rightward until reaching the position j of xi, namely, the leftmost position that has not been overwritten so far. At this point, An compares the scanned symbol ( i.e., the j-th symbol of xi) with (i.e., the j-th symbol of x0). By counting modulo 2 the number of factors equal to x0, and nally checking that the input string has length multiple of n, An can decide the membership of the input to Ln.
It is possible to implement An with a number of states linear in n and # +1 working symbols. Since for each position of a factor xi, i > 0, the head has to move back to the factor x0, we observe that An works in quadratic time in the length of the input string.
For each d 2, Hibbard proved that d-la recognize exactly the class of
context-free languages . He furthermore showed the existence of an innite
hierarchy of deterministic d-la, whose rst level ( i.e., corresponding to deterministic
2-la) has been later proved to coincide with the class of deterministic context-free
languages [
Clearly, 0-limited automata are no more than two-way nite automata. Hence,
they characterize the class of regular languages. Wagner and Wechsung extended
this result to the case d = 1: 1-la recognize exactly the class of regular
languages [
Like d-limited automata, 1-limited automata can operate in super-linear time (cf., Example 1). This contrasts with Hennie machines which operate in linear time by denition. The question we address in this paper is whether this ability of 1-limited automata with respect to Hennie machines yields a gap between the two models in terms of the size of their representations. 2
We show that, with a polynomial increase in size, each 1-limited automaton can
be transformed into an halting linear-time 1-limited automaton. This is achieved
by augmenting the exponential cost simulation of 1-la by 2nfa given in [
Theorem 1. For each 1-la A, there exists an equivalent 1-la A0 satisfying: 1. A0 has polynomial size with respect to A; 2. in every computation of A0, each tape cell is visited a number of times which is bounded by some polynomial in the size of A; 3. A0 works in linear time: on every input string w, it halts within O(jwj) steps; 4. if A is deterministic, then so is A0.
Linear-time 1-las are particular cases of Hennie machines, hence, it follows from the above result that any 1-la can be transformed into a Hennie machine of size polynomial in the size of the 1-la. Using Item 2 we can actually strengthen the result: each 1-la can be transformed into a weight-reducing Hennie machine of polynomial size.
Corollary 1. For each 1-la A, there exists an equivalent weight-reducing Hennie machine A0 of size polynomial in the size of A. Furthermore, if A is deterministic, then so is A0.
We also observe that the 1-limited automaton resulting from the construction
of Theorem 1 can be easily transformed into an equivalent one whose behavior
can be divided into two phases: (1) an initial phase consisting in a left-to-right
exp [
A direct consequence of this last result, is that reversing a 1-limited automaton, i.e., transforming it into another one recognizing the reverse of its accepted language, has polynomial cost. This fails in the deterministic case, for which we exhibit an exponential lower bound. As a consequence, we obtain exponential lower bounds for the simulation of deterministic weight-reducing Hennie machines or deterministic two-way automata with common guess by deterministic 1-limited automata.
Lnr = fxkxk 1
x0 j k > 0; xi 2 fa; bgn; #fi > 0 j xi = x0g is oddg.
The results are summarized in Figure 1.
Acknowledgement. We are very indebted to Giovanni Pighizzini for suggesting the problem and for many stimulating conversations.