A. Arratia-Quesada
On the power of deep pushdown stacks
Arratia-Quesada, A.; Stewart, I.A.; Beckmann, A.; Dimitracopoulos, C.; Loewe, B.
Authors
I.A. Stewart
A. Beckmann
C. Dimitracopoulos
B. Loewe
Abstract
Inspired by recent work of Meduna on deep pushdown automata, we consider the computational power of a class of basic program schemes, TeX, based around assignments, while-loops and non- deterministic guessing but with access to a deep pushdown stack which, apart from having the usual push and pop instructions, also has deep-push instructions which allow elements to be pushed to stack locations deep within the stack. We syntactically define sub-classes of TeX by restricting the occurrences of pops, pushes and deep-pushes and capture the complexity classes NP and PSPACE. Furthermore, we show that all problems accepted by program schemes of TeX are in EXPTIME.
Citation
Arratia-Quesada, A., Stewart, I., Beckmann, A., Dimitracopoulos, C., & Loewe, B. (2008). On the power of deep pushdown stacks. In Logic and theory of algorithms (11-21). https://doi.org/10.1007/978-3-540-69407-6
Conference Name | Computability in Europe 2008, Logic and Theory of Algorithms. |
---|---|
Conference Location | Athens, Greece |
Start Date | Jun 15, 2008 |
End Date | Jun 20, 2008 |
Publication Date | Jun 1, 2008 |
Deposit Date | Jul 2, 2009 |
Publicly Available Date | Jul 2, 2009 |
Pages | 11-21 |
Series Title | Lecture notes in computer science |
Series Number | 5028 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Logic and theory of algorithms. |
ISBN | 9783540694052 |
DOI | https://doi.org/10.1007/978-3-540-69407-6 |
Keywords | Models of computation, Program schemes, Complexity classes. |
Publisher URL | http://www.dur.ac.uk/i.a.stewart/Papers/DeepPushdownStacks.pdf |
Files
Accepted Conference Proceeding
(229 Kb)
PDF
Copyright Statement
The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-69407-6_2
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search