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.


Autor(inn)en / Herausgeber(innen)

Zuletzt aktualisiert 2019-25-07 um 16:53