1 Search Results for "Aguirre, Alejandro"

Document
DOI: 10.4230/LIPIcs.ICALP.2018.113
Almost Sure Productivity

Authors: Alejandro Aguirre, Gilles Barthe, Justin Hsu, and Alexandra Silva

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
We introduce Almost Sure Productivity (ASP), a probabilistic generalization of the productivity condition for coinductively defined structures. Intuitively, a probabilistic coinductive stream or tree is ASP if it produces infinitely many outputs with probability 1. Formally, we define ASP using a final coalgebra semantics of programs inspired by Kerstan and König. Then, we introduce a core language for probabilistic streams and trees, and provide two approaches to verify ASP: a syntactic sufficient criterion, and a decision procedure by reduction to model{-}checking LTL formulas on probabilistic pushdown automata.
Cite as

Alejandro Aguirre, Gilles Barthe, Justin Hsu, and Alexandra Silva. Almost Sure Productivity. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 113:1-113:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{aguirre_et_al:LIPIcs.ICALP.2018.113,
  author =	{Aguirre, Alejandro and Barthe, Gilles and Hsu, Justin and Silva, Alexandra},
  title =	{{Almost Sure Productivity}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{113:1--113:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.113},
  URN =		{urn:nbn:de:0030-drops-91174},
  doi =		{10.4230/LIPIcs.ICALP.2018.113},
  annote =	{Keywords: Coinduction, Probabilistic Programming, Productivity}
}
  • Refine by Author
  • 1 Aguirre, Alejandro
  • 1 Barthe, Gilles
  • 1 Hsu, Justin
  • 1 Silva, Alexandra

  • Refine by Classification
  • 1 Theory of computation → Denotational semantics
  • 1 Theory of computation → Probabilistic computation
  • 1 Theory of computation → Program reasoning

  • Refine by Keyword
  • 1 Coinduction
  • 1 Probabilistic Programming
  • 1 Productivity

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

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