Efficient Equivalence and Minimization for Non Deterministic Xor Automata

A word w in a regular language L is or-accepted by a non-deterministic finite or-automaton A if there exists a path along w from some initial state to some final state in A. The same word w is xor-accepted by the same non-deterministic finite xor-automaton A if the number of accepting pathes is odd. In the deterministic case, accepting pathes are unique and both definitions coincide. No polynomial time algorithm is known to minimize NFAs or to compute their equivalence. By contrast, we present a cubic time algorithm to reduce a xor-automaton to a minimal form M = MXA(A), within the least possible number of states. It is a finite strong normal form and automata equivalence is efficiently decided through reduction to the SNF