Shrinking Multi-pushdown Automata

摘要

The shrinking two-pushdown automaton is known to char-actize 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.