Document

**Published in:** LIPIcs, Volume 171, 31st International Conference on Concurrency Theory (CONCUR 2020)

The monad of convex sets of probability distributions is a well-known tool for modelling the combination of nondeterministic and probabilistic computational effects. In this work we lift this monad from the category of sets to the category of extended metric spaces, by means of the Hausdorff and Kantorovich metric liftings. Our main result is the presentation of this lifted monad in terms of the quantitative equational theory of convex semilattices, using the framework of quantitative algebras recently introduced by Mardare, Panangaden and Plotkin.

Matteo Mio and Valeria Vignudelli. Monads and Quantitative Equational Theories for Nondeterminism and Probability. In 31st International Conference on Concurrency Theory (CONCUR 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 171, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{mio_et_al:LIPIcs.CONCUR.2020.28, author = {Mio, Matteo and Vignudelli, Valeria}, title = {{Monads and Quantitative Equational Theories for Nondeterminism and Probability}}, booktitle = {31st International Conference on Concurrency Theory (CONCUR 2020)}, pages = {28:1--28:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-160-3}, ISSN = {1868-8969}, year = {2020}, volume = {171}, editor = {Konnov, Igor and Kov\'{a}cs, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2020.28}, URN = {urn:nbn:de:0030-drops-128407}, doi = {10.4230/LIPIcs.CONCUR.2020.28}, annote = {Keywords: Computational Effects, Monads, Metric Spaces, Quantitative Algebras} }

Document

**Published in:** LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

We consider the problem of computing the probability of regular languages of infinite trees with respect to the natural coin-flipping measure. We propose an algorithm which computes the probability of languages recognizable by game automata. In particular this algorithm is applicable to all deterministic automata. We then use the algorithm to prove through examples three properties of measure: (1) there exist regular sets having irrational probability, (2) there exist comeager regular sets having probability 0 and (3) the probability of game languages W_{i,k}, from automata theory, is 0 if k is odd and is 1 otherwise.

Henryk Michalewski and Matteo Mio. On the Problem of Computing the Probability of Regular Sets of Trees. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 489-502, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{michalewski_et_al:LIPIcs.FSTTCS.2015.489, author = {Michalewski, Henryk and Mio, Matteo}, title = {{On the Problem of Computing the Probability of Regular Sets of Trees}}, booktitle = {35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)}, pages = {489--502}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-97-2}, ISSN = {1868-8969}, year = {2015}, volume = {45}, editor = {Harsha, Prahladh and Ramalingam, G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.489}, URN = {urn:nbn:de:0030-drops-56390}, doi = {10.4230/LIPIcs.FSTTCS.2015.489}, annote = {Keywords: regular languages of trees, probability, meta-parity games} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail