[Solved]: Time Complexity of Regular Languages

Problem Detail: 

I wonder how I can go about proving that if a language L is decidable in o(nlog(n)) then L must be regular.

I should probably mention that by "decidable" I mean "being decidable by single-tape deterministic turing machine".

Thanks and regards Guillermo

Asked By : Guillermo Pineda-Villavicencio

Answered By : Yuval Filmus

This is a classical result of Kobayashi, On the structure of one-tape nondeterministic Turing machine time hierarchy, Theorem 3.3 on page 188. The idea is to use crossing sequences: you show an upper bound $O(1)$ on the size of any crossing sequence, and then use an argument of Hennie, One-tape off-line Turing machine computations, Theorem 2 on page 561, to conclude that the language accepted by the machine is regular.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/17975

 Ask a Question

 Download Related Notes/Documents