A class of replacement systems with simple optimality theory

Publisher Website
Google Scholar
Abstract
A class of replacement systems is studied which satisfies a “subcommutativity” condition. Examples of systems satisfying this condition are many of the systems of graph-like expressions which have recently been studied in connection with the efficient evaluation of recursive definitions. An optimality theory of subcommutative systems is developed and is used to give conditions which are sufficient to ensure that an evaluation (reduction) procedure is optimal. The optimality theory is also applied to develop conditions under which a given subcommutative system speeds up, in a natural sense, another replacement system.

This publication has 4 references indexed in Scilit: