Multi-head finite automata: Data-independent versus data-dependent computations (Q1608894)

We 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 \(NC^{1}\) 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 \(NC^{1}\) and logarithmic space coincide.