The equivalence and learning of probabilistic automata

Abstract

It is proved that the equivalence problem for probabilistic automata is solvable in time O((n/sub 1/+n/sub 2/)/sup 4/), where n/sub 1/ and n/sub 2/ are numbers of states of two given probabilistic automata. This result improves the best previous upper bound of coNP. The algorithm has some interesting applications, for example, to the covering and equivalence problems for uninitiated probabilistic automata, the equivalence and containment problems for unambiguous nondeterministic finite automata, and the path-equivalence problem for nondeterministic finite automata. Using the same technique, a polynomial-time algorithm for learning probabilistic automata is developed. The learning protocol is learning by means of queries.