Program Schemes with Deep Pushdown Storage

DOI10.1007/978-3-540-69407-6_2MaRDI QIDQ3507414zbMATH OpenOpenAlexFDO

Authors Iain Stewart, Argimiro 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)

Recommendations

• On the power of deep pushdown stacks
• Hierarchies in classes of program schemes
• PUSHDOWN AUTOMATA ON INFINITE TREES AND NONDETERMINISTIC CONTEXT-FREE PROGRAMS
• Logical and Complexity-theoretic Aspects of Models of Computation with Restricted Access to Arrays
• Program Schemes, Queues, the Recursive Spectrum and Zero-one Laws

Cites work

• A hierarchy between context-free and context-sensitive languages
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Deep pushdown automata
• Even Simple Programs Are Hard To Analyze
• Hierarchies in classes of program schemes
• scientific article; zbMATH DE number 3889514 (Why is no real title available?)
• scientific article; zbMATH DE number 3349780 (Why is no real title available?)
• On Classes of Program Schemata
• On static logics, dynamic logics, and complexity classes
• On the power of deep pushdown stacks
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• Some relationships between logics of programs and complexity theory
• Using Program Schemes to Capture Polynomial-Time Logically on Certain Classes of Structures
• Using the Hamiltonian path operator to capture NP

Cited in

(1)

• On the power of deep pushdown stacks

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3507414)