{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T23:04:03Z","timestamp":1784675043522,"version":"3.55.0"},"publisher-location":"Cham","reference-count":50,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319415277","type":"print"},{"value":"9783319415284","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-41528-4_1","type":"book-chapter","created":{"date-parts":[[2016,7,12]],"date-time":"2016-07-12T09:34:06Z","timestamp":1468316046000},"page":"3-22","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":81,"title":["Termination Analysis of Probabilistic Programs Through Positivstellensatz\u2019s"],"prefix":"10.1007","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hongfei","family":"Fu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amir Kafshdar","family":"Goharshady","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,7,13]]},"reference":[{"key":"1_CR1","unstructured":"SeDuMi 1.3 (2008). http:\/\/sedumi.ie.lehigh.edu\/"},{"key":"1_CR2","unstructured":"IBM ILOG CPLEX Optimizer Interactive Optimizer Community Edition 12.6.3.0 (2010). http:\/\/www-01.ibm.com\/software\/integration\/optimization\/cplex-optimizer\/"},{"key":"1_CR3","unstructured":"SOSTOOLS v3.00 (2013). http:\/\/www.cds.caltech.edu\/sostools\/"},{"issue":"3","key":"1_CR4","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s00165-012-0252-5","volume":"25","author":"D Babic","year":"2013","unstructured":"Babic, D., Cook, B., Hu, A.J., Rakamaric, Z.: Proving termination of nonlinear command sequences. Form. Asp. Comput. 25(3), 389\u2013403 (2013)","journal-title":"Form. Asp. Comput."},{"key":"1_CR5","volume-title":"Principles of Model Checking","author":"C Baier","year":"2008","unstructured":"Baier, C., Katoen, J.P.: Principles of Model Checking. MIT Press, Cambridge (2008)"},{"key":"1_CR6","volume-title":"Probability and Measure","author":"P Billingsley","year":"1995","unstructured":"Billingsley, P.: Probability and Measure, 3rd edn. Wiley, New York (1995)","edition":"3"},{"key":"1_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-540-32033-3_24","volume-title":"Term Rewriting and Applications","author":"O Bournez","year":"2005","unstructured":"Bournez, O., Garnier, F.: Proving positive almost-sure termination. In: Giesl, J. (ed.) RTA 2005. LNCS, vol. 3467, pp. 323\u2013337. Springer, Heidelberg (2005)"},{"key":"1_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1007\/11513988_48","volume-title":"Computer Aided Verification","author":"AR Bradley","year":"2005","unstructured":"Bradley, A.R., Manna, Z., Sipma, H.B.: Linear ranking with reachability. In: Etessami, K., Rajamani, S.K. (eds.) CAV 2005. LNCS, vol. 3576, pp. 491\u2013504. Springer, Heidelberg (2005)"},{"key":"1_CR9","first-page":"113","volume-title":"Lecture Notes in Computer Science","author":"Aaron R. Bradley","year":"2005","unstructured":"Bradley, A.R., Manna, Z., Sipma, H.B.: Termination of polynomial programs. In: Cousot [16], pp. 113\u2013129"},{"key":"1_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/978-3-642-39799-8_34","volume-title":"Computer Aided Verification","author":"A Chakarov","year":"2013","unstructured":"Chakarov, A., Sankaranarayanan, S.: Probabilistic program analysis with Martingales. In: Sharygina, N., Veith, H. (eds.) CAV 2013. LNCS, vol. 8044, pp. 511\u2013526. Springer, Heidelberg (2013)"},{"key":"1_CR11","unstructured":"Chatterjee, K., Fu, H., Goharshady, A.K.: Termination analysis of probabilistic programs through positivstellensatz\u2019s (2016). arXiv CoRR: http:\/\/arxiv.org\/abs\/1604.07169"},{"issue":"1","key":"1_CR12","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1145\/2914770.2837639","volume":"51","author":"Krishnendu Chatterjee","year":"2016","unstructured":"Chatterjee, K., Fu, H., Novotn\u00fd, P., Hasheminezhad, R.: Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. In: POPL, pp. 327\u2013342. ACM (2016)","journal-title":"ACM SIGPLAN Notices"},{"key":"1_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-45319-9_6","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"MA Col\u00f3n","year":"2001","unstructured":"Col\u00f3n, M.A., Sipma, H.B.: Synthesis of linear ranking functions. In: Margaria, T., Yi, W. (eds.) TACAS 2001. LNCS, vol. 2031, pp. 67\u201381. Springer, Heidelberg (2001)"},{"key":"1_CR14","first-page":"1","volume-title":"Lecture Notes in Computer Science","author":"Patrick Cousot","year":"2005","unstructured":"Cousot, P.: Proving program invariance and termination by parametric abstraction, Lagrangian relaxation and semidefinite programming. In: Cousot [16], pp. 1\u201324"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Cousot, P., Cousot, R.: Abstract interpretation: a unified Lattice model for static analysis of programs by construction or approximation of fixpoints. In: POPL, pp. 238\u2013252. ACM (1977)","DOI":"10.1145\/512950.512973"},{"key":"1_CR16","series-title":"Lecture Notes in Computer Science","volume-title":"VMCAI 2005","year":"2005","unstructured":"Cousot, R. (ed.): VMCAI 2005. LNCS, vol. 3385. Springer, Heidelberg (2005)"},{"key":"1_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of Measure for the Analysis of Randomized Algorithms","author":"D Dubhashi","year":"2009","unstructured":"Dubhashi, D., Panconesi, A.: Concentration of Measure for the Analysis of Randomized Algorithms, 1st edn. Cambridge University Press, New York (2009)","edition":"1"},{"key":"1_CR18","volume-title":"Probability: Theory and Examples","author":"R Durrett","year":"1996","unstructured":"Durrett, R.: Probability: Theory and Examples, 2nd edn. Duxbury Press, Belmont (1996)","edition":"2"},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/978-3-642-31424-7_14","volume-title":"Computer Aided Verification","author":"J Esparza","year":"2012","unstructured":"Esparza, J., Gaiser, A., Kiefer, S.: Proving termination of probabilistic programs using patterns. In: Madhusudan, P., Seshia, S.A. (eds.) CAV 2012. LNCS, vol. 7358, pp. 123\u2013138. Springer, Heidelberg (2012)"},{"key":"1_CR20","first-page":"457","volume":"12","author":"J Farkas","year":"1894","unstructured":"Farkas, J.: A fourier-f\u00e9le mechanikai elv alkalmaz\u00e1sai (Hungarian). Mathematikai\u00e9s Term\u00e9szettudom\u00e1nyi \u00c9rtesit\u00f6 12, 457\u2013472 (1894)","journal-title":"Mathematikai\u00e9s Term\u00e9szettudom\u00e1nyi \u00c9rtesit\u00f6"},{"key":"1_CR21","doi-asserted-by":"crossref","unstructured":"Fioriti, L.M.F., Hermanns, H.: Probabilistic termination: soundness, completeness, and compositionality. In: POPL, pp. 489\u2013501. ACM (2015)","DOI":"10.1145\/2775051.2677001"},{"key":"1_CR22","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1090\/psapm\/019\/0235771","volume":"19","author":"RW Floyd","year":"1967","unstructured":"Floyd, R.W.: Assigning meanings to programs. Math. Asp. Comput. Sci. 19, 19\u201333 (1967)","journal-title":"Math. Asp. Comput. Sci."},{"issue":"3","key":"1_CR23","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1214\/aoms\/1177728976","volume":"24","author":"FG Foster","year":"1953","unstructured":"Foster, F.G.: On the stochastic matrices associated with certain queuing processes. Ann. Math. Stat. 24(3), 355\u2013360 (1953)","journal-title":"Ann. Math. Stat."},{"key":"1_CR24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-78240-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1993","unstructured":"Gr\u00f6tschel, M., Lovasz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Heidelberg (1993)"},{"key":"1_CR25","doi-asserted-by":"publisher","first-page":"35","DOI":"10.2140\/pjm.1988.132.35","volume":"132","author":"D Handelman","year":"1988","unstructured":"Handelman, D.: Representing polynomials by positive linear functions on compact convex polyhedra. Pacific J. Math. 132, 35\u201362 (1988)","journal-title":"Pacific J. Math."},{"issue":"301","key":"1_CR26","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W Hoeffding","year":"1963","unstructured":"Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13\u201330 (1963)","journal-title":"J. Am. Stat. Assoc."},{"key":"1_CR27","volume-title":"Matrix Analysis","author":"RA Horn","year":"2013","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013)","edition":"2"},{"key":"1_CR28","volume-title":"Dynamic Programming and Markov Processes","author":"H Howard","year":"1960","unstructured":"Howard, H.: Dynamic Programming and Markov Processes. MIT Press, Cambridge (1960)"},{"key":"1_CR29","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-6101-8","volume-title":"Algebra","author":"TW Hungerford","year":"1974","unstructured":"Hungerford, T.W.: Algebra. Springer, Heidelberg (1974)"},{"issue":"1","key":"1_CR30","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0004-3702(98)00023-X","volume":"101","author":"LP Kaelbling","year":"1998","unstructured":"Kaelbling, L.P., Littman, M.L., Cassandra, A.R.: Planning and acting in partially observable stochastic domains. Artif. intell. 101(1), 99\u2013134 (1998)","journal-title":"Artif. intell."},{"key":"1_CR31","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1613\/jair.301","volume":"4","author":"LP Kaelbling","year":"1996","unstructured":"Kaelbling, L.P., Littman, M.L., Moore, A.W.: Reinforcement learning: a survey. J. Artif. Intell. Res. 4, 237\u2013285 (1996)","journal-title":"J. Artif. Intell. Res."},{"key":"1_CR32","volume-title":"Denumerable Markov Chains","author":"J Kemeny","year":"1966","unstructured":"Kemeny, J., Snell, J., Knapp, A.: Denumerable Markov Chains. D. Van Nostrand Company, Princeton (1966)"},{"issue":"6","key":"1_CR33","doi-asserted-by":"publisher","first-page":"1370","DOI":"10.1109\/TRO.2009.2030225","volume":"25","author":"H Kress-Gazit","year":"2009","unstructured":"Kress-Gazit, H., Fainekos, G.E., Pappas, G.J.: Temporal-logic-based reactive mission and motion planning. IEEE Trans. Robot. 25(6), 1370\u20131381 (2009)","journal-title":"IEEE Trans. Robot."},{"key":"1_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/978-3-642-22110-1_47","volume-title":"Computer Aided Verification","author":"M Kwiatkowska","year":"2011","unstructured":"Kwiatkowska, M., Norman, G., Parker, D.: PRISM 4.0: verification of probabilistic real-time systems. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 585\u2013591. Springer, Heidelberg (2011)"},{"key":"1_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/11889229_4","volume-title":"Refinement Techniques in Software Engineering","author":"AK McIver","year":"2006","unstructured":"McIver, A.K., Morgan, C.: Developing and reasoning about probabilistic programs in pGCL. In: Cavalcanti, A., Sampaio, A., Woodcock, J. (eds.) PSSE 2004. LNCS, vol. 3167, pp. 123\u2013155. Springer, Heidelberg (2006)"},{"key":"1_CR36","series-title":"Monographs in Computer Science","volume-title":"Abstraction, Refinement and Proof for Probabilistic Systems","author":"A McIver","year":"2005","unstructured":"McIver, A., Morgan, C.: Abstraction, Refinement and Proof for Probabilistic Systems. Monographs in Computer Science. Springer, New York (2005)"},{"key":"1_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/3-540-47764-0_7","volume-title":"Static Analysis","author":"D Monniaux","year":"2001","unstructured":"Monniaux, D.: An abstract analysis of the probabilistic termination of programs. In: Cousot, P. (ed.) SAS 2001. LNCS, vol. 2126, pp. 111\u2013126. Springer, Heidelberg (2001)"},{"key":"1_CR38","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, New York (1995)"},{"key":"1_CR39","series-title":"Computer Science and Applied Mathematics","volume-title":"Introduction to Probabilistic Automata","author":"A Paz","year":"1971","unstructured":"Paz, A.: Introduction to Probabilistic Automata. Computer Science and Applied Mathematics. Academic Press, New York (1971)"},{"key":"1_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-540-24622-0_20","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"A Podelski","year":"2004","unstructured":"Podelski, A., Rybalchenko, A.: A complete method for the synthesis of linear ranking functions. In: Steffen, B., Levi, G. (eds.) VMCAI 2004. LNCS, vol. 2937, pp. 239\u2013251. Springer, Heidelberg (2004)"},{"key":"1_CR41","doi-asserted-by":"publisher","first-page":"969","DOI":"10.1512\/iumj.1993.42.42045","volume":"42","author":"M Putinar","year":"1993","unstructured":"Putinar, M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 969\u2013984 (1993)","journal-title":"Indiana Univ. Math. J."},{"key":"1_CR42","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M Rabin","year":"1963","unstructured":"Rabin, M.: Probabilistic automata. Inf. Control 6, 230\u2013245 (1963)","journal-title":"Inf. Control"},{"key":"1_CR43","doi-asserted-by":"crossref","unstructured":"Sankaranarayanan, S., Chakarov, A., Gulwani, S.: Static analysis for probabilistic programs: inferring whole program properties from finitely many paths. In: PLDI, pp. 447\u2013458 (2013)","DOI":"10.1145\/2499370.2462179"},{"key":"1_CR44","series-title":"The IMA Volumes in Mathematics and its Applications","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-0-387-09686-5_8","volume-title":"Emerging Applications of Algebraic Geometry","author":"C Scheiderer","year":"1996","unstructured":"Scheiderer, C.: Positivity and sums of squares: a guide to recent results. In: Putinar, M., Sullivant, S. (eds.) Emerging Applications of Algebraic Geometry. IMAVMA, vol. 149, pp. 271\u2013324. Springer, New York (1996)"},{"key":"1_CR45","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BF01446568","volume":"289","author":"K Schm\u00fcdgen","year":"1991","unstructured":"Schm\u00fcdgen, K.: The $${K}$$-moment problem for compact semi-algebraic sets. Math. Ann. 289, 203\u2013206 (1991)","journal-title":"Math. Ann."},{"key":"1_CR46","series-title":"Wiley-Interscience Series in Discrete Mathematics and Optimization","volume-title":"Theory of Linear and Integer Programming","author":"A Schrijver","year":"1999","unstructured":"Schrijver, A.: Theory of Linear and Integer Programming. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1999)"},{"issue":"2","key":"1_CR47","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/s11424-013-1004-1","volume":"26","author":"L Shen","year":"2013","unstructured":"Shen, L., Wu, M., Yang, Z., Zeng, Z.: Generating exact nonlinear ranking functions by symbolic-numeric hybrid method. J. Syst. Sci. Comput. 26(2), 291\u2013301 (2013)","journal-title":"J. Syst. Sci. Comput."},{"key":"1_CR48","doi-asserted-by":"crossref","unstructured":"Sohn, K., Gelder, A.V.: Termination detection in logic programs using argument sizes. In: PODS, pp. 216\u2013226. ACM Press (1991)","DOI":"10.1145\/113413.113433"},{"key":"1_CR49","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813658","volume-title":"Probability with Martingales","author":"D Williams","year":"1991","unstructured":"Williams, D.: Probability with Martingales. Cambridge University Press, Cambridge (1991)"},{"issue":"1","key":"1_CR50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11704-009-0074-7","volume":"4","author":"L Yang","year":"2010","unstructured":"Yang, L., Zhou, C., Zhan, N., Xia, B.: Recent advances in program verification through computer algebra. Front. Comput. Sci. China 4(1), 1\u201316 (2010)","journal-title":"Front. Comput. Sci. China"}],"container-title":["Lecture Notes in Computer Science","Computer Aided Verification"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-41528-4_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T00:41:24Z","timestamp":1748997684000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-41528-4_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319415277","9783319415284"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-41528-4_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"13 July 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CAV","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Computer Aided Verification","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Toronto","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Canada","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 July 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 July 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cav2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}