# A super-linear time problem in NL

It is a well-known fact that $\mathsf{NL} = \cup_{k>0} \mathsf{2NFA[k]}$, where $\mathsf{2NFA[k]}$ is the class of languages recognized by two-way nondeterministic finite automata with $k>0$ input heads, shortly 2nfa(k).

I have two but similar questions:

Is there any known language in $\mathsf{NL}$ requiring super-linear time, where the model is a standard space-bounded NTM having a read-only input tape and a read/write work tape?

Is there any known language recognized by some 2nfa(k) in super-linear time but not recognized by any 2nfa(k) in linear time?

• I think both your questions are the same question. Do you have a reason for them being different, or are you just unsure? – Luke Mathieson Jul 25 '12 at 13:50
• @LukeMathieson: I am not sure whether for a given $t(n)$ time bounded NTM, there exists an equivalent $O(t(n))$ time bounded 2nfa(k) for some $k>0$, and vice versa. – Abuzer Yakaryilmaz Jul 25 '12 at 14:00
• From the equivalence though, you know that every language in NL has a 2nfa(k) and that every language that has a 2nfa(k) is in NL. – Luke Mathieson Jul 25 '12 at 14:17
• @LukeMathieson: Yes! – Abuzer Yakaryilmaz Jul 25 '12 at 14:25
• In the first question, you wrote "requiring super-linear time," but in which computational model? – Tsuyoshi Ito Jul 26 '12 at 13:19