ON THE VERIFICATION OF FUNCTION EQUIVALENCE WITH UNKNOWN INPUT CORRESPONDENCE

A method that verifies the equivalence of functions with unknown input correspondence is proposed in this paper. The key to our method is to associate a new signature with each input variable, thereby effectively establishing partial (sometimes total) correspondence between two sets of input variables. The descriptive power of our new signature appears to be very effective. In addition to the strong descriptive power, our proposed signature also provides information for pruning when exhaustive search has to be used finally on variables that cannot be matched in two input functions. We have implemented and tested an algorithm based on our approach. The experimental results are encouraging.