k\(+1\) heads are better than k for PDAs
type: Item
instance of: scholarly article
title: k\(+1\) heads are better than k for PDAs
zbMATH Open document ID: 0655.68104
DOI: 10.1016/0022-0000(88)90004-9
author: Marek Chrobak
author: Ming Li
published in: Journal of Computer and System Sciences
publication date: 1988-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 4070370
zbMATH Keywords: deterministic pushdown automata
MaRDI profile type: Publication
full work available at URL: 0022-0000(88)90004-9
OpenAlex ID: W2141989387
cites work: Time and tape complexity of pushdown automaton languages
cites work: Hierarchies of one-way multihead automata languages
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: Q5636862
cites work: Multi-tape and multi-head pushdown automata
cites work: Q5592246
cites work: Ferromagnetic Wire Memory
cites work: On two-way multihead automata
cites work: On 3-head versus 2-head finite automata
cites work: Q3751011
cites work: Tape versus queue and stacks: The lower bounds
cites work: A hierarchy theorem for multihead stack-counter automata
cites work: Remarks on multihead pushdown automata and multihead stack automata
cites work: Transformational methods and their application to complexity problems. Corrigenda
cites work: Q3885190
cites work: Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines
cites work: Q3751009
cites work: Q3051378
cites work: On-line simulation of k + 1 tapes by k tapes requires nonlinear time
cites work: Q5559262
cites work: On Multi-Head Finite Automata
cites work: On the power of real-time two-way multihead finite automata with jumps
cites work: Separating Nondeterministic Time Complexity Classes
cites work: Relating refined space complexity classes
cites work: On tape-bounded complexity classes and multihead finite automata
cites work: One-way multihead writing finite automata
description: scientific article; zbMATH DE number 4070370