Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-19T04:04:40.804Z Has data issue: false hasContentIssue false

Optimal reduction in replacement systems

Published online by Cambridge University Press:  17 April 2009

John Staples
Affiliation:
Department of Mathematics and Computer Science, Queensland Institute of Technology, North Quay, Queensland.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1977