Program Schemes with Pushdown Stores

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 aloowing one, two, or more pushdown stores, both with and without the ability to detect when a pds is empty. A main result is that the use of using one pds is empty. A main result is that the use of using one pds is computationally equivalent to allowing recursive functions. We also study the effect of adding the ability to do integer arithmetic, and multi-dimensional arrays. Keywords: Program schemes, schemata, pushdown stores, stacks, recursion, programming languages.