Fooling a two-way nondeterministic multihead automaton with reversal number restriction (Q1058864)

We define a language L and show that it can be recognized by no two-way nondeterministic sensing multihead finite automaton with \(n^ a\) reversal bound, where n is the length of input words, and \(1/3>a>0\) is a real number. Since L is recognized by a two-way deterministic two-head finite automaton working in linear time we obtain, for two-way finite automata, that time, reading heads, and nondeterminism as resources cannot compensate for the reversal number restriction.