Publication details for Professor Iain StewartArratia-Quesada, A. & Stewart, I.A. (2009). On the power of deep pushdown stacks. Acta Informatica 46(7): 509-531.
- Publication type: Journal Article
- ISSN/ISBN: 0001-5903
- DOI: 10.1007/978-3-540-69407-6
- Keywords: Complexity theory; program schemes; stacks.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
Inspired by recent work of Meduna on deep pushdown automata, we consider the computational power of a class of basic program schemes, NPSDSs, 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 NPSDSs 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 NPSDSs are in EXPTIME.