Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR01-081 | 8th August 2001 00:00

Pushdown Automaton with the Ability to Flip its Stack

RSS-Feed




TR01-081
Authors: Palash Sarkar
Publication: 15th November 2001 12:57
Downloads: 2073
Keywords: 


Abstract:

We introduce the idea of pushdown automata with the ability to flip
its stack. By bounding the number of times the stack can be flipped
we obtain a hierarchy of language classes from the context free
languages to the recursively enumerable languages. We show that each
class in the hierarchy is nonempty and conjecture that the hierarchy
is strict. Also we provide some interesting open problems for this
new kind of automata.



ISSN 1433-8092 | Imprint