Journal article
Shrinking multi-pushdown automata
Publication Details
Authors: | Holzer, M.; Otto, F. |
Editor: | Liskiewicz, M. and Reischuk, R. |
Publisher: | Springer |
Place: | Berlin |
Publication year: | 2005 |
Pages range : | 305-316 |
Book title: | Fundamentals of Computation Theory, Proceedings FCT 2005, |
Title of series: | Lecture Notes in Computer Science 3623 |
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.
