[{"abstract":[{"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.","lang":"eng"}],"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1806.06683"}],"quality_controlled":"1","type":"conference","scopus_import":"1","volume":11275,"editor":[{"full_name":"Ryu, Sukyoung","last_name":"Ryu","first_name":"Sukyoung"}],"department":[{"_id":"KrCh"}],"doi":"10.1007/978-3-030-02768-1_11","day":"01","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","title":"New approaches for almost-sure termination of probabilistic programs","external_id":{"arxiv":["1806.06683"],"isi":["000916310900011"]},"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0302-9743"],"isbn":["9783030027674"]},"status":"public","alternative_title":["LNCS"],"page":"181-201","project":[{"call_identifier":"FWF","name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425"},{"grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425","name":"Efficient Algorithms for Computer Aided Verification"}],"intvolume":"     11275","arxiv":1,"oa":1,"date_created":"2018-12-16T22:59:20Z","date_updated":"2026-04-16T09:54:21Z","article_processing_charge":"No","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>","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>.","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.","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>.","short":"M. Huang, H. Fu, K. Chatterjee, in:, S. Ryu (Ed.), Springer, 2018, 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."},"_id":"5679","date_published":"2018-12-01T00:00:00Z","isi":1,"year":"2018","conference":{"start_date":"2018-12-02","end_date":"2018-12-06","name":"16th Asian Symposium on Programming Languages and Systems, APLAS","location":"Wellington, New Zealand"},"author":[{"full_name":"Huang, Mingzhang","first_name":"Mingzhang","last_name":"Huang"},{"full_name":"Fu, Hongfei","last_name":"Fu","first_name":"Hongfei"},{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"}],"month":"12","publisher":"Springer","oa_version":"Preprint"}]