Skip to main content

Research Repository

Advanced Search

On the power of deep pushdown stacks

Arratia-Quesada, A.; Stewart, I.A.

On the power of deep pushdown stacks Thumbnail


A. Arratia-Quesada


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.


Arratia-Quesada, A., & Stewart, I. (2009). On the power of deep pushdown stacks. Acta Informatica, 46(7), 509-531.

Journal Article Type Article
Publication Date Nov 1, 2009
Deposit Date Dec 9, 2009
Publicly Available Date Jan 4, 2010
Journal Acta Informatica
Print ISSN 0001-5903
Electronic ISSN 1432-0525
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 46
Issue 7
Pages 509-531
Keywords Complexity theory, Program schemes, Stacks.


Accepted Journal Article (232 Kb)

Copyright Statement
The original publication is available at

You might also like

Downloadable Citations