Equivalence of some classes of algorithms

Our objective is to find large classes of equivalent programs which can be simply characterized so that it is possible to choose from amongst them the program which is optimum by some reasonable criterion. We would like to do this for as high a level of programming language as possible. In this paper, we will consider some easily characterized classes of equivalent programs and some techniques for optimizing over such classes of equivalent programs. In general when we speak of two descriptions of an algorithm being equivalent, we mean that they both produce the same output for the same inputs. The programs we will consider will consist, at first, of ordered sequences of assignment statements of the form: X = f(Xl, ... Xn) Such a language is not the same as any real programming language. It is more like a flow chart language. It is more chosen for simplicity. It will also be seen that for certain kinds of optimizing of more realistic programming languages, we can optimize in the above language and that optimization will carry over when we translate to a more realistic programming language. The classes of equivalent programs we will consider will each he characterized by an array of "black boxes". Each program in such a class will have the property that it has one assignment statement for each box in the characterizing array of a form which is directly related to that block and each program is equivalent to the characterizing array in that it will produce the same output as the array when presented with the same input. We will call such programs 1-equivalent to their characterizing array.Technical report dcs-tr-