Bisimulation and simulation algorithms on probabilistic transition systems by abstract interpretation

摘要

We show how bisimulation equivalence and simulation preorder on probabilistic LTSs (PLTSs), namely the main behavioural relations on probabilistic nondeterministic processes, can be characterized by abstract interpretation. Both bisimulation and simulation can be obtained as completions of partitions and preorders, viewed as abstract domains, w.r.t. a pair of concrete functions that encode a PLTS. This approach provides a general framework for designing algorithms that compute bisimulation and simulation on PLTSs. Notably, (i) we show that the standard bisimulation algorithm by Baier et al. (2000) can be viewed as an instance of such a framework and (ii) we design a new efficient simulation algorithm that improves the state of the art.