Aufsatz in einer Fachzeitschrift
Shrinking multi-pushdown automata
Details zur Publikation
Autor(inn)en: | Holzer, M.; Otto, F. |
Herausgeber: | Liskiewicz, M. and Reischuk, R. |
Verlag: | Springer |
Verlagsort / Veröffentlichungsort: | Berlin |
Publikationsjahr: | 2005 |
Seitenbereich: | 305-316 |
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.
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.
