2 Search Results for "Mio, Matteo"

Document
DOI: 10.4230/LIPIcs.CONCUR.2020.28
Monads and Quantitative Equational Theories for Nondeterminism and Probability

Authors: Matteo Mio and Valeria Vignudelli

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

Abstract
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.
Cite as

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
DOI: 10.4230/LIPIcs.FSTTCS.2015.489
On the Problem of Computing the Probability of Regular Sets of Trees

Authors: Henryk Michalewski and Matteo Mio

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

Abstract
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.
Cite as

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}
}
  • Refine by Author
  • 2 Mio, Matteo
  • 1 Michalewski, Henryk
  • 1 Vignudelli, Valeria

  • Refine by Classification
  • 1 Theory of computation → Axiomatic semantics
  • 1 Theory of computation → Categorical semantics
  • 1 Theory of computation → Logic and verification

  • Refine by Keyword
  • 1 Computational Effects
  • 1 Metric Spaces
  • 1 Monads
  • 1 Quantitative Algebras
  • 1 meta-parity games
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2015
  • 1 2020

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