Stack Cooperation in Multistack Pushdown Automata

摘要

The paper considers multistack pushdown automata with several strategies on the use of stacks, similar to the strategies of cooperation in grammar systems. As was to be expected, the accepting capacity of all nondeterministic variants equals the power of Turing machines. Also, all strategies in the deterministic case are equivalent. Moreover, one shows that they accept a large class of nonrecursive languages.