You are not logged in to this journal. Log in

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. ©1992 Society for Industrial and Applied Mathematics