Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Program schemes with deep pushdown storage

Edit abstract data

Speaker: Argimiro Arratia
Author(s): Argimiro Arratia and Iain Stewart
Slot: Mon, 12:20-12:40, Great Hall (col. 5)


Inspired by recent work of Meduna on deep pushdown automata, we
consider the computational power of a class of basic program
schemes, $\mbox{NPSDS}_s$, 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 $\mbox{NPSDS}_s$ by
restricting the occurrences of pops, pushes and deep-pushes and
capture the complexity classes {\bf NP} and {\bf PSPACE}.
Furthermore, we show that all problems accepted by program schemes
of $\mbox{NPSDS}_s$ are in {\bf EXPTIME}.

websites: Arnold Beckmann 2008-05-29 Valid HTML 4.01! Valid CSS!