A logical duality for underspecified probabilistic systems

详细信息    查看全文

• 作者：José ; e Desharnais ; ^a ; ^{josee.desharnais@ift.ulaval.ca} ; Franç ; ois Laviolette^a ; ^{francois.laviolette@ift.ulaval.ca} ; Amé ; lie Turgeon^a ; ^{amelie.turgeon@ift.ulaval.ca}
• 关键词：Probabilistic processes ; Duality ; Modal logic ; Underspecified processes ; Bisimulation ; Galois connection
• 刊名：Information and Computation
• 出版年：2011
• 出版时间：May 2011
• 年：2011
• 卷：209
• 期：5
• 页码：850-871
• 全文大小：636 K

文摘

This paper establishes a Stone-type duality between specifications and infLMPs. An infLMP is a probabilistic process whose transitions satisfy super-additivity instead of additivity. Interestingly, its simple structure can encode a mix of probabilistic and non-deterministic behavior, which, as we show, is strongly related to another well-known such model: probabilistic automata. Our duality puts in relation the category of infLMPs and a category of abstract representations of them based on properties only. We exhibit a Galois connection between these categories and show that we have an adjunct pair of functors when restricted to LMPs only. Our duality also shows that an infLMP can be considered as a demonic representative of a system’s information. Moreover, it carries forward a view where states are less important, and events, or properties, become the main characters, as it should be in probability theory. Along the way, we show that bisimulation and simulation are naturally interpreted in this setting, and we exhibit the interesting relationship between infLMPs and the usual probabilistic modal logics. This paper is an extended version of a Concur ’09 paper [13]; in particular, the comparison of infLMPs with probabilistic automata and the Galois connection are new.