Multi-head finite automata: Data-independent versus data-dependent computations
type: Item
instance of: scholarly article
title: Multi-head finite automata: Data-independent versus data-dependent computations
zbMATH Open document ID: 1016.68046
DOI: 10.1016/S0304-3975(01)00237-7
author: Markus Holzer
published in: Theoretical Computer Science
publication date: 2002-08-13T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1780599
zbMATH Keywords: multi-head finite automata
zbMATH Keywords: oblivious computations
zbMATH Keywords: complexity
zbMATH Keywords: uniformity and nonuniformity
MaRDI profile type: Publication
cites work: Q4039803
cites work: Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
cites work: On uniformity within \(NC^ 1\)
cites work: Automata that take advice
cites work: Inductive counting for width-restricted branching programs
cites work: Q4266541
cites work: On non-determinacy in simple computing devices
cites work: On two-way multihead automata
cites work: Turing machines that take advice
cites work: Classes of languages and linear-bounded automata
cites work: A constant-space sequential model of computation for first-order logic
cites work: Polynomial size \(\Omega\)-branching programs and their computational power
cites work: Transformational methods and their application to complexity problems
cites work: Transformational methods and their application to complexity problems. Corrigenda
cites work: Q3885190
cites work: Q4055196
cites work: Q4218105
cites work: Relations Among Complexity Measures
cites work: The network complexity and the Turing machine complexity of finite functions
cites work: On tape-bounded complexity classes and multihead finite automata
cites work: Q3795617
Recommended article: Q4699306
Recommended article: Tight hierarchy of data-independent multi-head automata
Recommended article: Q5145152
Recommended article: Finite dP Automata versus Multi-head Finite Automata
Recommended article: Complexity of multi-head finite automata: origins and directions
Recommended article: Some characterizations of multihead finite automata
Recommended article: A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
Recommended article: Q5654031
Recommended article: On multi-head automata with restricted nondeterminism
Recommended article: Q3474895
description: scientific article; zbMATH DE number 1780599