---
res:
bibo_abstract:
- "We consider the problem of expected cost analysis over nondeterministic probabilistic
programs,\r\nwhich aims at automated methods for analyzing the resource-usage
of such programs.\r\nPrevious approaches for this problem could only handle nonnegative
bounded costs.\r\nHowever, in many scenarios, such as queuing networks or analysis
of cryptocurrency protocols,\r\nboth positive and negative costs are necessary
and the costs are unbounded as well.\r\n\r\nIn this work, we present a sound and
efficient approach to obtain polynomial bounds on the\r\nexpected accumulated
cost of nondeterministic probabilistic programs.\r\nOur approach can handle (a)
general positive and negative costs with bounded updates in\r\nvariables; and
(b) nonnegative costs with general updates to variables.\r\nWe show that several
natural examples which could not be\r\nhandled by previous approaches are captured
in our framework.\r\n\r\nMoreover, our approach leads to an efficient polynomial-time
algorithm, while no\r\nprevious approach for cost analysis of probabilistic programs
could guarantee polynomial runtime.\r\nFinally, we show the effectiveness of our
approach using experimental results on a variety of programs for which we efficiently
synthesize tight resource-usage bounds.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Peixin
foaf_name: Wang, Peixin
foaf_surname: Wang
- foaf_Person:
foaf_givenName: Hongfei
foaf_name: Fu, Hongfei
foaf_surname: Fu
foaf_workInfoHomepage: http://www.librecat.org/personId=3AAD03D6-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Amir Kafshdar
foaf_name: Goharshady, Amir Kafshdar
foaf_surname: Goharshady
foaf_workInfoHomepage: http://www.librecat.org/personId=391365CE-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0003-1702-6584
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Xudong
foaf_name: Qin, Xudong
foaf_surname: Qin
- foaf_Person:
foaf_givenName: Wenjun
foaf_name: Shi, Wenjun
foaf_surname: Shi
bibo_doi: 10.1145/3314221.3314581
dct_date: 2019^xs_gYear
dct_language: eng
dct_publisher: Association for Computing Machinery@
dct_subject:
- Program Cost Analysis
- Program Termination
- Probabilistic Programs
- Martingales
dct_title: Cost analysis of nondeterministic probabilistic programs@
...