{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,8]],"date-time":"2026-10-08T11:37:01Z","timestamp":1791459421713,"version":"4.3.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2017,12,27]],"date-time":"2017-12-27T00:00:00Z","timestamp":1514332800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2013-T2-2-146"],"award-info":[{"award-number":["MOE2013-T2-2-146"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","award":["R-252-000-553-112"],"award-info":[{"award-number":["R-252-000-553-112"]}],"id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>The symbolic-heap fragment of separation logic has been actively developed and advocated for verifying the memory-safety property of computer programs. At present, one of its biggest challenges is to effectively prove entailments containing inductive heap predicates. These entailments are usually proof obligations generated when verifying programs that manipulate complex data structures like linked lists, trees, or graphs.<\/jats:p>\n          <jats:p>To assist in proving such entailments, this paper introduces a lemma synthesis framework, which automatically discovers lemmas to serve as eureka steps in the proofs. Mathematical induction and template-based constraint solving are two pillars of our framework. To derive the supporting lemmas for a given entailment, the framework firstly identifies possible lemma templates from the entailment's heap structure. It then sets up unknown relations among each template's variables and conducts structural induction proof to generate constraints about these relations. Finally, it solves the constraints to find out actual definitions of the unknown relations, thus discovers the lemmas. We have integrated this framework into a prototype prover and have experimented it on various entailment benchmarks. The experimental results show that our lemma-synthesis-assisted prover can prove many entailments that could not be handled by existing techniques. This new proposal opens up more opportunities to automatically reason with complex inductive heap predicates.<\/jats:p>","DOI":"10.1145\/3158097","type":"journal-article","created":{"date-parts":[[2017,12,29]],"date-time":"2017-12-29T14:21:49Z","timestamp":1514557309000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Automated lemma synthesis in symbolic-heap separation logic"],"prefix":"10.1145","volume":"2","author":[{"given":"Quang-Trung","family":"Ta","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ton Chanh","family":"Le","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Siau-Cheng","family":"Khoo","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wei-Ngan","family":"Chin","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,12,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-46669-8_26"},{"key":"e_1_2_2_2_1","unstructured":"Rajeev Alur Rastislav Bod\u00edk Eric Dallal Dana Fisman Pranav Garg Garvit Juniwal Hadas Kress-Gazit P. Madhusudan Milo M. K. Martin Mukund Raghothaman Shambwaditya Saha Sanjit A. Seshia Rishabh Singh Armando Solar-Lezama Emina Torlak and Abhishek Udupa. 2015. Syntax-Guided Synthesis. In Dependable Software Systems Engineering. 1\u201325.  Rajeev Alur Rastislav Bod\u00edk Eric Dallal Dana Fisman Pranav Garg Garvit Juniwal Hadas Kress-Gazit P. Madhusudan Milo M. K. Martin Mukund Raghothaman Shambwaditya Saha Sanjit A. Seshia Rishabh Singh Armando Solar-Lezama Emina Torlak and Abhishek Udupa. 2015. Syntax-Guided Synthesis. In Dependable Software Systems Engineering. 1\u201325."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30538-5_9"},{"key":"e_1_2_2_4_1","volume-title":"Smallfoot: Modular Automatic Assertion Checking with Separation Logic. In International Symposium on Formal Methods for Components and Objects. 115\u2013137","author":"Berdine Josh","unstructured":"Josh Berdine , Cristiano Calcagno , and Peter W . O\u2019Hearn. 2005a . Smallfoot: Modular Automatic Assertion Checking with Separation Logic. In International Symposium on Formal Methods for Components and Objects. 115\u2013137 . Josh Berdine, Cristiano Calcagno, and Peter W. O\u2019Hearn. 2005a. Smallfoot: Modular Automatic Assertion Checking with Separation Logic. In International Symposium on Formal Methods for Components and Objects. 115\u2013137."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11575467_5"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22110-1_15"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-010-9179-9"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22438-6_12"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603091"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837621"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exq052"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-044450813-3\/50015-1"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-17524-9_1"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2010.07.004"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737984"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45069-6_39"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23217-6_16"},{"key":"e_1_2_2_18_1","volume-title":"Parkinson","author":"Distefano Dino","year":"2008","unstructured":"Dino Distefano and Matthew J . Parkinson . 2008 . jStar: towards practical verification for java. 213\u2013226. Dino Distefano and Matthew J. Parkinson. 2008. jStar: towards practical verification for java. 213\u2013226."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-12736-1_17"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24953-7_7"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-38574-2_2"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11936-6_15"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41528-4_21"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78800-3_24"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70545-1_34"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44802-0_1"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993563"},{"key":"e_1_2_2_28_1","volume-title":"Separation Logic Modulo Theories. In Asian Symposium on Programming Languages and Systems (APLAS). 90\u2013106","author":"Navarro P\u00e9rez Juan Antonio","year":"2013","unstructured":"Juan Antonio Navarro P\u00e9rez and Andrey Rybalchenko . 2013 . Separation Logic Modulo Theories. In Asian Symposium on Programming Languages and Systems (APLAS). 90\u2013106 . Juan Antonio Navarro P\u00e9rez and Andrey Rybalchenko. 2013. Separation Logic Modulo Theories. In Asian Symposium on Programming Languages and Systems (APLAS). 90\u2013106."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2958031.2958054"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_47"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491956.2462169"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2002.1029817"},{"key":"e_1_2_2_33_1","volume-title":"Copenhagen","author":"Reynolds John C.","year":"2008","unstructured":"John C. Reynolds . 2008. An Introduction to Separation Logic. Lecture Notes for the PhD Fall School on Logics and Semantics of State , Copenhagen 2008 . Retrieved on 2017, March 16th. http:\/\/www.cs.cmu.edu\/~jcr\/copenhagen08.pdf John C. Reynolds. 2008. An Introduction to Separation Logic. Lecture Notes for the PhD Fall School on Logics and Semantics of State, Copenhagen 2008. Retrieved on 2017, March 16th. http:\/\/www.cs.cmu.edu\/~jcr\/copenhagen08.pdf"},{"key":"e_1_2_2_34_1","volume-title":"Theory of Linear and Integer Programming","author":"Schrijver Alexander","unstructured":"Alexander Schrijver . 1986. Theory of Linear and Integer Programming . John Wiley & Sons, Inc. , New York, NY, USA . Alexander Schrijver. 1986. Theory of Linear and Integer Programming. John Wiley & Sons, Inc., New York, NY, USA."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.3233\/SAT190107"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48989-6_40"},{"key":"e_1_2_2_38_1","unstructured":"Alfred North Whitehead and Bertrand Russell. 1912. Principia Mathematica. University Press.  Alfred North Whitehead and Bertrand Russell. 1912. Principia Mathematica. University Press."}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158097","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3158097","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:30Z","timestamp":1750212690000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3158097"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,27]]},"references-count":37,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1145\/3158097"],"URL":"https:\/\/doi.org\/10.1145\/3158097","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,27]]},"assertion":[{"value":"2017-12-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}