Approximating Bisimilarity for Markov Processes

In this paper we investigate bisimilarity for general Markov processes through the correspondence between sub-σ-algebras and equivalence relations. In particular, we study bisimulations from the perspective of fixed-point theory. Given a Markov process M=〈Ω,Σ,τ〉, we characterize its state bisimilari...

Full description

Saved in:
Bibliographic Details
Published in:Electronic notes in theoretical computer science 2013-11, Vol.298, p.427-440
Main Author: Zhou, Chunlai
Format: Article
Language:English
Subjects:
event bisimilarity
fixed point
Hennessy-Milner logic
Markov processes
state bisimilarity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper we investigate bisimilarity for general Markov processes through the correspondence between sub-σ-algebras and equivalence relations. In particular, we study bisimulations from the perspective of fixed-point theory. Given a Markov process M=〈Ω,Σ,τ〉, we characterize its state bisimilarity as the greatest fixed point of a composition of two natural set operators between equivalence relations on Ω and sub-σ-algebras of Σ. Moreover, we employ a Smith-Volterra-Cantor-set-construction to obtain an example to show that state bisimilarity is beyond ω iterations of these two operators alternately from event bisimilarity and hence the composite operator is not continuous. This process of iteration illustrates the gap between event bisimilarity (or logical equivalence) and state bisimilarity, and hence provides insights about the Hennessy-Milner property for general Markov processes. At the end of this paper, we also study approximation of Markov processes related to filtration.
ISSN:1571-0661
1571-0661
DOI:10.1016/j.entcs.2013.12.007