[{"project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"},{"name":"Quantitative Analysis of Probablistic Systems with a focus on Crypto-currencies","_id":"267066CE-B435-11E9-9278-68D0E5697425"}],"citation":{"apa":"Wang, J., Sun, Y., Fu, H., Chatterjee, K., & Goharshady, A. K. (2021). Quantitative analysis of assertion violations in probabilistic programs. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (pp. 1171–1186). Online: Association for Computing Machinery. https://doi.org/10.1145/3453483.3454102","ama":"Wang J, Sun Y, Fu H, Chatterjee K, Goharshady AK. Quantitative analysis of assertion violations in probabilistic programs. In: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. Association for Computing Machinery; 2021:1171-1186. doi:10.1145/3453483.3454102","ieee":"J. Wang, Y. Sun, H. Fu, K. Chatterjee, and A. K. Goharshady, “Quantitative analysis of assertion violations in probabilistic programs,” in Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Online, 2021, pp. 1171–1186.","short":"J. Wang, Y. Sun, H. Fu, K. Chatterjee, A.K. Goharshady, in:, Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2021, pp. 1171–1186.","mla":"Wang, Jinyi, et al. “Quantitative Analysis of Assertion Violations in Probabilistic Programs.” Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2021, pp. 1171–86, doi:10.1145/3453483.3454102.","ista":"Wang J, Sun Y, Fu H, Chatterjee K, Goharshady AK. 2021. Quantitative analysis of assertion violations in probabilistic programs. Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. PLDI: Programming Language Design and Implementation, 1171–1186.","chicago":"Wang, Jinyi, Yican Sun, Hongfei Fu, Krishnendu Chatterjee, and Amir Kafshdar Goharshady. “Quantitative Analysis of Assertion Violations in Probabilistic Programs.” In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, 1171–86. Association for Computing Machinery, 2021. https://doi.org/10.1145/3453483.3454102."},"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","external_id":{"arxiv":["2011.14617"],"isi":["000723661700076"]},"article_processing_charge":"No","author":[{"last_name":"Wang","full_name":"Wang, Jinyi","first_name":"Jinyi"},{"full_name":"Sun, Yican","last_name":"Sun","first_name":"Yican"},{"full_name":"Fu, Hongfei","last_name":"Fu","id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","first_name":"Hongfei"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","first_name":"Amir Kafshdar","full_name":"Goharshady, Amir Kafshdar","orcid":"0000-0003-1702-6584","last_name":"Goharshady"}],"title":"Quantitative analysis of assertion violations in probabilistic programs","acknowledgement":"We are very thankful to the anonymous reviewers for the helpful and valuable comments. The work was partially supported by the National Natural Science Foundation of China (NSFC) Grant No. 61802254, the Huawei Innovation Research Program, the ERC CoG 863818 (ForM-SMArt), the Facebook PhD Fellowship Program and DOC Fellowship #24956 of the Austrian Academy of Sciences (ÖAW).","oa":1,"quality_controlled":"1","publisher":"Association for Computing Machinery","year":"2021","isi":1,"publication":"Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation","day":"01","page":"1171-1186","date_created":"2021-07-11T22:01:18Z","doi":"10.1145/3453483.3454102","date_published":"2021-06-01T00:00:00Z","_id":"9646","conference":{"name":"PLDI: Programming Language Design and Implementation","location":"Online","end_date":"2021-06-26","start_date":"2021-06-20"},"type":"conference","status":"public","date_updated":"2023-08-10T14:14:08Z","department":[{"_id":"KrCh"}],"abstract":[{"text":"We consider the fundamental problem of deriving quantitative bounds on the probability that a given assertion is violated in a probabilistic program. We provide automated algorithms that obtain both lower and upper bounds on the assertion violation probability. The main novelty of our approach is that we prove new and dedicated fixed-point theorems which serve as the theoretical basis of our algorithms and enable us to reason about assertion violation bounds in terms of pre and post fixed-point functions. To synthesize such fixed-points, we devise algorithms that utilize a wide range of mathematical tools, including repulsing ranking supermartingales, Hoeffding's lemma, Minkowski decompositions, Jensen's inequality, and convex optimization. On the theoretical side, we provide (i) the first automated algorithm for lower-bounds on assertion violation probabilities, (ii) the first complete algorithm for upper-bounds of exponential form in affine programs, and (iii) provably and significantly tighter upper-bounds than the previous approaches. On the practical side, we show our algorithms can handle a wide variety of programs from the literature and synthesize bounds that are remarkably tighter than previous results, in some cases by thousands of orders of magnitude.","lang":"eng"}],"oa_version":"Preprint","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2011.14617"}],"scopus_import":"1","month":"06","publication_status":"published","publication_identifier":{"isbn":["9781450383912"]},"language":[{"iso":"eng"}],"ec_funded":1},{"doi":"10.1145/3453483.3454076","date_published":"2021-06-01T00:00:00Z","date_created":"2021-07-11T22:01:17Z","page":"772-787","day":"01","publication":"Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation","isi":1,"year":"2021","quality_controlled":"1","publisher":"Association for Computing Machinery","oa":1,"acknowledgement":"This research was partially supported by the ERC CoG 863818 (ForM-SMArt), the National Natural Science Foundation of China (NSFC) Grant No. 61802254, the Huawei Innovation Research Program, the Facebook PhD Fellowship Program, and DOC Fellowship No. 24956 of the Austrian Academy of Sciences (ÖAW).","title":"Polynomial reachability witnesses via Stellensätze","author":[{"first_name":"Ali","full_name":"Asadi, Ali","last_name":"Asadi"},{"orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"last_name":"Fu","full_name":"Fu, Hongfei","first_name":"Hongfei","id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","first_name":"Amir Kafshdar","last_name":"Goharshady","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir Kafshdar"},{"first_name":"Mohammad","full_name":"Mahdavi, Mohammad","last_name":"Mahdavi"}],"external_id":{"isi":["000723661700050"]},"article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"chicago":"Asadi, Ali, Krishnendu Chatterjee, Hongfei Fu, Amir Kafshdar Goharshady, and Mohammad Mahdavi. “Polynomial Reachability Witnesses via Stellensätze.” In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, 772–87. Association for Computing Machinery, 2021. https://doi.org/10.1145/3453483.3454076.","ista":"Asadi A, Chatterjee K, Fu H, Goharshady AK, Mahdavi M. 2021. Polynomial reachability witnesses via Stellensätze. Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. PLDI: Programming Language Design and Implementation, 772–787.","mla":"Asadi, Ali, et al. “Polynomial Reachability Witnesses via Stellensätze.” Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2021, pp. 772–87, doi:10.1145/3453483.3454076.","apa":"Asadi, A., Chatterjee, K., Fu, H., Goharshady, A. K., & Mahdavi, M. (2021). Polynomial reachability witnesses via Stellensätze. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (pp. 772–787). Online: Association for Computing Machinery. https://doi.org/10.1145/3453483.3454076","ama":"Asadi A, Chatterjee K, Fu H, Goharshady AK, Mahdavi M. Polynomial reachability witnesses via Stellensätze. In: Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation. Association for Computing Machinery; 2021:772-787. doi:10.1145/3453483.3454076","short":"A. Asadi, K. Chatterjee, H. Fu, A.K. Goharshady, M. Mahdavi, in:, Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2021, pp. 772–787.","ieee":"A. Asadi, K. Chatterjee, H. Fu, A. K. Goharshady, and M. Mahdavi, “Polynomial reachability witnesses via Stellensätze,” in Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation, Online, 2021, pp. 772–787."},"project":[{"grant_number":"863818","name":"Formal Methods for Stochastic Models: Algorithms and Applications","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","call_identifier":"H2020"},{"_id":"267066CE-B435-11E9-9278-68D0E5697425","name":"Quantitative Analysis of Probablistic Systems with a focus on Crypto-currencies"}],"ec_funded":1,"language":[{"iso":"eng"}],"publication_identifier":{"isbn":["9781450383912"]},"publication_status":"published","month":"06","scopus_import":"1","main_file_link":[{"url":"https://hal.archives-ouvertes.fr/hal-03183862/","open_access":"1"}],"oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"We consider the fundamental problem of reachability analysis over imperative programs with real variables. Previous works that tackle reachability are either unable to handle programs consisting of general loops (e.g. symbolic execution), or lack completeness guarantees (e.g. abstract interpretation), or are not automated (e.g. incorrectness logic). In contrast, we propose a novel approach for reachability analysis that can handle general and complex loops, is complete, and can be entirely automated for a wide family of programs. Through the notion of Inductive Reachability Witnesses (IRWs), our approach extends ideas from both invariant generation and termination to reachability analysis.\r\n\r\nWe first show that our IRW-based approach is sound and complete for reachability analysis of imperative programs. Then, we focus on linear and polynomial programs and develop automated methods for synthesizing linear and polynomial IRWs. In the linear case, we follow the well-known approaches using Farkas' Lemma. Our main contribution is in the polynomial case, where we present a push-button semi-complete algorithm. We achieve this using a novel combination of classical theorems in real algebraic geometry, such as Putinar's Positivstellensatz and Hilbert's Strong Nullstellensatz. Finally, our experimental results show we can prove complex reachability objectives over various benchmarks that were beyond the reach of previous methods."}],"department":[{"_id":"KrCh"}],"date_updated":"2023-08-10T14:13:39Z","status":"public","type":"conference","conference":{"name":" PLDI: Programming Language Design and Implementation","end_date":"2021-06-26","location":"Online","start_date":"2021-06-20"},"_id":"9645"},{"department":[{"_id":"KrCh"}],"date_updated":"2024-03-27T23:30:33Z","type":"conference","conference":{"name":"PLDI: Programming Language Design and Implementation","start_date":"2020-06-15","end_date":"2020-06-20","location":"London, United Kingdom"},"status":"public","_id":"8089","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"8934"}]},"publication_identifier":{"isbn":["9781450376136"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1902.04373"}],"month":"06","abstract":[{"lang":"eng","text":"We consider the classical problem of invariant generation for programs with polynomial assignments and focus on synthesizing invariants that are a conjunction of strict polynomial inequalities. We present a sound and semi-complete method based on positivstellensaetze, i.e. theorems in semi-algebraic geometry that characterize positive polynomials over a semi-algebraic set.\r\n\r\nOn the theoretical side, the worst-case complexity of our approach is subexponential, whereas the worst-case complexity of the previous complete method (Kapur, ACA 2004) is doubly-exponential. Even when restricted to linear invariants, the best previous complexity for complete invariant generation is exponential (Colon et al, CAV 2003). On the practical side, we reduce the invariant generation problem to quadratic programming (QCLP), which is a classical optimization problem with many industrial solvers. We demonstrate the applicability of our approach by providing experimental results on several academic benchmarks. To the best of our knowledge, the only previous invariant generation method that provides completeness guarantees for invariants consisting of polynomial inequalities is (Kapur, ACA 2004), which relies on quantifier elimination and cannot even handle toy programs such as our running example."}],"oa_version":"Preprint","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee"},{"last_name":"Fu","full_name":"Fu, Hongfei","id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","first_name":"Hongfei"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","first_name":"Amir Kafshdar","last_name":"Goharshady","full_name":"Goharshady, Amir Kafshdar","orcid":"0000-0003-1702-6584"},{"last_name":"Goharshady","full_name":"Goharshady, Ehsan Kafshdar","first_name":"Ehsan Kafshdar"}],"external_id":{"arxiv":["1902.04373"],"isi":["000614622300045"]},"article_processing_charge":"No","title":"Polynomial invariant generation for non-deterministic recursive programs","citation":{"mla":"Chatterjee, Krishnendu, et al. “Polynomial Invariant Generation for Non-Deterministic Recursive Programs.” Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2020, pp. 672–87, doi:10.1145/3385412.3385969.","ama":"Chatterjee K, Fu H, Goharshady AK, Goharshady EK. Polynomial invariant generation for non-deterministic recursive programs. In: Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. Association for Computing Machinery; 2020:672-687. doi:10.1145/3385412.3385969","apa":"Chatterjee, K., Fu, H., Goharshady, A. K., & Goharshady, E. K. (2020). Polynomial invariant generation for non-deterministic recursive programs. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (pp. 672–687). London, United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3385412.3385969","short":"K. Chatterjee, H. Fu, A.K. Goharshady, E.K. Goharshady, in:, Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2020, pp. 672–687.","ieee":"K. Chatterjee, H. Fu, A. K. Goharshady, and E. K. Goharshady, “Polynomial invariant generation for non-deterministic recursive programs,” in Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, London, United Kingdom, 2020, pp. 672–687.","chicago":"Chatterjee, Krishnendu, Hongfei Fu, Amir Kafshdar Goharshady, and Ehsan Kafshdar Goharshady. “Polynomial Invariant Generation for Non-Deterministic Recursive Programs.” In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, 672–87. Association for Computing Machinery, 2020. https://doi.org/10.1145/3385412.3385969.","ista":"Chatterjee K, Fu H, Goharshady AK, Goharshady EK. 2020. Polynomial invariant generation for non-deterministic recursive programs. Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI: Programming Language Design and Implementation, 672–687."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","project":[{"grant_number":"S 11407_N23","name":"Rigorous Systems Engineering","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425"}],"page":"672-687","doi":"10.1145/3385412.3385969","date_published":"2020-06-11T00:00:00Z","date_created":"2020-07-05T22:00:45Z","isi":1,"year":"2020","day":"11","publication":"Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation","quality_controlled":"1","publisher":"Association for Computing Machinery","oa":1},{"ec_funded":1,"related_material":{"record":[{"status":"public","id":"5457","relation":"earlier_version"},{"id":"8934","status":"public","relation":"dissertation_contains"}]},"language":[{"iso":"eng"}],"file":[{"date_updated":"2020-07-14T12:47:20Z","file_size":4051066,"creator":"akafshda","date_created":"2019-03-25T10:11:22Z","file_name":"paper.pdf","content_type":"application/pdf","access_level":"open_access","relation":"main_file","checksum":"703a5e9b8c8587f2a44085ffd9a4db64","file_id":"6176"}],"publication_status":"published","month":"06","scopus_import":"1","oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"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."}],"department":[{"_id":"KrCh"}],"file_date_updated":"2020-07-14T12:47:20Z","ddc":["000"],"date_updated":"2024-03-27T23:30:33Z","keyword":["Program Cost Analysis","Program Termination","Probabilistic Programs","Martingales"],"status":"public","conference":{"start_date":"2019-06-22","end_date":"2019-06-26","location":"Phoenix, AZ, United States","name":"PLDI: Conference on Programming Language Design and Implementation"},"type":"conference","_id":"6175","date_created":"2019-03-25T10:13:25Z","doi":"10.1145/3314221.3314581","date_published":"2019-06-08T00:00:00Z","page":"204-220","publication":"PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation","day":"08","year":"2019","isi":1,"has_accepted_license":"1","oa":1,"publisher":"Association for Computing Machinery","quality_controlled":"1","title":"Cost analysis of nondeterministic probabilistic programs","external_id":{"arxiv":["1902.04659"],"isi":["000523190300014"]},"article_processing_charge":"No","author":[{"first_name":"Peixin","last_name":"Wang","full_name":"Wang, Peixin"},{"last_name":"Fu","full_name":"Fu, Hongfei","id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","first_name":"Hongfei"},{"first_name":"Amir Kafshdar","id":"391365CE-F248-11E8-B48F-1D18A9856A87","last_name":"Goharshady","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir Kafshdar"},{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Qin","full_name":"Qin, Xudong","first_name":"Xudong"},{"last_name":"Shi","full_name":"Shi, Wenjun","first_name":"Wenjun"}],"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","citation":{"mla":"Wang, Peixin, et al. “Cost Analysis of Nondeterministic Probabilistic Programs.” PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2019, pp. 204–20, doi:10.1145/3314221.3314581.","short":"P. Wang, H. Fu, A.K. Goharshady, K. Chatterjee, X. Qin, W. Shi, in:, PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, Association for Computing Machinery, 2019, pp. 204–220.","ieee":"P. Wang, H. Fu, A. K. Goharshady, K. Chatterjee, X. Qin, and W. Shi, “Cost analysis of nondeterministic probabilistic programs,” in PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, Phoenix, AZ, United States, 2019, pp. 204–220.","ama":"Wang P, Fu H, Goharshady AK, Chatterjee K, Qin X, Shi W. Cost analysis of nondeterministic probabilistic programs. In: PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. Association for Computing Machinery; 2019:204-220. doi:10.1145/3314221.3314581","apa":"Wang, P., Fu, H., Goharshady, A. K., Chatterjee, K., Qin, X., & Shi, W. (2019). Cost analysis of nondeterministic probabilistic programs. In PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (pp. 204–220). Phoenix, AZ, United States: Association for Computing Machinery. https://doi.org/10.1145/3314221.3314581","chicago":"Wang, Peixin, Hongfei Fu, Amir Kafshdar Goharshady, Krishnendu Chatterjee, Xudong Qin, and Wenjun Shi. “Cost Analysis of Nondeterministic Probabilistic Programs.” In PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation, 204–20. Association for Computing Machinery, 2019. https://doi.org/10.1145/3314221.3314581.","ista":"Wang P, Fu H, Goharshady AK, Chatterjee K, Qin X, Shi W. 2019. Cost analysis of nondeterministic probabilistic programs. PLDI 2019: Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI: Conference on Programming Language Design and Implementation, 204–220."},"project":[{"name":"Efficient Algorithms for Computer Aided Verification","grant_number":"ICT15-003","_id":"25892FC0-B435-11E9-9278-68D0E5697425"},{"grant_number":"S11407","name":"Game Theory","_id":"25863FF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"Quantitative Game-theoretic Analysis of Blockchain Applications and Smart Contracts","_id":"266EEEC0-B435-11E9-9278-68D0E5697425"}]},{"language":[{"iso":"eng"}],"publication_status":"published","publication_identifier":{"issn":["0164-0925"]},"ec_funded":1,"volume":40,"related_material":{"record":[{"status":"public","id":"1438","relation":"earlier_version"}]},"issue":"2","oa_version":"Submitted Version","abstract":[{"lang":"eng","text":"In this article, we consider the termination problem of probabilistic programs with real-valued variables. Thequestions concerned are: qualitative ones that ask (i) whether the program terminates with probability 1(almost-sure termination) and (ii) whether the expected termination time is finite (finite termination); andquantitative ones that ask (i) to approximate the expected termination time (expectation problem) and (ii) tocompute a boundBsuch that the probability not to terminate afterBsteps decreases exponentially (con-centration problem). To solve these questions, we utilize the notion of ranking supermartingales, which isa powerful approach for proving termination of probabilistic programs. In detail, we focus on algorithmicsynthesis of linear ranking-supermartingales over affine probabilistic programs (Apps) with both angelic anddemonic non-determinism. An important subclass of Apps is LRApp which is defined as the class of all Appsover which a linear ranking-supermartingale exists.Our main contributions are as follows. Firstly, we show that the membership problem of LRApp (i) canbe decided in polynomial time for Apps with at most demonic non-determinism, and (ii) isNP-hard and inPSPACEfor Apps with angelic non-determinism. Moreover, theNP-hardness result holds already for Appswithout probability and demonic non-determinism. Secondly, we show that the concentration problem overLRApp can be solved in the same complexity as for the membership problem of LRApp. Finally, we show thatthe expectation problem over LRApp can be solved in2EXPTIMEand isPSPACE-hard even for Apps withoutprobability and non-determinism (i.e., deterministic programs). Our experimental results demonstrate theeffectiveness of our approach to answer the qualitative and quantitative questions over Apps with at mostdemonic non-determinism."}],"intvolume":" 40","month":"06","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1510.08517"}],"scopus_import":"1","date_updated":"2023-09-19T14:38:42Z","department":[{"_id":"KrCh"}],"_id":"5993","status":"public","type":"journal_article","publication":"ACM Transactions on Programming Languages and Systems","day":"01","year":"2018","isi":1,"date_created":"2019-02-14T12:29:10Z","doi":"10.1145/3174800","date_published":"2018-06-01T00:00:00Z","oa":1,"publisher":"Association for Computing Machinery (ACM)","quality_controlled":"1","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","citation":{"ista":"Chatterjee K, Fu H, Novotný P, Hasheminezhad R. 2018. Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. ACM Transactions on Programming Languages and Systems. 40(2), 7.","chicago":"Chatterjee, Krishnendu, Hongfei Fu, Petr Novotný, and Rouzbeh Hasheminezhad. “Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Affine Probabilistic Programs.” ACM Transactions on Programming Languages and Systems. Association for Computing Machinery (ACM), 2018. https://doi.org/10.1145/3174800.","ieee":"K. Chatterjee, H. Fu, P. Novotný, and R. Hasheminezhad, “Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs,” ACM Transactions on Programming Languages and Systems, vol. 40, no. 2. Association for Computing Machinery (ACM), 2018.","short":"K. Chatterjee, H. Fu, P. Novotný, R. Hasheminezhad, ACM Transactions on Programming Languages and Systems 40 (2018).","ama":"Chatterjee K, Fu H, Novotný P, Hasheminezhad R. Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. ACM Transactions on Programming Languages and Systems. 2018;40(2). doi:10.1145/3174800","apa":"Chatterjee, K., Fu, H., Novotný, P., & Hasheminezhad, R. (2018). Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. ACM Transactions on Programming Languages and Systems. Association for Computing Machinery (ACM). https://doi.org/10.1145/3174800","mla":"Chatterjee, Krishnendu, et al. “Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Affine Probabilistic Programs.” ACM Transactions on Programming Languages and Systems, vol. 40, no. 2, 7, Association for Computing Machinery (ACM), 2018, doi:10.1145/3174800."},"title":"Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs","external_id":{"arxiv":["1510.08517"],"isi":["000434634500003"]},"article_processing_charge":"No","author":[{"first_name":"Krishnendu","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","first_name":"Hongfei","full_name":"Fu, Hongfei","last_name":"Fu"},{"full_name":"Novotný, Petr","last_name":"Novotný","first_name":"Petr","id":"3CC3B868-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Hasheminezhad","full_name":"Hasheminezhad, Rouzbeh","first_name":"Rouzbeh"}],"article_number":"7","project":[{"grant_number":"P 23499-N23","name":"Modern Graph Algorithmic Techniques in Formal Verification","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"_id":"2581B60A-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307"},{"_id":"25681D80-B435-11E9-9278-68D0E5697425","call_identifier":"FP7","grant_number":"291734","name":"International IST Postdoc Fellowship Programme"}]},{"citation":{"chicago":"Chatterjee, Krishnendu, Hongfei Fu, Amir Kafshdar Goharshady, and Nastaran Okati. “Computational Approaches for Stochastic Shortest Path on Succinct MDPs.” In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, 2018:4700–4707. IJCAI, 2018. https://doi.org/10.24963/ijcai.2018/653.","ista":"Chatterjee K, Fu H, Goharshady AK, Okati N. 2018. Computational approaches for stochastic shortest path on succinct MDPs. Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. IJCAI: International Joint Conference on Artificial Intelligence vol. 2018, 4700–4707.","mla":"Chatterjee, Krishnendu, et al. “Computational Approaches for Stochastic Shortest Path on Succinct MDPs.” Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, vol. 2018, IJCAI, 2018, pp. 4700–07, doi:10.24963/ijcai.2018/653.","ama":"Chatterjee K, Fu H, Goharshady AK, Okati N. Computational approaches for stochastic shortest path on succinct MDPs. In: Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence. Vol 2018. IJCAI; 2018:4700-4707. doi:10.24963/ijcai.2018/653","apa":"Chatterjee, K., Fu, H., Goharshady, A. K., & Okati, N. (2018). Computational approaches for stochastic shortest path on succinct MDPs. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (Vol. 2018, pp. 4700–4707). Stockholm, Sweden: IJCAI. https://doi.org/10.24963/ijcai.2018/653","ieee":"K. Chatterjee, H. Fu, A. K. Goharshady, and N. Okati, “Computational approaches for stochastic shortest path on succinct MDPs,” in Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, Stockholm, Sweden, 2018, vol. 2018, pp. 4700–4707.","short":"K. Chatterjee, H. Fu, A.K. Goharshady, N. Okati, in:, Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI, 2018, pp. 4700–4707."},"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","author":[{"last_name":"Chatterjee","full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","first_name":"Hongfei","last_name":"Fu","full_name":"Fu, Hongfei"},{"id":"391365CE-F248-11E8-B48F-1D18A9856A87","first_name":"Amir","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir","last_name":"Goharshady"},{"full_name":"Okati, Nastaran","last_name":"Okati","first_name":"Nastaran"}],"external_id":{"isi":["000764175404118"],"arxiv":["1804.08984"]},"article_processing_charge":"No","title":"Computational approaches for stochastic shortest path on succinct MDPs","project":[{"_id":"25892FC0-B435-11E9-9278-68D0E5697425","grant_number":"ICT15-003","name":"Efficient Algorithms for Computer Aided Verification"},{"name":"Rigorous Systems Engineering","grant_number":"S 11407_N23","_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"}],"isi":1,"year":"2018","day":"17","publication":"Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence","page":"4700-4707","date_published":"2018-07-17T00:00:00Z","doi":"10.24963/ijcai.2018/653","date_created":"2019-02-13T13:26:27Z","quality_controlled":"1","publisher":"IJCAI","oa":1,"date_updated":"2024-03-27T23:30:34Z","department":[{"_id":"KrCh"}],"_id":"5977","type":"conference","conference":{"name":"IJCAI: International Joint Conference on Artificial Intelligence","end_date":"2018-07-19","location":"Stockholm, Sweden","start_date":"2018-07-13"},"status":"public","publication_identifier":{"issn":["10450823"],"isbn":["978-099924112-7"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":2018,"related_material":{"record":[{"status":"public","id":"8934","relation":"dissertation_contains"}]},"ec_funded":1,"abstract":[{"lang":"eng","text":"We consider the stochastic shortest path (SSP)problem for succinct Markov decision processes(MDPs), where the MDP consists of a set of vari-ables, and a set of nondeterministic rules that up-date the variables. First, we show that several ex-amples from the AI literature can be modeled assuccinct MDPs. Then we present computationalapproaches for upper and lower bounds for theSSP problem: (a) for computing upper bounds, ourmethod is polynomial-time in the implicit descrip-tion of the MDP; (b) for lower bounds, we present apolynomial-time (in the size of the implicit descrip-tion) reduction to quadratic programming. Our ap-proach is applicable even to infinite-state MDPs.Finally, we present experimental results to demon-strate the effectiveness of our approach on severalclassical examples from the AI literature."}],"oa_version":"Preprint","scopus_import":"1","main_file_link":[{"url":"https://arxiv.org/abs/1804.08984","open_access":"1"}],"month":"07","intvolume":" 2018"},{"acknowledgement":"Supported by the Natural Science Foundation of China (NSFC) under Grant No. 61532019 ","publisher":"ACM","quality_controlled":"1","oa":1,"year":"2016","day":"11","page":"327 - 342","date_published":"2016-01-11T00:00:00Z","doi":"10.1145/2837614.2837639","date_created":"2018-12-11T11:52:01Z","project":[{"name":"Modern Graph Algorithmic Techniques in Formal Verification","grant_number":"P 23499-N23","_id":"2584A770-B435-11E9-9278-68D0E5697425","call_identifier":"FWF"},{"_id":"25832EC2-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425","grant_number":"279307","name":"Quantitative Graph Games: Theory and Applications"},{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"citation":{"mla":"Chatterjee, Krishnendu, et al. Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Affine Probabilistic Programs. Vol. 20–22, ACM, 2016, pp. 327–42, doi:10.1145/2837614.2837639.","apa":"Chatterjee, K., Fu, H., Novotný, P., & Hasheminezhad, R. (2016). Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs (Vol. 20–22, pp. 327–342). Presented at the POPL: Principles of Programming Languages, St. Petersburg, FL, USA: ACM. https://doi.org/10.1145/2837614.2837639","ama":"Chatterjee K, Fu H, Novotný P, Hasheminezhad R. Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. In: Vol 20-22. ACM; 2016:327-342. doi:10.1145/2837614.2837639","short":"K. Chatterjee, H. Fu, P. Novotný, R. Hasheminezhad, in:, ACM, 2016, pp. 327–342.","ieee":"K. Chatterjee, H. Fu, P. Novotný, and R. Hasheminezhad, “Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs,” presented at the POPL: Principles of Programming Languages, St. Petersburg, FL, USA, 2016, vol. 20–22, pp. 327–342.","chicago":"Chatterjee, Krishnendu, Hongfei Fu, Petr Novotný, and Rouzbeh Hasheminezhad. “Algorithmic Analysis of Qualitative and Quantitative Termination Problems for Affine Probabilistic Programs,” 20–22:327–42. ACM, 2016. https://doi.org/10.1145/2837614.2837639.","ista":"Chatterjee K, Fu H, Novotný P, Hasheminezhad R. 2016. Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. POPL: Principles of Programming Languages, POPL, vol. 20–22, 327–342."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publist_id":"5760","author":[{"id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu","last_name":"Chatterjee","orcid":"0000-0002-4561-241X","full_name":"Chatterjee, Krishnendu"},{"last_name":"Fu","full_name":"Fu, Hongfei","id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","first_name":"Hongfei"},{"id":"3CC3B868-F248-11E8-B48F-1D18A9856A87","first_name":"Petr","full_name":"Novotny, Petr","last_name":"Novotny"},{"full_name":"Hasheminezhad, Rouzbeh","last_name":"Hasheminezhad","first_name":"Rouzbeh"}],"external_id":{"arxiv":["1510.08517"]},"title":"Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs","abstract":[{"text":"In this paper, we consider termination of probabilistic programs with real-valued variables. The questions concerned are: (a) qualitative ones that ask (i) whether the program terminates with probability 1 (almost-sure termination) and (ii) whether the expected termination time is finite (finite termination); (b) quantitative ones that ask (i) to approximate the expected termination time (expectation problem) and (ii) to compute a bound B such that the probability to terminate after B steps decreases exponentially (concentration problem). To solve these questions, we utilize the notion of ranking supermartingales which is a powerful approach for proving termination of probabilistic programs. In detail, we focus on algorithmic synthesis of linear ranking-supermartingales over affine probabilistic programs (APP's) with both angelic and demonic non-determinism. An important subclass of APP's is LRAPP which is defined as the class of all APP's over which a linear ranking-supermartingale exists. Our main contributions are as follows. Firstly, we show that the membership problem of LRAPP (i) can be decided in polynomial time for APP's with at most demonic non-determinism, and (ii) is NP-hard and in PSPACE for APP's with angelic non-determinism; moreover, the NP-hardness result holds already for APP's without probability and demonic non-determinism. Secondly, we show that the concentration problem over LRAPP can be solved in the same complexity as for the membership problem of LRAPP. Finally, we show that the expectation problem over LRAPP can be solved in 2EXPTIME and is PSPACE-hard even for APP's without probability and non-determinism (i.e., deterministic programs). Our experimental results demonstrate the effectiveness of our approach to answer the qualitative and quantitative questions over APP's with at most demonic non-determinism.","lang":"eng"}],"oa_version":"Preprint","alternative_title":["POPL"],"scopus_import":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1510.08517"}],"month":"01","publication_status":"published","language":[{"iso":"eng"}],"volume":"20-22","related_material":{"record":[{"relation":"later_version","id":"5993","status":"public"}]},"ec_funded":1,"_id":"1438","type":"conference","conference":{"name":"POPL: Principles of Programming Languages","start_date":"2016-01-20","end_date":"2016-01-22","location":"St. Petersburg, FL, USA"},"status":"public","date_updated":"2023-09-19T14:38:41Z","department":[{"_id":"KrCh"}]},{"year":"2016","day":"01","page":"3 - 22","doi":"10.1007/978-3-319-41528-4_1","date_published":"2016-07-01T00:00:00Z","date_created":"2018-12-11T11:51:43Z","quality_controlled":"1","publisher":"Springer","oa":1,"citation":{"chicago":"Chatterjee, Krishnendu, Hongfei Fu, and Amir Kafshdar Goharshady. “Termination Analysis of Probabilistic Programs through Positivstellensatz’s,” 9779:3–22. Springer, 2016. https://doi.org/10.1007/978-3-319-41528-4_1.","ista":"Chatterjee K, Fu H, Goharshady AK. 2016. Termination analysis of probabilistic programs through Positivstellensatz’s. CAV: Computer Aided Verification, LNCS, vol. 9779, 3–22.","mla":"Chatterjee, Krishnendu, et al. Termination Analysis of Probabilistic Programs through Positivstellensatz’s. Vol. 9779, Springer, 2016, pp. 3–22, doi:10.1007/978-3-319-41528-4_1.","apa":"Chatterjee, K., Fu, H., & Goharshady, A. K. (2016). Termination analysis of probabilistic programs through Positivstellensatz’s (Vol. 9779, pp. 3–22). Presented at the CAV: Computer Aided Verification, Toronto, Canada: Springer. https://doi.org/10.1007/978-3-319-41528-4_1","ama":"Chatterjee K, Fu H, Goharshady AK. Termination analysis of probabilistic programs through Positivstellensatz’s. In: Vol 9779. Springer; 2016:3-22. doi:10.1007/978-3-319-41528-4_1","ieee":"K. Chatterjee, H. Fu, and A. K. Goharshady, “Termination analysis of probabilistic programs through Positivstellensatz’s,” presented at the CAV: Computer Aided Verification, Toronto, Canada, 2016, vol. 9779, pp. 3–22.","short":"K. Chatterjee, H. Fu, A.K. Goharshady, in:, Springer, 2016, pp. 3–22."},"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87","first_name":"Krishnendu"},{"id":"3AAD03D6-F248-11E8-B48F-1D18A9856A87","first_name":"Hongfei","last_name":"Fu","full_name":"Fu, Hongfei"},{"first_name":"Amir","id":"391365CE-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-1702-6584","full_name":"Goharshady, Amir","last_name":"Goharshady"}],"publist_id":"5824","title":"Termination analysis of probabilistic programs through Positivstellensatz's","project":[{"call_identifier":"FWF","_id":"25832EC2-B435-11E9-9278-68D0E5697425","grant_number":"S 11407_N23","name":"Rigorous Systems Engineering"},{"name":"Quantitative Graph Games: Theory and Applications","grant_number":"279307","call_identifier":"FP7","_id":"2581B60A-B435-11E9-9278-68D0E5697425"},{"grant_number":"267989","name":"Quantitative Reactive Modeling","_id":"25EE3708-B435-11E9-9278-68D0E5697425","call_identifier":"FP7"}],"publication_status":"published","language":[{"iso":"eng"}],"volume":9779,"related_material":{"record":[{"status":"public","id":"8934","relation":"dissertation_contains"}]},"ec_funded":1,"abstract":[{"text":"We consider nondeterministic probabilistic programs with the most basic liveness property of termination. We present efficient methods for termination analysis of nondeterministic probabilistic programs with polynomial guards and assignments. Our approach is through synthesis of polynomial ranking supermartingales, that on one hand significantly generalizes linear ranking supermartingales and on the other hand is a counterpart of polynomial ranking-functions for proving termination of nonprobabilistic programs. The approach synthesizes polynomial ranking-supermartingales through Positivstellensatz's, yielding an efficient method which is not only sound, but also semi-complete over a large subclass of programs. We show experimental results to demonstrate that our approach can handle several classical programs with complex polynomial guards and assignments, and can synthesize efficient quadratic ranking-supermartingales when a linear one does not exist even for simple affine programs.","lang":"eng"}],"oa_version":"Preprint","alternative_title":["LNCS"],"scopus_import":1,"main_file_link":[{"url":"http://arxiv.org/abs/1604.07169","open_access":"1"}],"month":"07","intvolume":" 9779","date_updated":"2024-03-27T23:30:32Z","department":[{"_id":"KrCh"}],"_id":"1386","type":"conference","conference":{"start_date":"2016-07-17","end_date":"2016-07-23","location":"Toronto, Canada","name":"CAV: Computer Aided Verification"},"status":"public"}]