License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2017.23
URN: urn:nbn:de:0030-drops-77966
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7796/
Go to the corresponding LIPIcs Volume Portal

Bonchi, Filippo ; Silva, Alexandra ; Sokolova, Ana

The Power of Convex Algebras

pdf-format:
LIPIcs-CONCUR-2017-23.pdf (0.6 MB)

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

BibTeX - Entry

@InProceedings{bonchi_et_al:LIPIcs:2017:7796,
  author =	{Filippo Bonchi and Alexandra Silva and Ana Sokolova},
  title =	{{The Power of Convex Algebras}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{23:1--23:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Roland Meyer and Uwe Nestmann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7796},
  URN =		{urn:nbn:de:0030-drops-77966},
  doi =		{10.4230/LIPIcs.CONCUR.2017.23},
  annote =	{Keywords: belief-state transformers, bisimulation up-to, coalgebra, convex algebra, convex powerset monad, probabilistic automata}
}

Keywords: belief-state transformers, bisimulation up-to, coalgebra, convex algebra, convex powerset monad, probabilistic automata
Collection: 28th International Conference on Concurrency Theory (CONCUR 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI