Weak Bisimulation for Fully Probabilistic Processes

Christel BaierChristel Baier, Holger HermannsHolger Hermanns

DOI Link

Christel Baier, Holger Hermanns
Weak Bisimulation for Fully Probabilistic Processes
9th International Conference on Computer Aided Verification (CAV), volume 1254 of Lecture Notes in Computer Science, 119--130, 1997. Springer

Details
Bibtex

KurzfassungAbstract
Bisimulations that abstract from internal computation have proven to be useful for verification of compositionally defined transition system. In the literature of probabilistic extensions of such transition systems, similar bisimulations are rare. In this paper, we introduce weak bisimulation and branching bisimulation for transition systems where nondeterministic branching is replaced by probabilistic branching. In contrast to the nondeterministic case, both relations coincide. We give an algorithm to decide weak bisimulation with a time complexity cubic in the number of states of the transition system. This meets the worst case complexity for deciding branching bisimulation in the nondeterministic case.
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-63166-6_14.

@inproceedings{BH1997,
  author    = {Christel Baier and Holger Hermanns},
  title     = {Weak Bisimulation for Fully Probabilistic Processes},
  booktitle = {9th International Conference on Computer Aided Verification (CAV)},
  series    = {Lecture Notes in Computer Science},
  volume    = {1254},
  publisher = {Springer},
  year      = {1997},
  pages     = {119--130},
  doi       = {10.1007/3-540-63166-6_14}
}