Filippo Bonchi ; Alexandra Silva ; Ana Sokolova - Distribution Bisimilarity via the Power of Convex Algebras

lmcs:6158 - Logical Methods in Computer Science, July 23, 2021, Volume 17, Issue 3 - https://doi.org/10.46298/lmcs-17(3:10)2021
Distribution Bisimilarity via the Power of Convex AlgebrasArticle

Authors: Filippo Bonchi ; Alexandra Silva ; Ana Sokolova

    Probabilistic automata (PA), also known as probabilistic nondeterministic labelled transition systems, 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 distribution bisimilarity, 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.


    Volume: Volume 17, Issue 3
    Published on: July 23, 2021
    Accepted on: May 26, 2021
    Submitted on: February 26, 2020
    Keywords: Computer Science - Logic in Computer Science,F.3,G.3,F.1.2,D.2.4
    Funding:
      Source : OpenAIRE Graph
    • Automated Probabilistic Black-Box Verification; Funder: European Commission; Code: 101002697
    • Probabilistic Foundations for Networks; Funder: European Commission; Code: 679127

    4 Documents citing this article

    Consultation statistics

    This page has been seen 1275 times.
    This article's PDF has been downloaded 282 times.