article · 2008

Weak Bisimulation for Fully Probabilistic Processes Abstract

Christel Baier A, Holger Hermanns B

Cited by 0Abstract and details only

Abstract

Bisimulations that abstract from internal computation have proven to be useful for verification of compositionally defined transition systems. In the literature of probabilistic extensions of such transition systems, similar bisimulations are rare. In this paper, we introduce weak and branching bisimulation for fully probabilistic systems, 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 (and branching) bisimulation with a time complexity cubic in the number of states of the fully probabilistic system. This meets the worst case complexity for deciding branching bisimulation in the nondeterministic case. In addition, the relation is shown to be a congruence with respect to the operators of PLSCCS, a lazy synchronous probabilistic variant of CCS. We illustrate that due to these properties, weak bisimulation provides all the crucial ingredients

Cite this paper

APA 7

A, C. B., & B, H. H. (2008). Weak Bisimulation for Fully Probabilistic Processes Abstract.

MLA 9

A, Christel Baier, and Holger Hermanns B. “Weak Bisimulation for Fully Probabilistic Processes Abstract.” 2008.

Chicago

A, Christel Baier, and Holger Hermanns B. 2008. “Weak Bisimulation for Fully Probabilistic Processes Abstract.”

Harvard

A, C.B. and B, H.H. (2008) ‘Weak Bisimulation for Fully Probabilistic Processes Abstract’.

BibTeX

@article{a2008weak,
  title = {{Weak Bisimulation for Fully Probabilistic Processes Abstract}},
  author = {A, Christel Baier and B, Holger Hermanns},
  year = {2008}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.