On the power of deep pushdown stacks
From MaRDI portal
Publication:1037618
DOI10.1007/s00236-009-0103-xzbMath1186.68265OpenAlexW2117746481MaRDI QIDQ1037618
Iain A. Stewart, Argimiro Arratia Quesada
Publication date: 16 November 2009
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/6255/1/6255.pdf
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Elements of finite model theory.
- Some relationships between logics of programs and complexity theory
- Using the Hamiltonian path operator to capture NP
- Program schemes, arrays, Lindström quantifiers and zero-one laws
- Deep pushdown automata
- A hierarchy between context-free and context-sensitive languages
- Logical and Complexity-theoretic Aspects of Models of Computation with Restricted Access to Arrays
- On static logics, dynamic logics, and complexity classes
- Even Simple Programs Are Hard To Analyze
- Simultaneously One-Turn Two-Pushdown Automata
- The equivalence problem for deterministic finite-turn pushdown automata
- Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures
- Hierarchies in classes of program schemes
- Finite-Turn Pushdown Automata
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- On Classes of Program Schemata
This page was built for publication: On the power of deep pushdown stacks
