{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T01:31:25Z","timestamp":1743039085159,"version":"3.40.3"},"publisher-location":"Cham","reference-count":68,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319633893"},{"type":"electronic","value":"9783319633909"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-63390-9_3","type":"book-chapter","created":{"date-parts":[[2017,7,12]],"date-time":"2017-07-12T08:53:50Z","timestamp":1499849630000},"page":"41-63","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Non-polynomial Worst-Case Analysis of Recursive Programs"],"prefix":"10.1007","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[]},{"given":"Hongfei","family":"Fu","sequence":"additional","affiliation":[]},{"given":"Amir Kafshdar","family":"Goharshady","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,7,13]]},"reference":[{"issue":"1","key":"3_CR1","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.entcs.2009.12.008","volume":"258","author":"E Albert","year":"2009","unstructured":"Albert, E., Arenas, P., Genaim, S., G\u00f3mez-Zamalloa, M., Puebla, G., Ram\u00edrez-Deantes, D.V., Rom\u00e1n-D\u00edez, G., Zanardini, D.: Termination and cost analysis with COSTA and its user interfaces. Electr. Notes Theor. Comput. Sci. 258(1), 109\u2013121 (2009)","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/978-3-540-69166-2_15","volume-title":"Static Analysis","author":"E Albert","year":"2008","unstructured":"Albert, E., Arenas, P., Genaim, S., Puebla, G.: Automatic inference of upper bounds for recurrence relations in cost analysis. In: Alpuente, M., Vidal, G. (eds.) SAS 2008. LNCS, vol. 5079, pp. 221\u2013237. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-69166-2_15"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/978-3-540-71316-6_12","volume-title":"Programming Languages and Systems","author":"E Albert","year":"2007","unstructured":"Albert, E., Arenas, P., Genaim, S., Puebla, G., Zanardini, D.: Cost analysis of Java bytecode. In: Nicola, R. (ed.) ESOP 2007. LNCS, vol. 4421, pp. 157\u2013172. Springer, Heidelberg (2007). doi:10.1007\/978-3-540-71316-6_12"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/978-3-642-15769-1_8","volume-title":"Static Analysis","author":"C Alias","year":"2010","unstructured":"Alias, C., Darte, A., Feautrier, P., Gonnord, L.: Multi-dimensional rankings, program termination, and complexity bounds of flowchart programs. In: Cousot, R., Martel, M. (eds.) SAS 2010. LNCS, vol. 6337, pp. 117\u2013133. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-15769-1_8"},{"key":"3_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/978-3-642-11319-2_7","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"R Alur","year":"2010","unstructured":"Alur, R., Chaudhuri, S.: Temporal reasoning for procedural programs. In: Barthe, G., Hermenegildo, M. (eds.) VMCAI 2010. LNCS, vol. 5944, pp. 45\u201360. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-11319-2_7"},{"key":"3_CR6","volume-title":"Introduction to Real Analysis","author":"RG Bartle","year":"2011","unstructured":"Bartle, R.G., Sherbert, D.R.: Introduction to Real Analysis, 4th edn. Wiley, Hoboken (2011)","edition":"4"},{"volume-title":"POPL","year":"2016","key":"3_CR7","unstructured":"Bod\u00edk, R., Majumdar, R. (eds.): POPL. ACM, New York (2016)"},{"key":"3_CR8","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). doi:10.1007\/978-3-540-32033-3_24"},{"key":"3_CR9","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). doi:10.1007\/11513988_48"},{"issue":"4","key":"3_CR10","doi-asserted-by":"publisher","first-page":"13:1","DOI":"10.1145\/2866575","volume":"38","author":"M Brockschmidt","year":"2016","unstructured":"Brockschmidt, M., Emmes, F., Falke, S., Fuhs, C., Giesl, J.: Analyzing runtime and size complexity of integer programs. ACM Trans. Program. Lang. Syst. 38(4), 13:1\u201313:50 (2016)","journal-title":"ACM Trans. Program. Lang. Syst."},{"volume-title":"POPL","year":"2017","key":"3_CR11","unstructured":"Castagna, G., Gordon, A.D. (eds.): POPL. ACM, New York (2017)"},{"key":"3_CR12","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). doi:10.1007\/978-3-642-39799-8_34"},{"key":"3_CR13","unstructured":"Chatterjee, K., Fu, H.: Termination of nondeterministic recursive probabilistic programs. CoRR abs\/1701.02944 (2017). http:\/\/arxiv.org\/abs\/1701.02944"},{"key":"3_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-41528-4_1","volume-title":"Computer Aided Verification","author":"K Chatterjee","year":"2016","unstructured":"Chatterjee, K., Fu, H., Goharshady, A.K.: Termination analysis of probabilistic programs through Positivstellensatzs. In: Chaudhuri, S., Farzan, A. (eds.) CAV 2016. LNCS, vol. 9779, pp. 3\u201322. Springer, Cham (2016). doi:10.1007\/978-3-319-41528-4_1"},{"key":"3_CR15","unstructured":"Chatterjee, K., Fu, H., Goharshady, A.K.: Non-polynomial worst-case analysis of recursive programs. CoRR abs\/1705.00317 (2017). https:\/\/arxiv.org\/abs\/1705.00317"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Fu, H., Novotn\u00fd, P., Hasheminezhad, R.: Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs. In: Bod\u00edk and Majumdar [7], pp. 327\u2013342","DOI":"10.1145\/2914770.2837639"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Novotn\u00fd, P., \u017dikeli\u0107, \u0110.: Stochastic invariants for probabilistic termination. In: Castagna and Gordon [11], pp. 145\u2013160","DOI":"10.1145\/3093333.3009873"},{"issue":"2\u20133","key":"3_CR18","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1023\/A:1012996816178","volume":"14","author":"W Chin","year":"2001","unstructured":"Chin, W., Khoo, S.: Calculating sized types. Higher-Order Symbolic Comput. 14(2\u20133), 261\u2013300 (2001)","journal-title":"Higher-Order Symbolic Comput."},{"key":"3_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/978-3-540-45069-6_39","volume-title":"Computer Aided Verification","author":"MA Col\u00f3n","year":"2003","unstructured":"Col\u00f3n, M.A., Sankaranarayanan, S., Sipma, H.B.: Linear invariant generation using non-linear constraint solving. In: Hunt, W.A., Somenzi, F. (eds.) CAV 2003. LNCS, vol. 2725, pp. 420\u2013432. Springer, Heidelberg (2003). doi:10.1007\/978-3-540-45069-6_39"},{"key":"3_CR20","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). doi:10.1007\/3-540-45319-9_6"},{"key":"3_CR21","doi-asserted-by":"crossref","unstructured":"Cook, B., Podelski, A., Rybalchenko, A.: Termination proofs for systems code. In: Schwartzbach, M.I., Ball, T. (eds.) PLDI, pp. 415\u2013426. ACM (2006)","DOI":"10.1145\/1133255.1134029"},{"issue":"3","key":"3_CR22","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/s10703-009-0087-8","volume":"35","author":"B Cook","year":"2009","unstructured":"Cook, B., Podelski, A., Rybalchenko, A.: Summarization for termination: no return!. Form. Methods Syst. Des. 35(3), 369\u2013387 (2009)","journal-title":"Form. Methods Syst. Des."},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-642-36742-7_4","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"B Cook","year":"2013","unstructured":"Cook, B., See, A., Zuleger, F.: Ramsey vs. lexicographic termination proving. In: Piterman, N., Smolka, S.A. (eds.) TACAS 2013. LNCS, vol. 7795, pp. 47\u201361. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-36742-7_4"},{"key":"3_CR24","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"3_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-30579-8_1","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"P Cousot","year":"2005","unstructured":"Cousot, P.: Proving program invariance and termination by parametric abstraction, lagrangian relaxation and semidefinite programming. In: Cousot, R. (ed.) VMCAI 2005. LNCS, vol. 3385, pp. 1\u201324. Springer, Heidelberg (2005). doi:10.1007\/978-3-540-30579-8_1"},{"key":"3_CR26","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: Graham, R.M., Harrison, M.A., Sethi, R. (eds.) POPL, pp. 238\u2013252. ACM (1977)","DOI":"10.1145\/512950.512973"},{"key":"3_CR27","doi-asserted-by":"crossref","unstructured":"Cousot, P., Cousot, R.: An abstract interpretation framework for termination. In: Field, J., Hicks, M. (eds.) POPL, pp. 245\u2013258. ACM (2012)","DOI":"10.1145\/2103621.2103687"},{"key":"3_CR28","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":"3_CR29","doi-asserted-by":"crossref","unstructured":"Fioriti, L.M.F., Hermanns, H.: Probabilistic termination: soundness, completeness, and compositionality. In: Rajamani, S.K., Walker, D. (eds.) POPL, pp. 489\u2013501. ACM (2015)","DOI":"10.1145\/2775051.2677001"},{"issue":"1","key":"3_CR30","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0304-3975(91)90145-R","volume":"79","author":"P Flajolet","year":"1991","unstructured":"Flajolet, P., Salvy, B., Zimmermann, P.: Automatic average-case analysis of algorithm. Theor. Comput. Sci. 79(1), 37\u2013109 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR31","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. Aspects Comput. Sci. 19, 19\u201333 (1967)","journal-title":"Math. Aspects Comput. Sci."},{"key":"3_CR32","doi-asserted-by":"crossref","unstructured":"Gimenez, S., Moser, G.: The complexity of interaction. In: Bod\u00edk and Majumdar [7], pp. 243\u2013255","DOI":"10.1145\/2914770.2837646"},{"key":"3_CR33","unstructured":"G\u00f6del, K., Kleene, S.C., Rosser, J.B.: On undecidable propositions of formal mathematical systems. Institute for Advanced Study Princeton, NJ (1934)"},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Grobauer, B.: Cost recurrences for DML programs. In: Pierce, B.C. (ed.) ICFP, pp. 253\u2013264. ACM (2001)","DOI":"10.1145\/507669.507666"},{"key":"3_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"370","DOI":"10.1007\/978-3-540-70545-1_35","volume-title":"Computer Aided Verification","author":"BS Gulavani","year":"2008","unstructured":"Gulavani, B.S., Gulwani, S.: A numerical abstract domain based on expression abstraction and max operator with application in timing analysis. In: Gupta, A., Malik, S. (eds.) CAV 2008. LNCS, vol. 5123, pp. 370\u2013384. Springer, Heidelberg (2008). doi:10.1007\/978-3-540-70545-1_35"},{"key":"3_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1007\/978-3-642-02658-4_7","volume-title":"Computer Aided Verification","author":"S Gulwani","year":"2009","unstructured":"Gulwani, S.: SPEED: symbolic complexity bound analysis. In: Bouajjani, A., Maler, O. (eds.) CAV 2009. LNCS, vol. 5643, pp. 51\u201362. Springer, Heidelberg (2009). doi:10.1007\/978-3-642-02658-4_7"},{"key":"3_CR37","doi-asserted-by":"crossref","unstructured":"Gulwani, S., Mehra, K.K., Chilimbi, T.M.: SPEED: precise and efficient static estimation of program computational complexity. In: Shao, Z., Pierce, B.C. (eds.) POPL, pp. 127\u2013139. ACM (2009)","DOI":"10.1145\/1594834.1480898"},{"key":"3_CR38","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":"6","key":"3_CR39","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1007\/BF01211249","volume":"5","author":"WH Hesselink","year":"1993","unstructured":"Hesselink, W.H.: Proof rules for recursive procedures. Formal Asp. Comput. 5(6), 554\u2013570 (1993)","journal-title":"Formal Asp. Comput."},{"issue":"3","key":"3_CR40","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/2362389.2362393","volume":"34","author":"J Hoffmann","year":"2012","unstructured":"Hoffmann, J., Aehlig, K., Hofmann, M.: Multivariate amortized resource analysis. ACM Trans. Program. Lang. Syst. 34(3), 14 (2012)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"3_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1007\/978-3-642-31424-7_64","volume-title":"Computer Aided Verification","author":"J Hoffmann","year":"2012","unstructured":"Hoffmann, J., Aehlig, K., Hofmann, M.: Resource aware ML. In: Madhusudan, P., Seshia, S.A. (eds.) CAV 2012. LNCS, vol. 7358, pp. 781\u2013786. Springer, Heidelberg (2012). doi:10.1007\/978-3-642-31424-7_64"},{"key":"3_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-642-17164-2_13","volume-title":"Programming Languages and Systems","author":"J Hoffmann","year":"2010","unstructured":"Hoffmann, J., Hofmann, M.: Amortized resource analysis with polymorphic recursion and partial big-step operational semantics. In: Ueda, K. (ed.) APLAS 2010. LNCS, vol. 6461, pp. 172\u2013187. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-17164-2_13"},{"key":"3_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/978-3-642-11957-6_16","volume-title":"Programming Languages and Systems","author":"J Hoffmann","year":"2010","unstructured":"Hoffmann, J., Hofmann, M.: Amortized resource analysis with polynomial potential. In: Gordon, A.D. (ed.) ESOP 2010. LNCS, vol. 6012, pp. 287\u2013306. Springer, Heidelberg (2010). doi:10.1007\/978-3-642-11957-6_16"},{"key":"3_CR44","doi-asserted-by":"crossref","unstructured":"Hofmann, M., Jost, S.: Static prediction of heap space usage for first-order functional programs. In: Aiken, A., Morrisett, G. (eds.) POPL, pp. 185\u2013197. ACM (2003)","DOI":"10.1145\/640128.604148"},{"key":"3_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/11693024_3","volume-title":"Programming Languages and Systems","author":"M Hofmann","year":"2006","unstructured":"Hofmann, M., Jost, S.: Type-based amortised heap-space analysis. In: Sestoft, P. (ed.) ESOP 2006. LNCS, vol. 3924, pp. 22\u201337. Springer, Heidelberg (2006). doi:10.1007\/11693024_3"},{"key":"3_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-642-04027-6_24","volume-title":"Computer Science Logic","author":"M Hofmann","year":"2009","unstructured":"Hofmann, M., Rodriguez, D.: Efficient type-checking for amortised heap-space analysis. In: Gr\u00e4del, E., Kahle, R. (eds.) CSL 2009. LNCS, vol. 5771, pp. 317\u2013331. Springer, Heidelberg (2009). doi:10.1007\/978-3-642-04027-6_24"},{"key":"3_CR47","doi-asserted-by":"crossref","unstructured":"Hughes, J., Pareto, L.: Recursion and dynamic data-structures in bounded space: Towards embedded ML programming. In: R\u00e9mi, D., Lee, P. (eds.) ICFP. pp. 70\u201381. ACM (1999)","DOI":"10.1145\/317765.317785"},{"key":"3_CR48","doi-asserted-by":"crossref","unstructured":"Hughes, J., Pareto, L., Sabry, A.: Proving the correctness of reactive systems using sized types. In: Boehm, H., Jr., G.L.S. (eds.) POPL. pp. 410\u2013423. ACM Press (1996)","DOI":"10.1145\/237721.240882"},{"key":"3_CR49","unstructured":"Jones, C.: Probabilistic non-determinism. Ph.D. thesis, The University of Edinburgh (1989)"},{"key":"3_CR50","doi-asserted-by":"crossref","unstructured":"Jost, S., Hammond, K., Loidl, H., Hofmann, M.: Static determination of quantitative resource usage for higher-order programs. In: Hermenegildo, M.V., Palsberg, J. (eds.) POPL, pp. 223\u2013236. ACM (2010)","DOI":"10.1145\/1707801.1706327"},{"key":"3_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/978-3-642-05089-3_23","volume-title":"FM 2009: Formal Methods","author":"S Jost","year":"2009","unstructured":"Jost, S., Loidl, H.-W., Hammond, K., Scaife, N., Hofmann, M.: \u201cCarbon Credits\u201d for resource-bounded computations using amortised analysis. In: Cavalcanti, A., Dams, D.R. (eds.) FM 2009. LNCS, vol. 5850, pp. 354\u2013369. Springer, Heidelberg (2009). doi:10.1007\/978-3-642-05089-3_23"},{"key":"3_CR52","unstructured":"Knuth, D.E.: The Art of Computer Programming, vols. I\u2013III. Addison-Wesley, Reading (1973)"},{"key":"3_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/978-3-642-54833-8_21","volume-title":"Programming Languages and Systems","author":"T Kuwahara","year":"2014","unstructured":"Kuwahara, T., Terauchi, T., Unno, H., Kobayashi, N.: Automatic termination verification for higher-order functional programs. In: Shao, Z. (ed.) ESOP 2014. LNCS, vol. 8410, pp. 392\u2013411. Springer, Heidelberg (2014). doi:10.1007\/978-3-642-54833-8_21"},{"issue":"3","key":"3_CR54","doi-asserted-by":"publisher","first-page":"10:1","DOI":"10.1145\/1498926.1498928","volume":"31","author":"CS Lee","year":"2009","unstructured":"Lee, C.S.: Ranking functions for size-change termination. ACM Trans. Program. Lang. Syst. 31(3), 10:1\u201310:42 (2009)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"3_CR55","doi-asserted-by":"crossref","unstructured":"Lee, C.S., Jones, N.D., Ben-Amram, A.M.: The size-change principle for program termination. In: Hankin, C., Schmidt, D. (eds.) POPL, pp. 81\u201392. ACM (2001)","DOI":"10.1145\/373243.360210"},{"key":"3_CR56","unstructured":"lp_solve 5.5.2.3 (2016). http:\/\/lpsolve.sourceforge.net\/5.5\/"},{"key":"3_CR57","doi-asserted-by":"crossref","unstructured":"Olmedo, F., Kaminski, B.L., Katoen, J., Matheja, C.: Reasoning about recursive probabilistic programs. In: Grohe, M., Koskinen, E., Shankar, N. (eds.) LICS, pp. 672\u2013681. ACM (2016)","DOI":"10.1145\/2933575.2935317"},{"key":"3_CR58","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). doi:10.1007\/978-3-540-24622-0_20"},{"key":"3_CR59","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, Hoboken (1999)"},{"key":"3_CR60","volume-title":"Combinatorial Optimization - Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization - Polyhedra and Efficiency. Springer, Heidelberg (2003)"},{"issue":"2","key":"3_CR61","doi-asserted-by":"publisher","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. Complex. 26(2), 291\u2013301 (2013)","journal-title":"J. Syst. Sci. Complex."},{"key":"3_CR62","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/978-3-540-73228-0_25","volume-title":"Typed Lambda Calculi and Applications","author":"O Shkaravska","year":"2007","unstructured":"Shkaravska, O., Kesteren, R., Eekelen, M.: Polynomial size analysis of first-order functions. In: Rocca, S.R. (ed.) TLCA 2007. LNCS, vol. 4583, pp. 351\u2013365. Springer, Heidelberg (2007). doi:10.1007\/978-3-540-73228-0_25"},{"key":"3_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/978-3-319-08867-9_50","volume-title":"Computer Aided Verification","author":"M Sinn","year":"2014","unstructured":"Sinn, M., Zuleger, F., Veith, H.: A simple and scalable static analysis for bound analysis and amortized complexity analysis. In: Biere, A., Bloem, R. (eds.) CAV 2014. LNCS, vol. 8559, pp. 745\u2013761. Springer, Cham (2014). doi:10.1007\/978-3-319-08867-9_50"},{"key":"3_CR64","doi-asserted-by":"crossref","unstructured":"Sohn, K., Gelder, A.V.: Termination detection in logic programs using argument sizes. In: Rosenkrantz, D.J. (ed.) PODS, pp. 216\u2013226. ACM Press (1991)","DOI":"10.1145\/113413.113433"},{"key":"3_CR65","doi-asserted-by":"crossref","unstructured":"Srikanth, A., Sahin, B., Harris, W.R.: Complexity verification using guided theorem enumeration. In: Castagna and Gordon [11], pp. 639\u2013652","DOI":"10.1145\/3093333.3009864"},{"key":"3_CR66","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/978-3-642-38856-9_5","volume-title":"Static Analysis","author":"C Urban","year":"2013","unstructured":"Urban, C.: The abstract domain of segmented ranking functions. In: Logozzo, F., F\u00e4hndrich, M. (eds.) SAS 2013. LNCS, vol. 7935, pp. 43\u201362. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-38856-9_5"},{"issue":"3","key":"3_CR67","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1347375.1347389","volume":"7","author":"R Wilhelm","year":"2008","unstructured":"Wilhelm, R., et al.: The worst-case execution-time problem - overview of methods and survey of tools. ACM Trans. Embed. Comput. Syst. 7(3), 1\u201353 (2008)","journal-title":"ACM Trans. Embed. Comput. Syst."},{"issue":"1","key":"3_CR68","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":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-63390-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,13]],"date-time":"2021-07-13T00:06:09Z","timestamp":1626134769000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-63390-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319633893","9783319633909"],"references-count":68,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-63390-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"13 July 2017","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":"Heidelberg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 July 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 July 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cav2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/cavconference.org\/2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}