Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs

Abstract

Let Q be any algebraic structure and ~the set of all total programs over Q using the instruction set {z ,,--1, z ,,-x + y, z ,,--x -y, z ~ x * y, z ~--x/y}. (A program is total if no division by zero occurs during any computation ) Let the equivalence problem for ~ be the problem of deciding for two given programs in ~whether or not they compute the same funcuon The following results are proved: