Polynomial Time Algorithms for Testing Probabilistic Bisimulation and Simulation

Christel BaierChristel Baier

DOI Link

Christel Baier
Polynomial Time Algorithms for Testing Probabilistic Bisimulation and Simulation
8th International Conference on Computer Aided Verification (CAV), volume 1102 of Lecture Notes in Computer Science, 50--61, 1996. Springer

Details
Bibtex

KurzfassungAbstract
Various models and equivalence relations or preorders for probabilistic processes are proposed in the literature. This paper deals with a model based on labelled transition systems extended to the probabalistic setting and gives an O(n^2·m) algorithm for testing probabilistic bisimulation and an O (n^5 ·m^2) algorithm for testing probabilistic simulation where n is the number of states and m the number of transitions in the underlying probabilistic transition systems.
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/3-540-61474-5_57.

@inproceedings{B1996,
  author    = {Christel Baier},
  title     = {Polynomial Time Algorithms for Testing Probabilistic Bisimulation
               and Simulation},
  booktitle = {8th International Conference on Computer Aided Verification (CAV)},
  series    = {Lecture Notes in Computer Science},
  volume    = {1102},
  publisher = {Springer},
  year      = {1996},
  pages     = {50--61},
  doi       = {10.1007/3-540-61474-5_57}
}