Document Open Access Logo

Presenting Convex Sets of Probability Distributions by Convex Semilattices and Unique Bases ((Co)algebraic pearls)

Authors Filippo Bonchi, Ana Sokolova, Valeria Vignudelli

PDF
Thumbnail PDF

File

LIPIcs.CALCO.2021.11.pdf
  • Filesize: 0.75 MB
  • 18 pages

Document Identifiers

Author Details

Filippo Bonchi
  • University of Pisa, Italy
Ana Sokolova
  • University of Salzburg, Austria
Valeria Vignudelli
  • Univ Lyon, CNRS, ENS Lyon, UCB Lyon 1, LIP, France

Funding

  • Bonchi, Filippo: Supported by the Ministero dell’Università e della Ricerca of Italy under Grant No. 201784YSZ5, PRIN2017 – ASPRA (Analysis of Program Analyses).
  • Vignudelli, Valeria: Supported by the French projects ANR-20-CE48-0005 QuaReMe and ANR-16-CE25-0011 REPAS, the European Research Council (ERC) under the European Union’s Horizon 2020 programme (CoVeCe, grant agreement No 678157), the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).

Cite As Get BibTex

Filippo Bonchi, Ana Sokolova, and Valeria Vignudelli. Presenting Convex Sets of Probability Distributions by Convex Semilattices and Unique Bases ((Co)algebraic pearls). In 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 211, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.CALCO.2021.11

Abstract

We prove that every finitely generated convex set of finitely supported probability distributions has a unique base. We apply this result to provide an alternative proof of a recent result: the algebraic theory of convex semilattices presents the monad of convex sets of probability distributions.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic and verification
  • Theory of computation → Axiomatic semantics
  • Theory of computation → Categorical semantics
Keywords
  • Convex sets of distributions monad
  • Convex semilattices
  • Unique base

Metrics

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

References

  1. Christel Baier and Joost-Pieter Katoen. Principles of model checking. MIT Press, 2008. Google Scholar
  2. Filippo Bonchi, Alexandra Silva, and Ana Sokolova. The Power of Convex Algebras. In CONCUR 2017, volume 85, pages 23:1-23:18. LIPIcs, 2017. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2017.23.
  3. Filippo Bonchi, Ana Sokolova, and Valeria Vignudelli. The theory of traces for systems with nondeterminism and probability. Extended version of paper in Proc.LICS'19, 2019. URL: http://arxiv.org/abs/1808.00923v3.
  4. Pablo Samuel Castro, Prakash Panangaden, and Doina Precup. Equivalence relations in fully and partially observable markov decision processes. In IJCAI, pages 1653-1658, 2009. Google Scholar
  5. Christian Dehnert, Sebastian Junges, Joost-Pieter Katoen, and Matthias Volk. A storm is coming: A modern probabilistic model checker. In Proc. CAV 2017, volume 10427 of LNCS, pages 592-600, 2017. Google Scholar
  6. Nachum Dershowitz. Orderings for term-rewriting systems. Theoretical computer science, 17(3):279-301, 1982. Google Scholar
  7. Ernst-Erich Doberkat. Eilenberg-Moore algebras for stochastic relations. Inform. and Comput., 204(12):1756-1781, 2006. URL: https://doi.org/10.1016/j.ic.2006.09.001.
  8. Ernst-Erich Doberkat. Erratum and addendum: Eilenberg-Moore algebras for stochastic relations [mr2277336]. Inform. and Comput., 206(12):1476-1484, 2008. URL: https://doi.org/10.1016/j.ic.2008.08.002.
  9. Jean Goubault-Larrecq. Prevision domains and convex powercones. In FOSSACS 2008, pages 318-333. LNCS 4962, 2008. URL: https://doi.org/10.1007/978-3-540-78499-9_23.
  10. Alexandre Goy and Daniela Petrisan. Combining probabilistic and non-deterministic choice via weak distributive laws. In Holger Hermanns, Lijun Zhang, Naoki Kobayashi, and Dale Miller, editors, LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020, pages 454-464. ACM, 2020. URL: https://doi.org/10.1145/3373718.3394795.
  11. Hans A Hansson. Time and probability in formal design of distributed systems. PhD thesis, Uppsala University, 1991. Google Scholar
  12. Holger Hermanns, Jan Krcál, and Jan Kretínský. Probabilistic bisimulation: Naturally on distributions. In Proc. CONCUR'14, volume 8704 of LNCS, pages 249-265, 2014. Google Scholar
  13. Holger Hermanns, Augusto Parma, Roberto Segala, Björn Wachter, and Lijun Zhang. Probabilistic logical characterization. Information and Computation, 209(2):154-172, 2011. Google Scholar
  14. Chris Heunen, Ohad Kammar, Sam Staton, and Hongseok Yang. A convenient category for higher-order probability theory. CoRR, abs/1701.02547, 2017. URL: http://arxiv.org/abs/1701.02547.
  15. B. Jacobs. Convexity, duality and effects. In Theoretical computer science, volume 323 of IFIP Adv. Inf. Commun. Technol., pages 1-19. Springer, Berlin, 2010. URL: https://doi.org/10.1007/978-3-642-15240-5_1.
  16. Bart Jacobs. Coalgebraic trace semantics for combined possibilitistic and probabilistic systems. Electr. Notes Theor. Comput. Sci., 203(5):131-152, 2008. Google Scholar
  17. Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and Acting in Partially Observable Stochastic Domains. Artif. Intell., 1998. Google Scholar
  18. Klaus Keimel and Gordon D. Plotkin. Mixed powerdomains for probability and nondeterminism. Logical Methods in Computer Science, 13(1), 2017. URL: https://doi.org/10.23638/LMCS-13(1:2)2017.
  19. Marta Z. Kwiatkowska, Gethin Norman, and David Parker. Prism: Probabilistic symbolic model checker. In Computer Performance Evaluation / TOOLS, pages 200-204. LNCS 2324, 2002. Google Scholar
  20. Matteo Mio. Upper-expectation bisimilarity and łukasiewicz μ-calculus. In Proc. FOSSACS'14, volume 8412 of LNCS, pages 335-350, 2014. Google Scholar
  21. Matteo Mio, Ralph Sarkis, and Valeria Vignudelli. Combining nondeterminism, probability, and termination: Equational and metric reasoning. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021, Rome, Italy, June 29 - July 2, 2021, pages 1-14. IEEE, 2021. URL: https://doi.org/10.1109/LICS52264.2021.9470717.
  22. Matteo Mio and Valeria Vignudelli. Monads and quantitative equational theories for nondeterminism and probability. In Igor Konnov and Laura Kovács, editors, 31st International Conference on Concurrency Theory, CONCUR 2020, September 1-4, 2020, Vienna, Austria (Virtual Conference), volume 171 of LIPIcs, pages 28:1-28:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2020.28.
  23. M. Mislove, J. Ouaknine, and J. Worrell. Axioms for probability and nondeterminism. In Proc. of the 10th Int. Workshop on Expressiveness in Concurrency (EXPRESS 2003), volume 96 of ENTCS, pages 7-28. Elsevier, 2003. Google Scholar
  24. Michael W. Mislove. Nondeterminism and probabilistic choice: Obeying the laws. In CONCUR 2000, pages 350-364. LNCS 1877, 2000. URL: https://doi.org/10.1007/3-540-44618-4_26.
  25. Walter Rudin. Functional Analysis. McGraw-Hill, 1991. Google Scholar
  26. Stuart Russell and Peter Norvig. Artificial Intelligence: A Modern Approach. Prentice Hall, 2009. Google Scholar
  27. Roberto Segala and Nancy Lynch. Probabilistic simulations for probabilistic processes. Nordic Journal of Computing, 2(2):250-273, 1995. 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. Sam Staton, Hongseok Yang, Frank Wood, Chris Heunen, and Ohad Kammar. Semantics for probabilistic programming: higher-order functions, continuous distributions, and soft constraints. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '16, New York, NY, USA, July 5-8, 2016, pages 525-534, 2016. URL: https://doi.org/10.1145/2933575.2935313.
  30. T. Świrszcz. Monadic functors and convexity. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 22:39-42, 1974. Google Scholar
  31. Regina Tix, Klaus Keimel, and Gordon D. Plotkin. Semantic domains for combining probability and non-determinism. ENTCS, 222:3-99, 2009. URL: https://doi.org/10.1016/j.entcs.2009.01.002.
  32. R. Tyllerr. Convex Analysis. Princeton University Press, 1972. Google Scholar
  33. D. Varacca. Probability, Nondeterminism and Concurrency: Two Denotational Models for Probabilistic Computation. PhD thesis, Univ. Aarhus, 2003. BRICS Dissertation Series, DS-03-14. Google Scholar
  34. D. Varacca and G. Winskel. Distributing probabililty over nondeterminism. MSCS, 16(1):87-113, 2006. Google Scholar
  35. Moshe Y Vardi. Automatic verification of probabilistic concurrent finite state programs. In Foundations of Computer Science, 1985., 26th Annual Symposium on, pages 327-338. IEEE, 1985. 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 About DROPS Imprint Privacy Contact