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

DOI10.1016/S0304-3975(01)00237-7MaRDI QIDQ1608894zbMATH OpenFDO

Authors Markus Holzer

Publication date 13 August 2002

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00237-7

zbMATH Keywords

complexitymulti-head finite automataoblivious computationsuniformity and nonuniformity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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.

Recommendations

• scientific article; zbMATH DE number 1361488
• Tight hierarchy of data-independent multi-head automata
• Multi-head finite automata: characterizations, concepts and open problems
• Finite dP Automata versus Multi-head Finite Automata
• Complexity of multi-head finite automata: origins and directions
• Some characterizations of multihead finite automata
• A NOTE ON MULTIHEAD FINITE-STATE AUTOMATA
• scientific article; zbMATH DE number 3383997
• On multi-head automata with restricted nondeterminism
• scientific article; zbMATH DE number 4143455

Cites work

• A constant-space sequential model of computation for first-order logic
• Automata that take advice
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Classes of languages and linear-bounded automata
• scientific article; zbMATH DE number 4061160 (Why is no real title available?)
• scientific article; zbMATH DE number 3690693 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 3471609 (Why is no real title available?)
• scientific article; zbMATH DE number 1222567 (Why is no real title available?)
• scientific article; zbMATH DE number 1346517 (Why is no real title available?)
• Inductive counting for width-restricted branching programs
• On non-determinacy in simple computing devices
• On tape-bounded complexity classes and multihead finite automata
• On two-way multihead automata
• On uniformity within \(NC^ 1\)
• Polynomial size \(\Omega\)-branching programs and their computational power
• Relations Among Complexity Measures
• The network complexity and the Turing machine complexity of finite functions
• Transformational methods and their application to complexity problems
• Transformational methods and their application to complexity problems. Corrigenda
• Turing machines that take advice

Cited in

(7)

• New size hierarchies for two way automata
• Tight hierarchy of data-independent multi-head automata
• Oblivious two-way finite automata: decidability and complexity
• Finite dP Automata versus Multi-head Finite Automata
• scientific article; zbMATH DE number 1361488 (Why is no real title available?)
• Complexity of multi-head finite automata: origins and directions
• Multi-head two-way finite automata with advice

This page was built for publication: Multi-head finite automata: Data-independent versus data-dependent computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1608894)