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.


Authors/Editors

Last updated on 2019-25-07 at 16:53