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


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Journal:
FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATIONAL STRUCTURES, FOSSACS 2012
Volume:
7213
Pages:
467-481
Publication date:
2012-01-01
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


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