# $DTIME_1(o(n^2))\setminus$ REGULAR

Maybe this is well-known, but I couldn't find any example of a non-regular lanugage that is decidable on a single-tape Turing machine in subquadratic time. Help!

Related paper: On the structure of one-tape nondeterministic turing machine time hierarchy by Kobayashi.

Related question: Why do we use single tape Turing machines for time complexity? by Kaveh.

• Also note that for one tape TMs $DTIME( o(n \log n)) \subseteq REG$ so there is no hope to find a non regular language that is not "hooked" in some manner to the length of the input. Commented Feb 19, 2020 at 16:09

For example, I think you can decide if $$\lfloor\log_2|w|\rfloor$$ is even in time $$O(n\log n)$$: you first overwrite the input string with all 1s, and then do $$\log n$$ passes over the string where you turn every other 1 into a 0 (while skipping 0s that are already there). You keep track of the number of passes modulo 2.

• or you can design a similar algorithm to accept iff |w| is a power of 2. Commented Feb 18, 2020 at 13:29
• @Denis Indeed. More generally, if $L$ is a regular language, you can decide if $|w|\in L$ (written in some base $b\ge2$). Commented Feb 18, 2020 at 13:35
• Or better, if you keep a binary counter at one end of the string, you can just compute $|w|$ itself in time $O(n\log n)$, and then you can do whatever you want with it. That is, if $L\subseteq\{0,1\}^*$ is any language decidable in time $O(2^{\alpha n})$ for some $1<\alpha<2$, you can decide if $|w|\in L$ in time $O(n^\alpha)$. Commented Feb 19, 2020 at 9:36
• More generally, one can decide in the same way whether $(\#_a(w),\#_b(w),\dots)\in L$, where $a,b,\dots$ are symbols of the alphabet. Commented Apr 9, 2023 at 5:49

The language $$L=\{0^n1^n : n\geq 0\}$$ is non-regular, but decidable in time $$O(n\log n)$$ on a one-tape Turing machine (one can either use a counter or iteratively remove every next 0 and 1 plus check parity).