Aufsatz in einer Fachzeitschrift
Shrinking multi-pushdown automata
Details zur Publikation
Autor(inn)en: | Holzer, M.; Otto, F.
|
Herausgeber: | Liskiewicz, M. and Reischuk, R.
|
Verlagsort / Veröffentlichungsort: | Berlin
|
Buchtitel: | Fundamentals of Computation Theory, Proceedings FCT 2005,
|
Titel der Buchreihe: | Lecture Notes in Computer Science 3623
|
Zusammenfassung, Abstract
The shrinking two-pushdown automaton is known to charactize the class of growing context-sensitive languages, while its deterministic variant accepts the Church-Rosser languages. Here we study the expressive power of shrinking pushdown automata with more than two pushdown stores, obtaining a close correspondence to linear time-bounded multi-tape Turing machines.Autor(inn)en / Herausgeber(innen)