Optimal reduction in replacement systems

Publisher Website
Google Scholar
Abstract
High level programming languages can generally be compiled in many different ways. Thus it is natural to ask if there is a best way, for example in the sense of achieving complete execution of the program in a minimum number of steps; such a complete, minimal execution procedure will be called optimal.In recent years this question has been studied and answered for several simple models of programming languages, and a technique for proving procedures to be optimal has gradually emerged. Even for model languages the proofs of optimality become intricate; thus it is natural to emphasize the simplicity of the underlying technique by generalising it to an abstract system. That is the purpose of this paper. The general method to be given applies to prove all theorems (on optimal executions for model languages) which are known to the author. None of the previously known proofs has explicitly used the method, but in no case is it particularly difficult to modify the known proof so as to conform with the method.

This publication has 5 references indexed in Scilit: