k\(+1\) heads are better than k for PDAs
From MaRDI portal
Publication:1109579
DOI10.1016/0022-0000(88)90004-9zbMath0655.68104OpenAlexW2141989387MaRDI QIDQ1109579
Publication date: 1988
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0022-0000(88)90004-9
Related Items (6)
Refined simulation of multihead automata ⋮ Asynchronous Parallel Communicating Systems of Pushdown Automata ⋮ Exact Affine Counter Automata ⋮ Unnamed Item ⋮ Stack versus sensitivity for one-way automata ⋮ One-way multihead finite automata and 2-bounded languages
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the power of real-time two-way multihead finite automata with jumps
- Remarks on multihead pushdown automata and multihead stack automata
- Hierarchies of one-way multihead automata languages
- Tape versus queue and stacks: The lower bounds
- A hierarchy theorem for multihead stack-counter automata
- On 3-head versus 2-head finite automata
- On tape-bounded complexity classes and multihead finite automata
- Relating refined space complexity classes
- Transformational methods and their application to complexity problems. Corrigenda
- On two-way multihead automata
- On-line simulation of k + 1 tapes by k tapes requires nonlinear time
- Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
- One-way multihead writing finite automata
- Separating Nondeterministic Time Complexity Classes
- Ferromagnetic Wire Memory
- On Multi-Head Finite Automata
- Multi-tape and multi-head pushdown automata
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Time and tape complexity of pushdown automaton languages
This page was built for publication: k\(+1\) heads are better than k for PDAs
