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

Research paper by J. Hromkovič

Indexed on: 01 Dec '85Published on: 01 Dec '85Published in: Acta Informatica


We define a language L and show that it can be recognized by no two-way nondeterministic sensing multihead finite automaton with na 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.