Journal article icon

Journal article

On the Complexity of the Equivalence Problem for Probabilistic Automata

Abstract:

Deciding equivalence of probabilistic automata is a key problem for establishing various behavioural and anonymity properties of probabilistic systems. In recent experiments a randomised equivalence test based on polynomial identity testing outperformed deterministic algorithms. In this paper we show that polynomial identity testing yields efficient algorithms for various generalisations of the equivalence problem. First, we provide a randomized NC procedure that also outputs a counterexample...

Expand abstract
Publication status:
Published

Actions


Access Document


Authors


Murawski, AS More by this author
Ouaknine, J More by this author
Wachter, B More by this author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Journal:
FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATIONAL STRUCTURES, FOSSACS 2012
Volume:
7213
Pages:
467-481
Publication date:
2012
DOI:
EISSN:
1611-3349
ISSN:
0302-9743
URN:
uuid:543a9e46-04b5-4a60-9352-9d761598bbc0
Source identifiers:
323276
Local pid:
pubs:323276
Language:
English

Terms of use


Metrics



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

TO TOP