Time and tape complexity of pushdown automaton languages

DOI10.1016/S0019-9958(68)91087-5zbMath0257.68065WikidataQ29396489 ScholiaQ29396489MaRDI QIDQ5672196

John E. Hopcrofts, Jeffrey D. Ullman, A. V. Aho

Publication date: 1968

Published in: Information and Control (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Two-way automata with more than one storage medium ⋮ Partitions with minimum entropy of regions in \(\mathbb R^{2}\) ⋮ On pebble automata ⋮ Path-based depth-first search for strong and biconnected components ⋮ Maximally-Polyvariant Partial Evaluation in Polynomial Time ⋮ Iterative deepening multiobjective \(A^{*}\) ⋮ Self-reducibility ⋮ Improved algorithm for all pairs shortest paths ⋮ Unnamed Item ⋮ k\(+1\) heads are better than k for PDAs ⋮ Alternating multihead finite automata ⋮ Sweeping input-driven pushdown automata ⋮ Time complexity of languages recognized by one-way multihead pushdown automata ⋮ A note on two-way nondeterministic pushdown automata ⋮ Relationships between pushdown automata with counters and complexity classes ⋮ On the complexity of finite, pushdown, and stack automata ⋮ A multiple-heaps algorithm for parallel simulation of collision systems ⋮ Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages ⋮ Remarks on the complexity of nondeterministic counter languages ⋮ HyPAM: A hybrid continuum-particle model for incompressible free-surface flows ⋮ Unary Resolution: Characterizing Ptime ⋮ Unnamed Item ⋮ On the computational power of pushdown automata ⋮ A Practical Simulation Result for Two-Way Pushdown Automata ⋮ Pushdown automata with counters ⋮ On two-way multihead automata ⋮ Time complexity of loop-free two-way pushdown automata ⋮ A simulation result for two-way pushdown automata ⋮ A frame for general divide-and-conquer recurrences ⋮ A simplified correctness proof for a well-known algorithm computing strongly connected components. ⋮ Complexity and decidability for chain code picture languages ⋮ On efficient recognition of transductions and relations ⋮ Notes on looping deterministic two-way pushdown automata