Document Open Access Logo

Termination in Convex Sets of Distributions

Authors Ana Sokolova, Harald Woracek

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2017.22.pdf
  • Filesize: 0.5 MB
  • 16 pages

Document Identifiers

Author Details

Ana Sokolova
Harald Woracek

Cite AsGet BibTex

Ana Sokolova and Harald Woracek. Termination in Convex Sets of Distributions. In 7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 72, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.CALCO.2017.22

Abstract

Convex algebras, also called (semi)convex sets, are at the heart of modelling probabilistic systems including probabilistic automata. Abstractly, they are the Eilenberg-Moore algebras of the finitely supported distribution monad. Concretely, they have been studied for decades within algebra and convex geometry. In this paper we study the problem of extending a convex algebra by a single point. Such extensions enable the modelling of termination in probabilistic systems. We provide a full description of all possible extensions for a particular class of convex algebras: For a fixed convex subset D of a vector space satisfying additional technical condition, we consider the algebra of convex subsets of D. This class contains the convex algebras of convex subsets of distributions, modelling (nondeterministic) probabilistic automata. We also provide a full description of all possible extensions for the class of free convex algebras, modelling fully probabilistic systems. Finally, we show that there is a unique functorial extension, the so-called black-hole extension.
Keywords
  • convex algebra
  • one-point extensions
  • convex powerset monad

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Falk Bartels, Ana Sokolova, and Erik de Vink. A hierarchy of probabilistic system types. Theoretical Computer Science, 327:3-22, 2004. Google Scholar
  2. Filippo Bonchi, Alexandra Silva, and Ana Sokolova. The power of convex algebras, 2017. Submitted. Google Scholar
  3. Reinhard Börger and Ralf Kemper. A cogenerator for preseparated superconvex spaces. Appl. Categ. Structures, 4(4):361-370, 1996. Google Scholar
  4. Pablo Samuel Castro, Prakash Panangaden, and Doina Precup. Equivalence relations in fully and partially observable Markov decision processes. In Proc. IJCAI, pages 1653-1658, 2009. Google Scholar
  5. Silvia Crafa and Francesco Ranzato. A spectrum of behavioral relations over LTSs on probability distributions. In Proc. CONCUR, pages 124-139. LNCS 6901, 2011. Google Scholar
  6. Yuxin Deng and Matthew Hennessy. On the semantics of Markov automata. Inf. Comput., 222:139-168, 2013. Google Scholar
  7. Yuxin Deng, Rob J. van Glabbeek, Matthew Hennessy, and Carroll Morgan. Characterising testing preorders for finite probabilistic processes. LMCS, 4(4), 2008. Google Scholar
  8. Yuxin Deng, Rob J. van Glabbeek, Matthew Hennessy, and Carroll Morgan. Testing finitary probabilistic processes. In Proc. CONCUR, pages 274-288. LNCS 5710, 2009. Google Scholar
  9. Ernst-Erich Doberkat. Eilenberg-Moore algebras for stochastic relations. Inform. and Comput., 204(12):1756-1781, 2006. Google Scholar
  10. Ernst-Erich Doberkat. Erratum and addendum: Eilenberg-Moore algebras for stochastic relations. Inform. and Comput., 206(12):1476-1484, 2008. Google Scholar
  11. Joe Flood. Semiconvex geometry. J. Austral. Math. Soc. Ser. A, 30(4):496-510, 1980/81. Google Scholar
  12. Tobias Fritz. Convex spaces I: Definition and Examples. arXiv:0903.5522v3 [math.MG]. Google Scholar
  13. Stanley Gudder and Franklin Schroeck. Generalized convexity. SIAM J. Math. Anal., 11(6):984-1001, 1980. Google Scholar
  14. Holger Hermanns, Jan Krcál, and Jan Kretínský. Probabilistic bisimulation: Naturally on distributions. In Proc. CONCUR, LNCS 8704, pages 249-265, 2014. Google Scholar
  15. Bart Jacobs. Convexity, duality and effects. In Theoretical computer science, volume 323 of IFIP Adv. Inf. Commun. Technol., pages 1-19. Springer, 2010. Google Scholar
  16. Bart Jacobs, Alexandra Silva, and Ana Sokolova. Trace semantics via determinization. J. Comput. Syst. Sci., 81(5):859-879, 2015. Google Scholar
  17. Bart Jacobs, Bas Westerbaan, and Bram Westerbaan. States of convex sets. In Proc. FOSSACS, pages 87-101. LNCS 9034, 2015. Google Scholar
  18. Hellmuth Kneser. Konvexe Räume. Arch. Math., 3:198-206, 1952. Google Scholar
  19. Matteo Mio. Upper-expectation bisimilarity and łukasiewicz μ-calculus. In Proc. FOSSACS, pages 335-350. LNCS 8412, 2014. Google Scholar
  20. Walter D. Neumann. On the quasivariety of convex subsets of affine spaces. Arch. Math. (Basel), 21:11-16, 1970. Google Scholar
  21. Augusto Parma and Roberto Segala. Logical characterizations of bisimulations for discrete probabilistic systems. In Proc. FOSSACS, pages 287-301. LNCS 4423, 2007. Google Scholar
  22. Dieter Pumplün and Helmut Röhrl. Convexity theories. IV. Klein-Hilbert parts in convex modules. Appl. Categ. Structures, 3(2):173-200, 1995. Google Scholar
  23. R. Tyrrell Rockafellar. Convex analysis. Princeton Mathematical Series, No. 28. Princeton University Press, Princeton, N.J., 1970. Google Scholar
  24. Helmut Röhrl. Convexity theories. 0. Foundations. Appl. Categ. Structures, 2(1):13-43, 1994. Google Scholar
  25. Rolf Schneider. Convex bodies: the Brunn-Minkowski theory, volume 44 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1993. Google Scholar
  26. Roberto Segala. Modeling and verification of randomized distributed real-time systems. PhD thesis, MIT, 1995. Google Scholar
  27. Roberto Segala and Nancy Lynch. Probabilistic simulations for probabilistic processes. In Proc. CONCUR, pages 481-496. LNCS 836, 1994. Google Scholar
  28. Zbigniew Semadeni. Monads and their Eilenberg-Moore algebras in functional analysis. Queen’s University, Kingston, Ont., 1973. Queen’s Papers in Pure and Applied Mathematics, No. 33. Google Scholar
  29. Alexandra Silva, Filippo Bonchi, Marcello Bonsangue, and Jan Rutten. Generalizing the powerset construction, coalgebraically. In Proc. FSTTCS, pages 272-283. LIPIcs 8, 2010. Google Scholar
  30. Ana Sokolova. Probabilistic systems coalgebraically: A survey. Theoretical Computer Science, 412(38):5095-5110, 2011. Google Scholar
  31. Ana Sokolova and Harald Woracek. Termination in Convex Sets of Distributions. 25 pp., ASC Report 8, Vienna University of Technology, 2017. URL: http://www.asc.tuwien.ac.at/preprint/2017/asc08x2017.pdf.
  32. Marshall Harvey Stone. Postulates for the barycentric calculus. Ann. Mat. Pura Appl. (4), 29:25-30, 1949. Google Scholar
  33. Tadeusz Świrszcz. Monadic functors and convexity. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 22:39-42, 1974. Google Scholar
  34. Erik de Vink and Jan Rutten. Bisimulation for probabilistic transition systems: a coalgebraic approach. Theoretical Computer Science, 221:271-293, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact