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


Authors

A. Arratia-Quesada



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.
Public URL https://durham-repository.worktribe.com/output/1523099

Files

Accepted Journal Article (232 Kb)
PDF

Copyright Statement
The original publication is available at www.springerlink.com






You might also like



Downloadable Citations