Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/7964

On the power of deep pushdown stacks
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics
The original publication is available at http://www.springerlink.com/content/y46h6501746506p0/fulltext.pdf
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.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Computational complexity
Computer algorithms
Complexitat computacional
Algorismes computacionals
info:eu-repo/semantics/submittedVersion
Artículo
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Stewart, Iain A.
Arratia Quesada, Argimiro Alejandro; Ortiz Gómez, Carlos