---
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_identifier:
  - UT:000523190300014
  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@
...