UCL Discovery
UCL home » Library Services » Electronic resources » UCL Discovery

The power of convex algebras

Bonchi, F; Silva, A; Sokolova, A; (2017) The power of convex algebras. In: Meyer, R and Nestmann, U, (eds.) 28th International Conference on Concurrency Theory (CONCUR 2017). (pp. 23:1-23:18). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik: Dagstuhl, Germany. Green open access

[img]
Preview
Text
The power of convex algebras.pdf - Published version

Download (681kB) | Preview

Abstract

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 beliefstate 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.

Type: Proceedings paper
Title: The power of convex algebras
Event: 28th International Conference on Concurrency Theory (CONCUR 2017), 5-8 September 2017, Berlin, Germany
ISBN-13: 9783959770484
Open access status: An open access version is available from UCL Discovery
DOI: 10.4230/LIPIcs.CONCUR.2017.23
Publisher version: http://dx.doi.org/10.4230/LIPIcs.CONCUR.2017.23
Language: English
Additional information: Copyright © Filippo Bonchi, Alexandra Silva, and Ana Sokolova. Licensed under the Creative Commons License CC-BY (https://creativecommons.org/licenses/by/3.0/).
Keywords: belief-state transformers, bisimulation up-to, coalgebra, convex algebra, convex powerset monad, probabilistic automata
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: https://discovery.ucl.ac.uk/id/eprint/10027982
Downloads since deposit
8Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item