Time and tape complexity of pushdown automaton languages
From MaRDI portal
Cited in
(38)- HyPAM: A hybrid continuum-particle model for incompressible free-surface flows
- Complexity and decidability for chain code picture languages
- On efficient recognition of transductions and relations
- Two-way automata with more than one storage medium
- On pebble automata
- k\(+1\) heads are better than k for PDAs
- Alternating multihead finite automata
- Time complexity of languages recognized by one-way multihead pushdown automata
- A note on two-way nondeterministic pushdown automata
- Remarks on the complexity of nondeterministic counter languages
- Notes on looping deterministic two-way pushdown automata
- Iterative deepening multiobjective \(A^{*}\)
- 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.
- Improved algorithm for all pairs shortest paths
- On the computational power of pushdown automata
- Pushdown automata with counters
- On two-way multihead automata
- Self-reducibility
- Unary resolution: characterizing \textsc{Ptime}
- A practical simulation result for two-way pushdown automata
- Partitions with minimum entropy of regions in \(\mathbb R^{2}\)
- Path-based depth-first search for strong and biconnected components
- Maximally-polyvariant partial evaluation in polynomial time
- scientific article; zbMATH DE number 3976380 (Why is no real title available?)
- Relationships between pushdown automata with counters and complexity classes
- On the complexity of finite, pushdown, and stack automata
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
- scientific article; zbMATH DE number 3576701 (Why is no real title available?)
- Sweeping input-driven pushdown automata
- The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
- Sweeping input-driven pushdown automata
- The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
- A multiple-heaps algorithm for parallel simulation of collision systems
- Characterizations of pushdown machines in terms of time-bounded computers
- Language acceptors with a pushdown: characterizations and complexity
This page was built for publication: Time and tape complexity of pushdown automaton languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5672196)
