11
$\begingroup$

(I don't think that this is a good fit on cstheory, since I figure that this question already has a known answer. However, if you think that this would be a better fit there, please feel free to migrate it)

It can easily be shown that REGULAR (the class of regular languages) is contained in DTIME(O(n)), because for any regular language L we can decide membership in that language in O(n) time by converting a DFA that decides L into a TM that decides L in a single pass over the input. However, is it also true that DTIME(O(n)) is contained in REGULAR; that is, that any language that can be decided in O(n) time by a single-tape TM is necessarily regular?

I have no idea how to approach this problem, and every language I can think of in DTIME(O(n)) seems to be regular. Intuitively, this would make sense, since if you're only allowed to make finitely many passes over the input, you could only remember finitely many things about it, which it seems like you could simulate with a sufficiently large DFA. However, the fact that you can write to the input tape seems like it might complicate things.

And no, this isn't a homework problem. I'm actually teaching a course that covers computability and complexity theory and thought it would be interesting to present the answer to this question in lecture. :-)

Thanks!

$\endgroup$
  • $\begingroup$ On the complexity zoo it says that REG = DSPACE($O(1))$. (see qwiki.stanford.edu/index.php/Complexity_Zoo_1.0#reg ) $\endgroup$ – sxd Nov 20 '11 at 21:56
  • 2
    $\begingroup$ @DimitriSurinx: The equality REG=DSPACE(O(1)) is almost by definition. The question asks about something deeper. $\endgroup$ – Tsuyoshi Ito Nov 20 '11 at 23:22
  • $\begingroup$ @TsuyoshiIto: Oh, yes you are right, didn't think of it that way. $\endgroup$ – sxd Nov 21 '11 at 0:33
  • $\begingroup$ math.stackexchange.com/q/2203692/14578, cs.stackexchange.com/q/17975/755 $\endgroup$ – D.W. Apr 19 '17 at 22:19
  • $\begingroup$ @D.W. I believe that the second linked question was asked two years after this one and that the first was asked almost five and a half years later. :-) $\endgroup$ – templatetypedef Apr 19 '17 at 23:50
16
$\begingroup$

For the benefit of the readers, here is an outline of the proof that an $o(n\log n)$-time TM accepts a regular language.

Consider the computation of the TM on some input $x$. Write $x$ as follows: $$ |x_0|x_1|\cdots|x_n|. $$ Each $|$ signifies a boundary between two cells. The crossing number at a boundary on $x$ is simply the number of times the machine crosses the boundary. The crossing sequence is the sequence of states that the TM enters immediately after crossing the boundary (first from left to right, then from right to left, and so on).

Claim (Kobayashi '85): If a TM runs in time $o(n\log n)$, then the crossing number at any boundary on any input is $O(1)$.

Proof idea: Suppose that on some input, the crossing number at some boundary $X$ is large (at least $A$). Pick a smallest such input. Since the machine runs in time $o(n\log n)$, there must be many boundaries (at least $B(n)$) at which the crossing number is small (at most $c(n)$). Since $B(n)$ is so big compared to $c(n)$, by the pigeonhole principle there must be four boundaries with the same crossing sequence, out of which there are two on the same side of $X$. It follows that if we "excise" the substring bounded by these boundaries, we get a smaller string with a boundary with crossing number at least $A$. Q.E.D.

A computation is of course needed to show that there is an appropriate choice of $A,B(n),c(n)$ whenever the time is $o(n\log n)$. That's left for you to verify.

Claim (Hennie '65): If the crossing number of a TM is $O(1)$ for any input and any boundary, then the language it accepts is regular.

Proof idea: For strings $x,y$, define $x \equiv y$ if for any $z$, whenever the machine accepts $xz$ then it accepts $yz$, and vice versa. We show that $\equiv$ has finitely many equivalence classes, so the claim follows from Myhill-Nerode.

For a string $x$, let $S(x)$ denote the set of crossing sequences at the boundary $x|z$ for any $z$ such that the TM accepts $xz$. Suppose that $S(x) = S(y)$. We will show that $x \equiv y$. Indeed, take any $z$ such that the TM accepts $xz$. Since $S(x) \subseteq S(y)$, there is $w$ such that the TM accepts $yw$, and the crossing sequences at $x|z$ and $y|w$ are the same. This implies (after some thought) that indeed $yz$ is accepted by the TM. Q.E.D.

$\endgroup$
9
$\begingroup$

Single-tape $o(n \log n)$ Turing machines can recognize only regular languages. See http://arxiv.org/abs/cs/0310046 for reference. I recall seeing the proof for $O(n)$ only (can't remember the source now), and it was definitely not simple.

$\endgroup$
7
$\begingroup$

When you get below general polynomial time, you need to be careful which computation model we're working with -- a RAM can achieve much more in $O(n)$ time than a Turing machine can.

Anyway, with a "realistic" model, DTIME($O(n)$) can recognize much more than regular languages, such as $\{a^nb^n\mid n\in\mathbb N\}$ on a counter machine.

More generally, it is easy to see that a Turing machine with a read-only input tape and a separate scratch tape can recognize at least every LR($k$) context-free language in linear time -- and more than that, such as $\{a^nb^nc^n\mid n\in\mathbb N\}$ which is not context-free.

$\endgroup$
4
$\begingroup$

Yes, this is an old result that in $o(n \lg n)$ time a single tape Turing Machine can only decide regular languages. The proof is through considering the crossing sequences, you can find a proof in the second volume of Odifreddi's book.

$\endgroup$
  • $\begingroup$ Also see this question. $\endgroup$ – Kaveh Nov 20 '11 at 22:39
  • $\begingroup$ could you please post me the page number where this result is proved? I mean Odifreddi's book. $\endgroup$ – fade2black Jul 7 '17 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.