A CHARACTERIZATION AND NEARLY LINEAR-TIME EQUIVALENCE TEST FOR MU-BRANCHING PROGRAMS

We present a characterization of mu-branching programs and a decomposi tion tree data structure which results from the characterization. We t hen show how the data structure can be used to test the equivalence of a pair of n-node mu-branching programs in O (n alpha(n)) time, where alpha(n) is a functional inverse of the Ackermann function. In additio n, we show that equivalence testing of k mu-branching programs for k g reater than or equal to 3 is co-NP-complete.