On the power of deep pushdown stacks

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

doi:10.1007/s00236-009-0103-x

On the power of deep pushdown stacks

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

Authors

A. Arratia-Quesada

Professor Iain Stewart i.a.stewart@durham.ac.uk
Professor

Abstract

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.

Citation

Arratia-Quesada, A., & Stewart, I. (2009). On the power of deep pushdown stacks. Acta Informatica, 46(7), 509-531. https://doi.org/10.1007/s00236-009-0103-x

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
DOI	https://doi.org/10.1007/s00236-009-0103-x
Keywords	Complexity theory, Program schemes, Stacks.