# Time Complexity of Regular Languages

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

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.