Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Bisimulation and cocongruence for probabilistic systems
Danos V., Desharnais J., Laviolette F., Panangaden P. Information and Computation204 (4):503-523,2006.Type:Article
Date Reviewed: Oct 5 2006

Probabilistic transition systems (PTSs) extend classic labeled transition systems via a mechanism to represent probability. In the literature, they have been used as semantic models of probabilistic processes. Labeled Markov processes (LMPs) represent a subset of PTSs that study interacting Markov processes. This paper is focused on the probabilistic bisimulation between LMPs—that is, on a method that relates as equivalent two LMPs if and only if their probabilistic transition schemes have the same probabilistic branching structure.

The paper introduces a novel kind of probabilistic bisimulation between LMPs: event bisimulation (EB). EB is proven to be a generalization of probabilistic bisimulation. Actually, it applies to systems that have a measurable state space, while probabilistic bisimulation works only on analytic spaces.

I enjoyed the paper. It gives a clear snapshot of the related literature, and, in doing so, describes the basic notions one needs to understand to complete the paper. A logical characterization of EB is given by a set of theorems that are explained with examples. Although this is a dense paper, it is easy to read.

Reviewer:  Marco Cristani Review #: CR133397 (0708-0804)
Bookmark and Share
 
Proof Theory (F.4.1 ... )
 
 
Markov Processes (G.3 ... )
 
 
Probabilistic Computation (F.1.2 ... )
 
 
Modes Of Computation (F.1.2 )
 
 
Probability And Statistics (G.3 )
 
Would you recommend this review?
yes
no
Other reviews under "Proof Theory": Date
On the strength of temporal proofs
Andréka H., Németi I., Sain I. Theoretical Computer Science 80(2): 125-151, 1991. Type: Article
Apr 1 1992
Completion for unification
Doggaz N., Kirchner C. (ed) Theoretical Computer Science 85(2): 231-251, 1991. Type: Article
Aug 1 1992
Proof normalization with nonstandard objects
Goto S. Theoretical Computer Science 85(2): 333-351, 1991. Type: Article
Aug 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy