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

DOI10.1016/S0304-3975(01)00237-7zbMath1016.68046MaRDI QIDQ1608894

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)

Related Items (4)

Complexity of multi-head finite automata: origins and directions ⋮ Tight hierarchy of data-independent multi-head automata ⋮ New size hierarchies for two way automata ⋮ Oblivious two-way finite automata: decidability and complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Inductive counting for width-restricted branching programs
• Turing machines that take advice
• Polynomial size \(\Omega\)-branching programs and their computational power
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• On tape-bounded complexity classes and multihead finite automata
• Transformational methods and their application to complexity problems
• The network complexity and the Turing machine complexity of finite functions
• Transformational methods and their application to complexity problems. Corrigenda
• A constant-space sequential model of computation for first-order logic
• On non-determinacy in simple computing devices
• On two-way multihead automata
• On uniformity within \(NC^ 1\)
• Automata that take advice
• Relations Among Complexity Measures
• Classes of languages and linear-bounded automata

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