---
_id: '5679'
abstract:
- lang: eng
  text: We study the almost-sure termination problem for probabilistic programs. First,
    we show that supermartingales with lower bounds on conditional absolute difference
    provide a sound approach for the almost-sure termination problem. Moreover, using
    this approach we can obtain explicit optimal bounds on tail probabilities of non-termination
    within a given number of steps. Second, we present a new approach based on Central
    Limit Theorem for the almost-sure termination problem, and show that this approach
    can establish almost-sure termination of programs which none of the existing approaches
    can handle. Finally, we discuss algorithmic approaches for the two above methods
    that lead to automated analysis techniques for almost-sure termination of probabilistic
    programs.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Mingzhang
  full_name: Huang, Mingzhang
  last_name: Huang
- first_name: Hongfei
  full_name: Fu, Hongfei
  last_name: Fu
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
citation:
  ama: 'Huang M, Fu H, Chatterjee K. New approaches for almost-sure termination of
    probabilistic programs. In: Ryu S, ed. Vol 11275. Springer; 2018:181-201. doi:<a
    href="https://doi.org/10.1007/978-3-030-02768-1_11">10.1007/978-3-030-02768-1_11</a>'
  apa: 'Huang, M., Fu, H., &#38; Chatterjee, K. (2018). New approaches for almost-sure
    termination of probabilistic programs. In S. Ryu (Ed.) (Vol. 11275, pp. 181–201).
    Presented at the 16th Asian Symposium on Programming Languages and Systems, APLAS,
    Wellington, New Zealand: Springer. <a href="https://doi.org/10.1007/978-3-030-02768-1_11">https://doi.org/10.1007/978-3-030-02768-1_11</a>'
  chicago: Huang, Mingzhang, Hongfei Fu, and Krishnendu Chatterjee. “New Approaches
    for Almost-Sure Termination of Probabilistic Programs.” edited by Sukyoung Ryu,
    11275:181–201. Springer, 2018. <a href="https://doi.org/10.1007/978-3-030-02768-1_11">https://doi.org/10.1007/978-3-030-02768-1_11</a>.
  ieee: M. Huang, H. Fu, and K. Chatterjee, “New approaches for almost-sure termination
    of probabilistic programs,” presented at the 16th Asian Symposium on Programming
    Languages and Systems, APLAS, Wellington, New Zealand, 2018, vol. 11275, pp. 181–201.
  ista: Huang M, Fu H, Chatterjee K. 2018. New approaches for almost-sure termination
    of probabilistic programs. 16th Asian Symposium on Programming Languages and Systems,
    APLAS, LNCS, vol. 11275, 181–201.
  mla: Huang, Mingzhang, et al. <i>New Approaches for Almost-Sure Termination of Probabilistic
    Programs</i>. Edited by Sukyoung Ryu, vol. 11275, Springer, 2018, pp. 181–201,
    doi:<a href="https://doi.org/10.1007/978-3-030-02768-1_11">10.1007/978-3-030-02768-1_11</a>.
  short: M. Huang, H. Fu, K. Chatterjee, in:, S. Ryu (Ed.), Springer, 2018, pp. 181–201.
conference:
  end_date: 2018-12-06
  location: Wellington, New Zealand
  name: 16th Asian Symposium on Programming Languages and Systems, APLAS
  start_date: 2018-12-02
date_created: 2018-12-16T22:59:20Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2026-04-16T09:54:21Z
day: '01'
department:
- _id: KrCh
doi: 10.1007/978-3-030-02768-1_11
editor:
- first_name: Sukyoung
  full_name: Ryu, Sukyoung
  last_name: Ryu
external_id:
  arxiv:
  - '1806.06683'
  isi:
  - '000916310900011'
intvolume: '     11275'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1806.06683
month: '12'
oa: 1
oa_version: Preprint
page: 181-201
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
publication_identifier:
  isbn:
  - '9783030027674'
  issn:
  - 0302-9743
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: New approaches for almost-sure termination of probabilistic programs
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 11275
year: '2018'
...