期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2001
卷号：2001
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
关键词：formal languages , push down automata , Theory of Computation
