0
$\begingroup$

Let $TIME(f(n)) = $ the collection of languages decidable by a one tape DTM in $O(f(n))$. I am looking for a characterization of this class of languages, if $f$ is sublinear. This means there is not even enough time to read the whole input. On one hand, a guess is that this every language in this class must be regular (but not the other way) since you can only compute basic things like if the first letter is a 1. On the other hand, I feel like you could take a non regular language, and pad it in a funny way to increase the size of the input, but could still have it decidable in sublinear in this "padded" length of input.

There are some related questions and answers but not really what I am looking for. I am not concerned with approximation or property testing.

$\endgroup$
4
  • 2
    $\begingroup$ This is not a research-level question. It is both well known and easy to prove (using indeed the fact that such a machine cannot read the whole input) that on a usual TM (even multitape), DTIME(o(n)) equals DTIME(O(1)), i.e., languages whose membership only depends on the first O(1) bits of the input. In fact, this is true for DTIME(f(n)) where f is any function such that f(n)<n for at least one n. $\endgroup$ – Emil Jeřábek Jul 19 at 17:17
  • $\begingroup$ @EmilJeřábek Can you direct me to a source $\endgroup$ – abrahimladha Jul 19 at 20:21
  • $\begingroup$ See e.g. cs.stackexchange.com/questions/140651/… $\endgroup$ – Emil Jeřábek Jul 20 at 6:00
  • 2
    $\begingroup$ It is also a classic result that the language of every single-tape TM that uses time $o(n\log n)$ is regular. $\endgroup$ – Neal Young Jul 20 at 11:15