文章基本信息

标题：Linear Time Simulation of Invertible Non-Deterministic Stack Algorithms
本地全文：下载
作者：Nils Andersen
期刊名称：Journal of Universal Computer Science
印刷版ISSN：0948-6968
出版年度：1997
卷号：3
期号：3
页码：148-171
出版社：Graz University of Technology and Know-Center
摘要：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.