Program Schemes with Pushdown Stores
Steven Ford Brown, David Gries, Thomas G. Szymanski · SIAM Journal on Computing · 1972
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.