{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T09:05:07Z","timestamp":1742979907373,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031248405"},{"type":"electronic","value":"9783031248412"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"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":[[2023]]},"DOI":"10.1007\/978-3-031-24841-2_4","type":"book-chapter","created":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T00:04:39Z","timestamp":1673222679000},"page":"56-72","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Execution Time Program Verification with\u00a0Tight Bounds"],"prefix":"10.1007","author":[{"given":"Ana Carolina","family":"Silva","sequence":"first","affiliation":[]},{"given":"Manuel","family":"Barbosa","sequence":"additional","affiliation":[]},{"given":"M\u00e1rio","family":"Florido","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,8]]},"reference":[{"issue":"1","key":"4_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., et al.: Termination and cost analysis with COSTA and its user interfaces. Electron. Notes Theor. Comput. Sci. 258(1), 109\u2013121 (2009). https:\/\/doi.org\/10.1016\/j.entcs.2009.12.008","journal-title":"Electron. Notes Theor. Comput. Sci."},{"key":"4_CR2","doi-asserted-by":"publisher","unstructured":"Almeida, J.B., Frade, M.J., Pinto, J.S., de Sousa, S.M.: Rigorous Software Development - An Introduction to Program Verification. Undergraduate Topics in Computer Science. Springer, London (2011). https:\/\/doi.org\/10.1007\/978-0-85729-018-2","DOI":"10.1007\/978-0-85729-018-2"},{"issue":"6","key":"4_CR3","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1007\/s00165-019-00501-3","volume":"31","author":"KR Apt","year":"2019","unstructured":"Apt, K.R., Olderog, E.: Fifty years of Hoare\u2019s logic. Formal Aspects Comput. 31(6), 751\u2013807 (2019). https:\/\/doi.org\/10.1007\/s00165-019-00501-3","journal-title":"Formal Aspects Comput."},{"key":"4_CR4","doi-asserted-by":"publisher","unstructured":"Atkey, R.: Amortised resource analysis with separation logic. Log. Methods Comput. Sci. 7(2) (2011). https:\/\/doi.org\/10.2168\/LMCS-7(2:17)2011","DOI":"10.2168\/LMCS-7(2:17)2011"},{"key":"4_CR5","doi-asserted-by":"publisher","unstructured":"Avanzini, M., Lago, U.D.: Automating sized-type inference for complexity analysis. Proc. ACM Program. Lang. 1(ICFP), 43:1\u201343:29 (2017). https:\/\/doi.org\/10.1145\/3110287","DOI":"10.1145\/3110287"},{"key":"4_CR6","doi-asserted-by":"publisher","unstructured":"Barbosa, M., Barthe, G., Gr\u00e9goire, B., Koutsos, A., Strub, P.Y.: Mechanized proofs of adversarial complexity and application to universal composability. In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security, CCS 2021, pp. 2541\u20132563. Association for Computing Machinery, New York (2021). https:\/\/doi.org\/10.1145\/3460120.3484548","DOI":"10.1145\/3460120.3484548"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-642-54862-8_10","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"M Brockschmidt","year":"2014","unstructured":"Brockschmidt, M., Emmes, F., Falke, S., Fuhs, C., Giesl, J.: Alternating runtime and size complexity analysis of integer programs. In: \u00c1brah\u00e1m, E., Havelund, K. (eds.) TACAS 2014. LNCS, vol. 8413, pp. 140\u2013155. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54862-8_10"},{"key":"4_CR8","doi-asserted-by":"publisher","unstructured":"Carbonneaux, Q., Hoffmann, J., Ramananandro, T., Shao, Z.: End-to-end verification of stack-space bounds for C programs. In: O\u2019Boyle, M.F.P., Pingali, K. (eds.) ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2014, Edinburgh, United Kingdom, 09\u201311 June 2014, pp. 270\u2013281. ACM (2014). https:\/\/doi.org\/10.1145\/2594291.2594301","DOI":"10.1145\/2594291.2594301"},{"key":"4_CR9","doi-asserted-by":"publisher","unstructured":"Carbonneaux, Q., Hoffmann, J., Shao, Z.: Compositional certified resource bounds. In: Grove, D., Blackburn, S.M. (eds.) Proceedings of the 36th ACM SIGPLAN Conference on Programming Language Design and Implementation, Portland, OR, USA, 15\u201317 June 2015, pp. 467\u2013478. ACM (2015). https:\/\/doi.org\/10.1145\/2737924.2737955","DOI":"10.1145\/2737924.2737955"},{"key":"4_CR10","doi-asserted-by":"publisher","unstructured":"Dijkstra, E.W.: Guarded commands, non-determinacy and a calculus for the derivation of programs. In: Shooman, M.L., Yeh, R.T. (eds.) Proceedings of the International Conference on Reliable Software 1975, Los Angeles, California, USA, 21\u201323 April 1975, p. 2. ACM (1975). https:\/\/doi.org\/10.1145\/800027.808417","DOI":"10.1145\/800027.808417"},{"key":"4_CR11","doi-asserted-by":"publisher","unstructured":"Gulwani, S., Mehra, K.K., Chilimbi, T.: SPEED: precise and efficient static estimation of program computational complexity. In: Proceedings of the 36th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2009, pp. 127\u2013139. Association for Computing Machinery, New York (2009). https:\/\/doi.org\/10.1145\/1480881.1480898","DOI":"10.1145\/1480881.1480898"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/978-3-319-89960-2_9","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"MPL Haslbeck","year":"2018","unstructured":"Haslbeck, M.P.L., Nipkow, T.: Hoare logics for time bounds - a study in meta theory. In: Beyer, D., Huisman, M. (eds.) TACAS 2018, Part I. LNCS, vol. 10805, pp. 155\u2013171. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-89960-2_9"},{"key":"4_CR13","doi-asserted-by":"publisher","unstructured":"Hoffmann, J., Das, A., Weng, S.: Towards automatic resource bound analysis for OCaml. In: Castagna, G., Gordon, A.D. (eds.) Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, POPL 2017, Paris, France, 18\u201320 January 2017, pp. 359\u2013373. ACM (2017). https:\/\/doi.org\/10.1145\/3009837.3009842","DOI":"10.1145\/3009837.3009842"},{"key":"4_CR14","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). https:\/\/doi.org\/10.1007\/978-3-642-11957-6_16"},{"key":"4_CR15","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). https:\/\/doi.org\/10.1007\/11693024_3"},{"key":"4_CR16","doi-asserted-by":"publisher","unstructured":"Kaminski, B.L., Katoen, J., Matheja, C., Olmedo, F.: Weakest precondition reasoning for expected runtimes of randomized algorithms. J. ACM 65(5), 30:1\u201330:68 (2018). https:\/\/doi.org\/10.1145\/3208102","DOI":"10.1145\/3208102"},{"issue":"7","key":"4_CR17","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1145\/1538788.1538814","volume":"52","author":"X Leroy","year":"2009","unstructured":"Leroy, X.: Formal verification of a realistic compiler. Commun. ACM 52(7), 107\u2013115 (2009). https:\/\/doi.org\/10.1145\/1538788.1538814","journal-title":"Commun. ACM"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Loeckx, J., Sieber, K.: The Foundations of Program Verification, 2nd ed. Wiley-Teubner (1987)","DOI":"10.1007\/978-3-322-96753-4"},{"issue":"2","key":"4_CR19","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0167-6423(87)90029-3","volume":"9","author":"HR Nielson","year":"1987","unstructured":"Nielson, H.R.: A Hoare-like proof system for analysing the computation time of programs. Sci. Comput. Program. 9(2), 107\u2013136 (1987). https:\/\/doi.org\/10.1016\/0167-6423(87)90029-3","journal-title":"Sci. Comput. Program."},{"key":"4_CR20","doi-asserted-by":"publisher","unstructured":"Nielson, H.R., Nielson, F.: Semantics with Applications: An Appetizer. Undergraduate Topics in Computer Science. Springer, London (2007). https:\/\/doi.org\/10.1007\/978-1-84628-692-6","DOI":"10.1007\/978-1-84628-692-6"},{"key":"4_CR21","doi-asserted-by":"publisher","unstructured":"Radi\u010dek, I., Barthe, G., Gaboardi, M., Garg, D., Zuleger, F.: Monadic refinements for relational cost analysis. Proc. ACM Program. Lang. 2(POPL) (2017). https:\/\/doi.org\/10.1145\/3158124","DOI":"10.1145\/3158124"},{"key":"4_CR22","doi-asserted-by":"publisher","first-page":"739","DOI":"10.1017\/S147106841400057X","volume":"14","author":"A Serrano","year":"2014","unstructured":"Serrano, A., L\u00f3pez-Garc\u00eda, P., Hermenegildo, M.V.: Resource usage analysis of logic programs via abstract interpretation using sized types. Theory Pract. Log. Program. 14, 739\u2013754 (2014). https:\/\/doi.org\/10.1017\/S147106841400057X","journal-title":"Theory Pract. Log. Program."},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Silva, A.C., Barbosa, M., Florido, M.: Execution time program verification with tight bounds (2022). Available from Arxiv","DOI":"10.1007\/978-3-031-24841-2_4"},{"key":"4_CR24","doi-asserted-by":"publisher","unstructured":"Sim\u00f5es, H.R., Vasconcelos, P.B., Florido, M., Jost, S., Hammond, K.: Automatic amortised analysis of dynamic memory allocation for lazy functional programs. In: Thiemann, P., Findler, R.B. (eds.) ACM SIGPLAN International Conference on Functional Programming, ICFP 2012, Copenhagen, Denmark, 9\u201315 September 2012, pp. 165\u2013176. ACM (2012). https:\/\/doi.org\/10.1145\/2364527.2364575","DOI":"10.1145\/2364527.2364575"},{"issue":"2","key":"4_CR25","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1137\/0606031","volume":"6","author":"RE Tarjan","year":"1985","unstructured":"Tarjan, R.E.: Amortized computational complexity. SIAM J. Algebraic Discrete Methods 6(2), 306\u2013318 (1985). https:\/\/doi.org\/10.1137\/0606031","journal-title":"SIAM J. Algebraic Discrete Methods"},{"key":"4_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1007\/978-3-662-46669-8_32","volume-title":"Programming Languages and Systems","author":"P Vasconcelos","year":"2015","unstructured":"Vasconcelos, P., Jost, S., Florido, M., Hammond, K.: Type-based allocation analysis for co-recursion in lazy functional languages. In: Vitek, J. (ed.) ESOP 2015. LNCS, vol. 9032, pp. 787\u2013811. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46669-8_32"}],"container-title":["Lecture Notes in Computer Science","Practical Aspects of Declarative Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-24841-2_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T14:08:22Z","timestamp":1673273302000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-24841-2_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031248405","9783031248412"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-24841-2_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"8 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PADL","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Practical Aspects of Declarative Languages","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Boston , MA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 January 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 January 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"padl2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/popl23.sigplan.org\/home\/PADL-2023","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"36","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"15","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"42% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}