A Polynomial-Time Algorithm for the Equivalence of Probabilistic Automata
Author:
- Wen-Guey TzengWTWen-Guey Tzeng
- 1 April 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 21 (2) , 216-227
Abstract
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.
Keywords
This publication has 3 references indexed in Scilit:
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite AutomataSIAM Journal on Computing, 1985
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- Probabilistic automataInformation and Control, 1963