Equivalence and learning of probabilistic automata

Wen-Guey Tzeng*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

13 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages268-273
Number of pages6
ISBN (Print)0818619821
DOIs
StatePublished - 1 Nov 1989
Event30th Annual Symposium on Foundations of Computer Science - Research Triangle Park, NC, USA
Duration: 30 Oct 19891 Nov 1989

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Conference

Conference30th Annual Symposium on Foundations of Computer Science
CityResearch Triangle Park, NC, USA
Period30/10/891/11/89

Fingerprint

Dive into the research topics of 'Equivalence and learning of probabilistic automata'. Together they form a unique fingerprint.

Cite this