Journal article icon

Journal article

Language equivalence for probabilistic automata

Abstract:

In this paper, we propose a new randomised algorithm for deciding language equivalence for probabilistic automata. This algorithm is based on polynomial identity testing and thus returns an answer with an error probability that can be made arbitrarily small. We implemented our algorithm, as well as deterministic algorithms of Tzeng and Doyen et al., optimised for running time whilst adequately handling issues of numerical stability. We conducted extensive benchmarking experiments, including t...

Expand abstract

Actions


Access Document


Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Journal:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume:
6806 LNCS
Pages:
526-540
Publication date:
2011-01-01
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
Source identifiers:
304663
Language:
English
Pubs id:
pubs:304663
UUID:
uuid:89667f45-8b34-4954-8315-ba4a0c551e85
Local pid:
pubs:304663
Deposit date:
2012-12-19

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP