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)

zbMATH Keywords

complexitymulti-head finite automataoblivious computationsuniformity and nonuniformity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

• 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?)
• 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
• 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

(6)

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

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)