{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T02:44:48Z","timestamp":1767926688615,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,7,15]],"date-time":"2022-07-15T00:00:00Z","timestamp":1657843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"DFG Koselleck","award":["NI 491\/16-1"],"award-info":[{"award-number":["NI 491\/16-1"]}]},{"name":"Verifizierte Algorithmenanalyse","award":["LA 3292\/1"],"award-info":[{"award-number":["LA 3292\/1"]}]},{"name":"Verifizierte Model Checker"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>\n            We present a framework to verify both, functional correctness and (amortized) worst-case complexity of practically efficient algorithms. We implemented a stepwise refinement approach, using the novel concept of\n            <jats:italic>resource currencies<\/jats:italic>\n            to naturally structure the resource analysis along the refinement chain, and allow a fine-grained analysis of operation counts. Our framework targets the LLVM intermediate representation. We extend its semantics from earlier work with a cost model. As case studies, we verify the amortized constant time push operation on dynamic arrays and the\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\u2009\n            <jats:italic>n<\/jats:italic>\n            ) introsort algorithm, and refine them down to efficient LLVM implementations. Our sorting algorithm performs on par with the state-of-the-art implementation found in the GNU C++ Library, and provably satisfies the complexity required by the C++ standard.\n          <\/jats:p>","DOI":"10.1145\/3486169","type":"journal-article","created":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T21:25:53Z","timestamp":1645651553000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["For a Few Dollars More: Verified Fine-Grained Algorithm\u00a0Analysis Down to LLVM"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4306-869X","authenticated-orcid":false,"given":"Maximilian P. L.","family":"Haslbeck","sequence":"first","affiliation":[{"name":"Technische Universit\u00e4t M\u00fcnchen, Munich, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peter","family":"Lammich","sequence":"additional","affiliation":[{"name":"University of Twente, Enschede, Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,7,15]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11957-6_6"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-009-9148-3"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.30"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/2594291.2594301"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3408998"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22102-1_9"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-017-9431-7"},{"key":"e_1_3_2_9_2","unstructured":"cppreference. [n.d.]. C++ Standard Library Specification of Sort. Retrieved 12 October 2020 from https:\/\/en.cppreference.com\/w\/cpp\/algorithm\/sort."},{"key":"e_1_3_2_10_2","volume-title":"A Discipline of Programming","author":"Dijkstra Edsger W.","year":"1976","unstructured":"Edsger W. Dijkstra. 1976. A Discipline of Programming. Prentice-Hall. Retrieved fromhttps:\/\/www.worldcat.org\/oclc\/01958445."},{"key":"e_1_3_2_11_2","unstructured":"GNU C++ Library [n.d.]. The GNU C++ Library. Retrieved May 18th 2022 from https:\/\/gcc.gnu.org\/onlinedocs\/libstdc++\/. Version 7.4.0."},{"key":"e_1_3_2_12_2","unstructured":"Arma\u00ebl Gu\u00e9neau. 2019. Mechanized Verification of the Correctness and Asymptotic Complexity of Programs. (V\u00e9rification m\u00e9canis\u00e9e de la correction et complexit\u00e9 asymptotique de programmes) . Ph.D. Dissertation. Inria Paris France. Retrieved from https:\/\/tel.archives-ouvertes.fr\/tel-02437532."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-89884-1_19"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITP.2019.18"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITP.2019.20"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-72019-3_11"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/366622.366644"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49498-1_15"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90012-1"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.4204\/eptcs.43.1"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22102-1_17"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2854065.2854067"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITP.2019.22"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-017-9437-1"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-51054-1_18"},{"key":"e_1_3_2_26_2","article-title":"A separation logic framework for Imperative HOL","author":"Lammich Peter","year":"2012","unstructured":"Peter Lammich and Rene Meis. 2012. A separation logic framework for Imperative HOL. Archive of Formal Proofs (Nov. 2012). Retrieved from http:\/\/isa-afp.org\/entries\/Separation_Logic_Imperative_HOL.html, Formal proof development.","journal-title":"Archive of Formal Proofs"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32347-8_12"},{"key":"e_1_3_2_28_2","unstructured":"libc++ [n.d.]. \u201dlibc++\u201d C++ Standard Library. Retrieved 20. May 2022 from https:\/\/releases.llvm.org\/14.0.0\/projects\/libcxx\/docs\/."},{"key":"e_1_3_2_29_2","unstructured":"Adri\u00e1n L\u00f6wenberg Casas. 2019. Proof af the Amortized time complexity of an efficient Union-Find data structure in Isabelle\/HOL . BS Thesis. Technical University of Munich."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17184-1_1"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/261387.261395"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59152-6_2"},{"key":"e_1_3_2_33_2","unstructured":"Vineet Rajani. 2020. A type-theory for higher-order amortized analysis . Ph.D. Dissertation. Saarland University Saarbr\u00fccken Germany. Retrieved from https:\/\/publikationen.sulb.uni-saarland.de\/handle\/20.500.11880\/29104."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/3434308"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/99370.99404"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/91556.91592"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133903"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-94205-6_35"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3486169","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3486169","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:07Z","timestamp":1750191127000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3486169"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,15]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3486169"],"URL":"https:\/\/doi.org\/10.1145\/3486169","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,15]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}