Multi-head finite automata: Data-independent versus data-dependent computations
From MaRDI portal
Publication:1608894
DOI10.1016/S0304-3975(01)00237-7zbMATH Open1016.68046MaRDI QIDQ1608894FDOQ1608894
Authors: Markus Holzer 
Publication date: 13 August 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
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
- On uniformity within \(NC^ 1\)
- Relations Among Complexity Measures
- On non-determinacy in simple computing devices
- Title not available (Why is that?)
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Turing machines that take advice
- On tape-bounded complexity classes and multihead finite automata
- Automata that take advice
- Inductive counting for width-restricted branching programs
- Classes of languages and linear-bounded automata
- The network complexity and the Turing machine complexity of finite functions
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Transformational methods and their application to complexity problems
- On two-way multihead automata
- Polynomial size \(\Omega\)-branching programs and their computational power
- Title not available (Why is that?)
- Transformational methods and their application to complexity problems. Corrigenda
- Title not available (Why is that?)
- A constant-space sequential model of computation for first-order logic
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
- Title not available (Why is that?)
- Oblivious two-way finite automata: decidability and complexity
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)
