Arratia-Quesada, A. and Stewart, I. A. (2009) 'On the power of deep pushdown stacks.', Acta informatica., 46 (7). pp. 509-531.
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.
|Keywords:||Complexity theory, Program schemes, Stacks.|
|Full text:||PDF - Accepted Version (228Kb)|
|Publisher Web site:||http://dx.doi.org/10.1007/s00236-009-0103-x|
|Publisher statement:||The original publication is available at www.springerlink.com|
|Record Created:||09 Dec 2009 14:05|
|Last Modified:||06 Dec 2011 09:33|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|