{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T22:48:28Z","timestamp":1775861308258,"version":"3.50.1"},"publisher-location":"Cham","reference-count":28,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032227225","type":"print"},{"value":"9783032227232","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-22723-2_7","type":"book-chapter","created":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T11:59:38Z","timestamp":1775822378000},"page":"181-209","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Ranking Function-Based Termination Analysis via Bidirectional Decompositional Search"],"prefix":"10.1007","author":[{"given":"Yasmin Chandini","family":"Sarita","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avaljot","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaurya","family":"Gomber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gagandeep","family":"Singh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mahesh","family":"Vishwanathan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,10]]},"reference":[{"key":"7_CR1","doi-asserted-by":"publisher","unstructured":"Albert, E., Arenas, P., Genaim, S., Puebla, G., Zanardini, D.: Costa: Design and implementation of a cost and termination analyzer for java bytecode. pp. 113\u2013132 (10 2007). https:\/\/doi.org\/10.1007\/978-3-540-92188-2_5","DOI":"10.1007\/978-3-540-92188-2_5"},{"key":"7_CR2","doi-asserted-by":"crossref","unstructured":"Beyer, D.: Advances in automatic software verification: Sv-comp 2020. In: Biere, A., Parker, D. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. pp. 347\u2013367. Springer International Publishing, Cham (2020)","DOI":"10.1007\/978-3-030-45237-7_21"},{"key":"7_CR3","doi-asserted-by":"publisher","unstructured":"Borralleras, C., Brockschmidt, M., Larraz, D., Oliveras, A., Rodr\u00edguez-Carbonell, E., Rubio, A.: Proving termination through conditional termination. In: Proceedings, Part I, of the 23rd International Conference on Tools and Algorithms for the Construction and Analysis of Systems - Volume 10205. p. 99\u2013117. Springer-Verlag, Berlin, Heidelberg (201https:\/\/doi.org\/10.1007\/978-3-662-54577-5_6, https:\/\/doi.org\/10.1007\/978-3-662-54577-5_6","DOI":"10.1007\/978-3-662-54577-5_6"},{"key":"7_CR4","doi-asserted-by":"crossref","unstructured":"Bradley, A.R.: Sat-based model checking without unrolling. In: Jhala, R., Schmidt, D. (eds.) Verification, Model Checking, and Abstract Interpretation. pp. 70\u201387. Springer Berlin Heidelberg, Berlin, Heidelberg (2011)","DOI":"10.1007\/978-3-642-18275-4_7"},{"key":"7_CR5","doi-asserted-by":"crossref","unstructured":"Bradley, A.R., Manna, Z., Sipma, H.B.: Linear ranking with reachability. In: Etessami, K., Rajamani, S.K. (eds.) Computer Aided Verification. pp. 491\u2013504. Springer Berlin Heidelberg, Berlin, Heidelberg (2005)","DOI":"10.1007\/11513988_48"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Bradley, A.R., Manna, Z., Sipma, H.B.: Termination of polynomial programs. In: Cousot, R. (ed.) Verification, Model Checking, and Abstract Interpretation. pp. 113\u2013129. Springer Berlin Heidelberg, Berlin, Heidelberg (2005)","DOI":"10.1007\/978-3-540-30579-8_8"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Brockschmidt, M., Cook, B., Fuhs, C.: Better termination proving through cooperation. In: Sharygina, N., Veith, H. (eds.) Computer Aided Verification. pp. 413\u2013429. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)","DOI":"10.1007\/978-3-642-39799-8_28"},{"key":"7_CR8","doi-asserted-by":"publisher","unstructured":"Chen, H.Y., David, C., Kroening, D., Schrammel, P., Wachter, B.: Synthesising interprocedural bit-precise termination proofs. In: Proceedings of the 30th IEEE\/ACM International Conference on Automated Software Engineering. p. 53\u201364. ASE \u201915, IEEE Press (201https:\/\/doi.org\/10.1109\/ASE.2015.10, https:\/\/doi.org\/10.1109\/ASE.2015.10","DOI":"10.1109\/ASE.2015.10"},{"key":"7_CR9","doi-asserted-by":"publisher","unstructured":"Cook, B., Podelski, A., Rybalchenko, A.: Termination proofs for systems code. In: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation. p. 415\u2013426. PLDI \u201906, Association for Computing Machinery, New York, NY, USA (2006https:\/\/doi.org\/10.1145\/1133981.1134029, https:\/\/doi.org\/10.1145\/1133981.1134029","DOI":"10.1145\/1133981.1134029"},{"key":"7_CR10","doi-asserted-by":"publisher","unstructured":"Giacobbe, M., Kroening, D., Parsert, J.: Neural termination analysis. In: Proceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering. p. 633\u2013645. ESEC\/FSE 2022, Association for Computing Machinery, New York, NY, USA (2022).https:\/\/doi.org\/10.1145\/3540250.3549120, https:\/\/doi.org\/10.1145\/3540250.3549120","DOI":"10.1145\/3540250.3549120"},{"key":"7_CR11","doi-asserted-by":"publisher","unstructured":"Giesl, J., Aschermann, C., Brockschmidt, M., Emmes, F., Frohn, F., Fuhs, C., Hensel, J., Otto, C., Pl\u00fccker, M., Schneider-Kamp, P., Str\u00f6der, T., Swiderski, S., Thiemann, R.: Analyzing program termination and complexity automatically with aprove. J. Autom. Reason. 58(1), 3\u201331 (jan 2017https:\/\/doi.org\/10.1007\/s10817-016-9388-y, https:\/\/doi.org\/10.1007\/s10817-016-9388-y","DOI":"10.1007\/s10817-016-9388-y"},{"key":"7_CR12","doi-asserted-by":"crossref","unstructured":"Giesl, J., Rubio, A., Sternagel, C., Waldmann, J., Yamada, A.: The termination and complexity competition. In: Beyer, D., Huisman, M., Kordon, F., Steffen, B. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. pp. 156\u2013166. Springer International Publishing, Cham (2019)","DOI":"10.1007\/978-3-030-17502-3_10"},{"key":"7_CR13","doi-asserted-by":"publisher","unstructured":"Gonnord, L., Monniaux, D., Radanne, G.: Synthesis of ranking functions using extremal counterexamples. SIGPLAN Not. 50(6), 608\u2013618 (jun 2015https:\/\/doi.org\/10.1145\/2813885.2737976, https:\/\/doi.org\/10.1145\/2813885.2737976","DOI":"10.1145\/2813885.2737976"},{"key":"7_CR14","doi-asserted-by":"publisher","unstructured":"Heizmann, M., Hoenicke, J., Podelski, A.: Termination analysis by learning terminating programs (05 2014https:\/\/doi.org\/10.1007\/978-3-319-08867-9_53","DOI":"10.1007\/978-3-319-08867-9_53"},{"key":"7_CR15","unstructured":"Kamath, A., Senthilnathan, A., Chakraborty, S., Deligiannis, P., Lahiri, S., Lal, A., Rastogi, A., Roy, S., Sharma, R.: Leveraging llms for program verification. In: Formal Methods in Computer-Aided Design (FMCAD) (October 2024)"},{"key":"7_CR16","doi-asserted-by":"publisher","unstructured":"Larraz, D., Oliveras, A., Rodr\u00edguez-Carbonell, E., Rubio, A.: Proving termination of imperative programs using max-smt. In: 2013 Formal Methods in Computer-Aided Design. pp. 218\u2013225 (201https:\/\/doi.org\/10.1109\/FMCAD.2013.6679413","DOI":"10.1109\/FMCAD.2013.6679413"},{"key":"7_CR17","doi-asserted-by":"publisher","unstructured":"Le, T.C., Antonopoulos, T., Fathololumi, P., Koskinen, E., Nguyen, T.: Dynamite: Dynamic termination and non-termination proofs. Proc. ACM Program. Lang. 4(OOPSLA) (nov 2020https:\/\/doi.org\/10.1145\/3428257, https:\/\/doi.org\/10.1145\/3428257","DOI":"10.1145\/3428257"},{"key":"7_CR18","doi-asserted-by":"publisher","unstructured":"Magill, S., Tsai, M.H., Lee, P., Tsay, Y.K.: Automatic numeric abstractions for heap-manipulating programs. vol.\u00a045, pp. 211\u2013222 (01 2010).https:\/\/doi.org\/10.1145\/1706299.1706326","DOI":"10.1145\/1706299.1706326"},{"key":"7_CR19","doi-asserted-by":"publisher","unstructured":"Nguyen, T., Kapur, D., Weimer, W., Forrest, S.: Dig: A dynamic invariant generator for polynomial and array invariants. ACM Trans. Softw. Eng. Methodol. 23(4) (sep 2014https:\/\/doi.org\/10.1145\/2556782, https:\/\/doi.org\/10.1145\/2556782","DOI":"10.1145\/2556782"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Podelski, A., Rybalchenko, A.: A complete method for the synthesis of linear ranking functions. In: Steffen, B., Levi, G. (eds.) Verification, Model Checking, and Abstract Interpretation. pp. 239\u2013251. Springer Berlin Heidelberg, Berlin, Heidelberg (2004)","DOI":"10.1007\/978-3-540-24622-0_20"},{"key":"7_CR21","doi-asserted-by":"publisher","unstructured":"Str\u00f6der, T., Giesl, J., Brockschmidt, M., Frohn, F., Fuhs, C., Hensel, J., Schneider-Kamp, P., Aschermann, C.: Automatically proving termination and memory safety for programs with pointer arithmetic. J. Autom. Reason. 58(1), 33\u201365 (Jan 2017). https:\/\/doi.org\/10.1007\/s10817-016-9389-x, https:\/\/doi.org\/10.1007\/s10817-016-9389-x","DOI":"10.1007\/s10817-016-9389-x"},{"key":"7_CR22","doi-asserted-by":"publisher","unstructured":"Unno, H., Terauchi, T., Gu, Y., Koskinen, E.: Modular primal-dual fixpoint logic solving for temporal verification. Proc. ACM Program. Lang. 7(POPL) (jan 2023https:\/\/doi.org\/10.1145\/3571265, https:\/\/doi.org\/10.1145\/3571265","DOI":"10.1145\/3571265"},{"key":"7_CR23","doi-asserted-by":"crossref","unstructured":"Unno, H., Terauchi, T., Koskinen, E.: Constraint-based relational verification. In: Silva, A., Leino, K.R.M. (eds.) Computer Aided Verification. pp. 742\u2013766. Springer International Publishing, Cham (2021)","DOI":"10.1007\/978-3-030-81685-8_35"},{"key":"7_CR24","doi-asserted-by":"crossref","unstructured":"Urban, C., Gurfinkel, A., Kahsai, T.: Synthesizing ranking functions from bits and pieces. In: Chechik, M., Raskin, J.F. (eds.) Tools and Algorithms for the Construction and Analysis of Systems. pp. 54\u201370. Springer Berlin Heidelberg, Berlin, Heidelberg (2016)","DOI":"10.1007\/978-3-662-49674-9_4"},{"key":"7_CR25","doi-asserted-by":"publisher","unstructured":"Welp, T., Kuehlmann, A.: Property directed invariant refinement for program verification. In: 2014 Design, Automation & Test in Europe Conference & Exhibition (DATE). pp.\u00a01\u20136 (2014). https:\/\/doi.org\/10.7873\/DATE.2014.127","DOI":"10.7873\/DATE.2014.127"},{"key":"7_CR26","doi-asserted-by":"publisher","unstructured":"Xie, X., Chen, B., Zou, L., Lin, S.W., Liu, Y., Li, X.: Loopster: Static loop termination analysis. In: Proceedings of the 2017 11th Joint Meeting on Foundations of Software Engineering. p. 84\u201394. ESEC\/FSE 2017, Association for Computing Machinery, New York, NY, USA (2017).https:\/\/doi.org\/10.1145\/3106237.3106260, https:\/\/doi.org\/10.1145\/3106237.3106260","DOI":"10.1145\/3106237.3106260"},{"key":"7_CR27","doi-asserted-by":"publisher","unstructured":"Xu, R., Chen, J., He, F.: Data-driven loop bound learning for termination analysis. In: Proceedings of the 44th International Conference on Software Engineering. p. 499\u2013510. ICSE \u201922, Association for Computing Machinery, New York, NY, USA (2022https:\/\/doi.org\/10.1145\/3510003.3510220, https:\/\/doi.org\/10.1145\/3510003.3510220","DOI":"10.1145\/3510003.3510220"},{"key":"7_CR28","doi-asserted-by":"publisher","unstructured":"Zhu, S., Kincaid, Z.: Breaking the mold: Nonlinear ranking function synthesis without templates. In: Computer Aided Verification: 36th International Conference, CAV 2024, Montreal, QC, Canada, July 24\u201327, 2024, Proceedings, Part I. p. 431\u2013452. Springer-Verlag, Berlin, Heidelberg (2024).https:\/\/doi.org\/10.1007\/978-3-031-65627-9_21, https:\/\/doi.org\/10.1007\/978-3-031-65627-9_21","DOI":"10.1007\/978-3-031-65627-9_21"}],"container-title":["Lecture Notes in Computer Science","Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-22723-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T22:03:01Z","timestamp":1775858581000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-22723-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032227225","9783032227232"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-22723-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"10 April 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ESOP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Symposium on Programming","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Turin","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"35","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"esop2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/etaps.org\/about\/esop\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}