A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
Wen-Guey Tzeng · SIAM Journal on Computing · 1992
Two probabilistic automata are equivalent if for any string x, the two automata accept x with equal probability. This paper presents an $O((n_1 + n_2 )^4 )$ algorithm for determining whether two probabilistic automata $U_1 $ and $U_2 $ are equivalent, where $n_1 $ and $n_2 $ are the number of states in $U_1 $ and $U_2 $, respectively.This improves the best previous result, which showed that the problem was in $coNP$. The existence of this algorithm implies that the covering and equivalence problems for uninitiated probabilistic automata are also polynomial-time solvable. The algorithm used to determine the equivalence of probabilistic automata can also solve the path equivalence problem for nondeterministic finite automata without $\lambda $-transitions and the equivalence problem for unambiguous finite automata in polynomial time. This paper studies the approximate equivalence (or $\delta $-equivalence) problem for probabilistic automata. An algorithm for the approximate equivalence problem for positive probabilistic automata is given.