Informatics Report Series


Report   

EDI-INF-RR-1170


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Bisimulation and cocongruence for probabilistic systems
Authors: Vincent Danos ; J Desharnais ; F Laviolette ; P Panangaden
Date:Apr 2006
Publication Title:Information and Computation
Publisher:Elsevier
Publication Type:Journal Article Publication Status:Published
Volume No:204 (4) Page Nos:503-523
DOI:10.1016/j.ic.2005.02.004 ISBN/ISSN:0890-5401
Abstract:
We introduce a new notion of bisimulation, called event bisimulation on labelled Markov processes and compare it with the, now standard, notoin of probabilistic bisimulation, originally due to Larsen and Skou. Event bisimulation uses a sub sigma-algebra as the basic carrier of information rather than an equivalence relation. The resulting notion is thus based on measurable subsets rather than on points: hence the name. Event bisimulation applies smoothly for general measure spaces; bisimulation, on the other hand, is known only to work satisfactorily for analytic spaces. We prove the logical characterization theorem for event bisimulation without having to invoke any of the subtle aspects of analytic spaces that feature prominently in the corresponding proof for ordinary bisimulation. These complexities only arise when we show that on analytic spaces the two concepts coincide. We show that the concept of event bisimulation arises naturally from taking the cocongruence point of view for probabilistic systems. We show that the theory can be given a pleasing categorical treatment in line with general coalgebraic principles. As an easy application of these ideas we develop a notion of ``almost sure'' bisimulation; the theory comes almost ``for free'' once we modify Giry's monad appropriately.
Links To Paper
No links available
Bibtex format
@Article{EDI-INF-RR-1170,
author = { Vincent Danos and J Desharnais and F Laviolette and P Panangaden },
title = {Bisimulation and cocongruence for probabilistic systems},
journal = {Information and Computation},
publisher = {Elsevier},
year = 2006,
month = {Apr},
volume = {204 (4)},
pages = {503-523},
doi = {10.1016/j.ic.2005.02.004},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh