Linear Time Simulation of Invertible Non-Deterministic Stack Algorithms

Nils Andersen (Department of Computing Science, University of Copenhagen, Denmark)

Abstract: It is demonstrated how a program making use of a single stack may be transformed, via memoization, into an equivalent one running in time proportional to the sum of variabilities at certain program points of the original program. This result generalizes Cook's linear time simulation of a deterministic two-way push-down automaton and also provides a lucid explanation of Cook's construction.

Obtaining an efficient transformed program depends on making good use of the stack to reduce variabilities at the critical program points. It is suggested to obtain such a program directly from a source program expressed in a non-deterministic language with invertible operations and annotated with a kind of "cuts" somewhat similar to cuts in a Prolog program.