文章基本信息

标题：The Power of Convex Algebras
本地全文：下载
作者：Filippo Bonchi ; Alexandra Silva ; Ana Sokolova 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：85
页码：23:1-23:18
DOI：10.4230/LIPIcs.CONCUR.2017.23
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Probabilistic automata (PA) combine probability and nondeterminism. They can be given different semantics, like strong bisimilarity, convex bisimilarity, or (more recently) distribution bisimilarity. The latter is based on the view of PA as transformers of probability distributions, also called belief states, and promotes distributions to first-class citizens. We give a coalgebraic account of the latter semantics, and explain the genesis of the belief-state transformer from a PA. To do so, we make explicit the convex algebraic structure present in PA and identify belief-state transformers as transition systems with state space that carries a convex algebra. As a consequence of our abstract approach, we can give a sound proof technique which we call bisimulation up-to convex hull.
关键词：belief-state transformers; bisimulation up-to; coalgebra; convex algebra; convex powerset monad; probabilistic automata