Unprovability of the Logical Characterization of Bisimulation

PEDRO SÁNCHEZ TERRAF

Information and Computation

ACADEMIC PRESS INC ELSEVIER SCIENCE

Lugar: Amsterdam; Año: 2011 vol. 209 p. 1048 - 1056

0890-5401

We quickly review labelled Markov processes (LMP) and provide a counterexample showingthat in general measurable spaces, event bisimilarity and state bisimilarity differ in LMP.This shows that the Hennessy–Milner logic proposed by Desharnais does not characterizestate bisimulation in non-analytic measurable spaces. Furthermore we show that, undercurrent foundations of Mathematics, such logical characterization is unprovable for spacesthat are projections of a coanalytic set. Underlying this construction there is a proof thatstationary Markov processes over general measurable spaces do not have semi-pullbacks.