Name
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
the verification of randomised anonymity protocols, the outcome of which establishes that the randomised algorithm significantly
outperforms the deterministic ones in a majority of our test cases. Finally, we also provide fine-grained analytical bounds
on the complexity of these algorithms, accounting for the differences in performance.
|
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-22110-1_42 | CAV |
Keywords | DocType | Citations |
deterministic algorithm,error probability,randomised anonymity protocol,language equivalence,extensive benchmarking experiment,numerical stability,probabilistic automaton,analytical bound,polynomial identity testing,new randomised algorithm,randomised algorithm | Conference | 21 |
PageRank | References | Authors |
0.97 | 21 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stefan Kiefer | 1 | 345 | 36.87 |
| Andrzej S. Murawski | 2 | 324 | 32.93 |
| Joël Ouaknine | 3 | 1481 | 99.25 |
| Björn Wachter | 4 | 326 | 20.09 |
| James Worrell | 5 | 1040 | 81.17 |