@inproceedings{5679,
  abstract     = {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.},
  author       = {Huang, Mingzhang and Fu, Hongfei and Chatterjee, Krishnendu},
  editor       = {Ryu, Sukyoung},
  isbn         = {9783030027674},
  issn         = {03029743},
  location     = {Wellington, New Zealand},
  pages        = {181--201},
  publisher    = {Springer},
  title        = {{New approaches for almost-sure termination of probabilistic programs}},
  doi          = {10.1007/978-3-030-02768-1_11},
  volume       = {11275},
  year         = {2018},
}