Skip to main content

Research Repository

Advanced Search

On the power of deep pushdown stacks

Arratia-Quesada, A.; Stewart, I.A.; Beckmann, A.; Dimitracopoulos, C.; Loewe, B.

On the power of deep pushdown stacks Thumbnail


Authors

A. Arratia-Quesada

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




Downloadable Citations