Multi-head finite automata: data-independent versus data-dependent computations

AbstractWe develop a multi-head finite automata framework suitable for a more detailed study of the relationship between parallel logarithmic time and sequential logarithmic space, in the uniform and nonuniform settings. In both settings it turns out that NC1 requires data-independent or oblivious computations, i.e., the movement of the input-heads only depends on the length of the input, whereas logarithmic space is captured with data-dependent computations on multi-head finite state machines. This sheds new light on the question whether NC1 and logarithmic space coincide