Program Schemes with Pushdown Stores | Zendy

Steven Ford Brown | Zendy; David Gries | Zendy; Thomas G. Szymanski | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Program Schemes with Pushdown Stores

Author(s) -

Steven Ford Brown,

David Gries,

Thomas G. Szymanski

Publication year - 1972

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0201017

Subject(s) - embedded pushdown automaton , deterministic pushdown automaton , integer (computer science) , computer science , pushdown automaton , mathematics , context free language , discrete mathematics , theoretical computer science , algorithm , programming language , rule based machine translation , artificial intelligence , context free grammar , automata theory , automaton , tree adjoining grammar , nondeterministic finite automaton

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research