Unprovability of the logical characterization of bisimulation

详细信息    查看全文

• 作者：Pedro Sá ; nchez Terraf¹ ; ^a ; ^{sterraf@famaf.unc.edu.ar"" rel=""nofollow}
• 关键词：Labelled Markov process ; Probabilistic bisimulation ; Modal logic ; Nonmeasurable set
• 刊名：Information and Computation
• 出版年：2011
• 出版时间：July 2011
• 年：2011
• 卷：209
• 期：7
• 页码：1048-1056
• 全文大小：186 K

文摘

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