Lecture Notes in Computer Science, 1993, Volume 724/1993, 112-123, DOI: 10.1007/3-540-57264-3_34

Occam's razor in metacomputation: the notion of a perfect process tree

Robert Glück and Andrei V. Klimov

View Related Documents

Abstract

We introduce the notion of a perfect process tree as a model for the full propagation of information in metacomputation. Starting with constant propagation we construct step-by-step the driving mechanism used in supercompilation which ensures the perfect propagation of information. The concept of a simple supercompiler based on perfect driving coupled with a simple folding strategy is explained. As an example we demonstrate that specializing a naive pattern matcher with respect to a fixed pattern obtains the efficiency of a matcher generated by the Knuth, Morris & Pratt algorithm.
Supported by the Austrian Science Foundation (FWF) under grant number J0780-PHY.
Supported by the Russian Foundation for Fundamental Research under grant number 93-12-628 and in part by the lsquoösterreichische Forschungsgemeinschaftrsquo under grant number 06/1789.

Fulltext Preview

Image of the first page of the fulltext document