Program Schemes with Deep Pushdown Storage

DOI10.1007/978-3-540-69407-6_2zbMath1142.68346OpenAlexW1545845921MaRDI QIDQ3507414

Iain A. Stewart, Argimiro A. Arratia

Publication date: 19 June 2008

Published in: Logic and Theory of Algorithms (Search for Journal in Brave)

Full work available at URL: http://dro.dur.ac.uk/5770/1/5770.pdf

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Cites Work

• Unnamed Item
• Unnamed Item
• On the power of deep pushdown stacks
• 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
• On static logics, dynamic logics, and complexity classes
• Even Simple Programs Are Hard To Analyze
• Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures
• Hierarchies in classes of program schemes
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• On Classes of Program Schemata

This page was built for publication: Program Schemes with Deep Pushdown Storage