TY - GEN

T1 - Equivalence and learning of probabilistic automata

AU - Tzeng, Wen-Guey

PY - 1989/11/1

Y1 - 1989/11/1

N2 - It is proved that the equivalence problem for probabilistic automata is solvable in time O((n1 + n2)4), where n1 and n2 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.

AB - It is proved that the equivalence problem for probabilistic automata is solvable in time O((n1 + n2)4), where n1 and n2 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.

UR - http://www.scopus.com/inward/record.url?scp=0024768668&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1989.63489

DO - 10.1109/SFCS.1989.63489

M3 - Conference contribution

AN - SCOPUS:0024768668

SN - 0818619821

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 268

EP - 273

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

Y2 - 30 October 1989 through 1 November 1989

ER -