Arratia-Quesada, A. and Stewart, I. A. (2008) 'Program schemes with deep pushdown storage.', in Logic and theory of algorithms. Berlin: Springer, pp. 11-21. Lecture notes in computer science. (5028).
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.
|Item Type:||Book chapter|
|Keywords:||Models of computation, Program schemes, Complexity classes.|
|Full text:||PDF - Accepted Version (224Kb)|
|Publisher Web site:||http://dx.doi.org/10.1007/978-3-540-69407-6_2|
|Publisher statement:||The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-540-69407-6_2|
|Record Created:||02 Jul 2009 14:50|
|Last Modified:||31 Mar 2015 12:41|
|Social bookmarking:||Export: EndNote, Zotero | BibTex|
|Usage statistics||Look up in GoogleScholar | Find in a UK Library|