Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the power of deep pushdown stacks

Autor
Arratia, A.; Stewart, I.
Tipus d'activitat
Article en revista
Revista
Acta informatica
Data de publicació
2009-11
Volum
46
Número
7
Pàgina inicial
509
Pàgina final
531
DOI
https://doi.org/10.1007/s00236-009-0103-x Obrir en finestra nova
Repositori
http://hdl.handle.net/2117/7964 Obrir en finestra nova
URL
http://www.springerlink.com/content/y46h6501746506p0/ Obrir en finestra nova
Resum
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 ...
Citació
Arratia, A.; Stewart, I. On the power of deep pushdown stacks. "Acta informatica", Novembre 2009, vol. 46, núm. 7, p. 509-531.

Participants

Arxius