{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T20:31:05Z","timestamp":1792787465424,"version":"4.5.0"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA1","license":[{"start":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T00:00:00Z","timestamp":1775779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Swedish Research Council","award":["2021-06327"],"award-info":[{"award-number":["2021-06327"]}],"id":[{"id":"https:\/\/ror.org\/03zttf063","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Swedish Research Council","award":["2024-05195"],"award-info":[{"award-number":["2024-05195"]}],"id":[{"id":"https:\/\/ror.org\/03zttf063","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Swedish Research Council","award":["2025-06185"],"award-info":[{"award-number":["2025-06185"]}],"id":[{"id":"https:\/\/ror.org\/03zttf063","id-type":"ROR","asserted-by":"crossref"}]},{"name":"Ethereum Foundation","award":["FY25-2124"],"award-info":[{"award-number":["FY25-2124"]}],"id":[{"id":"https:\/\/ror.org\/05j1x9f71","id-type":"ROR","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2026,4,10]]},"abstract":"<jats:p>\n                    Verification of programs operating on heap-allocated data structures, for instance lists or trees, poses significant challenges due to the potentially unbounded size of such data structures. We present\n                    <jats:italic toggle=\"yes\">time-indexed heap invariants<\/jats:italic>\n                    , a novel invariant-based heap encoding leveraging uninterpreted predicates and prophecy variables to reduce verification of heap-manipulating programs to verification of programs over integers only. Our encoding of heap is general and agnostic to specific data structures. To the best of our knowledge, our approach is the first heap invariant-based method that achieves both soundness and completeness. We provide formal proofs establishing the correctness of our encodings. Through an experimental evaluation, we demonstrate that time-indexed heap invariants significantly extend the capability of existing verification tools, allowing automatic verification of programs with heap that were previously out of reach for state-of-the-art tools.\n                  <\/jats:p>","DOI":"10.1145\/3798228","type":"journal-article","created":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T14:33:43Z","timestamp":1775831623000},"page":"794-822","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sound and Complete Invariant-Based Heap Encodings"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1522-6673","authenticated-orcid":false,"given":"Zafer","family":"Esen","sequence":"first","affiliation":[{"name":"Uppsala University, Uppsala, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2733-7098","authenticated-orcid":false,"given":"Philipp","family":"R\u00fcmmer","sequence":"additional","affiliation":[{"name":"University of Regensburg, Regensburg, Germany"},{"name":"Uppsala University, Uppsala, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8967-6987","authenticated-orcid":false,"given":"Tjark","family":"Weber","sequence":"additional","affiliation":[{"name":"Uppsala University, Uppsala, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,4,10]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90224-P"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-57256-2_21"},{"key":"e_1_3_1_4_2","volume-title":"The SMT-LIB Standard: Version 2.6","author":"Barrett Clark","year":"2017","unstructured":"Clark Barrett, Pascal Fontaine, and Cesare Tinelli. 2017. The SMT-LIB Standard: Version 2.6. Technical Report. Department of Computer Science, The University of Iowa. Available at www.SMT-LIB.org."},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2008.27"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73368-3_22"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-57256-2_15"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_16"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23534-9_2"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38856-9_8"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22438-6_15"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1561\/2500000037"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74061-2_24"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39910-0_11"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/512950.512973"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068421000211"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2017-1461"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/11691372_19"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_29"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-68446-4_9"},{"key":"e_1_3_1_21_2","unstructured":"Zafer Esen and Philipp R\u00fcmmer. 2021. A Theory of Heap for Constrained Horn Clauses (Extended Technical Report). CoRR abs\/2104.04224 (2021). arXiv:2104.04224 https:\/\/arxiv.org\/abs\/2104.04224"},{"key":"e_1_3_1_22_2","first-page":"38","volume-title":"Proceedings of the 20th Internal Workshop on Satisfiability Modulo Theories co-located with the 11th International Joint Conference on Automated Reasoning (IJCAR 2022) part of the 8th Federated Logic Conference (FLoC 2022), Haifa, Israel, August 11-12, 2022 (CEUR Workshop Proceedings, Vol. 3185)","author":"Esen Zafer","year":"2022","unstructured":"Zafer Esen and Philipp R\u00fcmmer. 2022. An SMT-LIB Theory of Heaps. In Proceedings of the 20th Internal Workshop on Satisfiability Modulo Theories co-located with the 11th International Joint Conference on Automated Reasoning (IJCAR 2022) part of the 8th Federated Logic Conference (FLoC 2022), Haifa, Israel, August 11-12, 2022 (CEUR Workshop Proceedings, Vol. 3185), David D\u00e9harbe and Antti E. J. Hyv\u00e4rinen (Eds.). CEUR-WS.org, 38\u201353. https:\/\/ceur-ws.org\/Vol-3185\/paper1180.pdf"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.34727\/2022\/isbn.978-3-85448-053-2_45"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","unstructured":"Zafer Esen Philipp R\u00fcmmer and Tjark Weber. 2026. Artifact for the paper \u201cSound and Complete Invariant-Based Heap Encodings\u201d. doi:10.5281\/zenodo.18500638","DOI":"10.5281\/zenodo.18500638"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-98668-0_1"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/373243.360220"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/113445.113468"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-22308-2_11"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21690-4_20"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","unstructured":"Luk\u00e1s Hol\u00edk Michal Kotoun Petr Peringer Veronika Sokov\u00e1 Marek Trt\u00edk and Tom\u00e1s Vojnar. 2016. Predator Shape Analysis Tool Suite. In Hardware and Software: Verification and Testing - 12th International Haifa Verification Conference HVC 2016 Haifa Israel November 14-17 2016 Proceedings (Lecture Notes in Computer Science Vol. 10028) Roderick Bloem and Eli Arbel (Eds.). 202\u2013209. doi:10.1007\/978-3-319-49052-6_13","DOI":"10.1007\/978-3-319-49052-6_13"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39799-8_52"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/567752.567776"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.29007\/zrct"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_19"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1667048.1667051"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2015.7542257"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3158125"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-44914-8_12"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-89963-3_24"},{"key":"e_1_3_1_40_2","first-page":"21","volume-title":"Information Processing, Proceedings of the 2nd IFIP Congress 1962, Munich, Germany, August 27 - September 1, 1962","author":"McCarthy John","year":"1962","unstructured":"John McCarthy. 1962. Towards a Mathematical Science of Computation. In Information Processing, Proceedings of the 2nd IFIP Congress 1962, Munich, Germany, August 27 - September 1, 1962. North-Holland, 21\u201328."},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30823-9_32"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53413-7_18"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-49122-5_2"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44802-0_1"},{"key":"e_1_3_1_45_2","volume-title":"Axiomatic Proof Techniques for Parallel Programs","author":"Owicki Susan S.","year":"1975","unstructured":"Susan S. Owicki. 1975. Axiomatic Proof Techniques for Parallel Programs. Ph.D. Dissertation. Cornell University, USA."},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45237-7_30"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2002.1029817"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375602"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-82700-6_10"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1955.5.285"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ECOOP.2024.43"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-98668-0_3"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798228","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T11:22:38Z","timestamp":1790421758000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,10]]},"references-count":51,"journal-issue":{"issue":"OOPSLA1","published-print":{"date-parts":[[2026,4,10]]}},"alternative-id":["10.1145\/3798228"],"URL":"https:\/\/doi.org\/10.1145\/3798228","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,10]]},"assertion":[{"value":"2025-10-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-02-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-10","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}