Program Schemes with Pushdown Stores
SIAM Journal on Computing1972Vol. 1(3), pp. 242–268
Abstract
We attempt to characterize classes of schemes allowing pushdown stores, building on an earlier work by Constable and Gries [1]. We study the effect (on the computational power) of allowing one, two, or more pushdown stores, both with and without the ability to detect when a pds is empty. A main result is that using one pds is computationally equivalent to allowing recursive functions. We also study the effect of adding the ability to do integer arithmetic, and multidimensional arrays.
Related Papers
- → Synchronization of Pushdown Automata(2006)21 cited
- → A pushdown automation or a context-free grammar—which is more economical?(1982)17 cited
- SYNCHRONIZATION OF PUSHDOWN AUTOMATA(2006)
- → On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata(2008)9 cited
- → Time varying pushdown automata(1988)4 cited