{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T08:44:24Z","timestamp":1780994664515,"version":"3.54.1"},"reference-count":35,"publisher":"Cambridge University Press (CUP)","issue":"3-4","license":[{"start":{"date-parts":[[2018,8,10]],"date-time":"2018-08-10T00:00:00Z","timestamp":1533859200000},"content-version":"unspecified","delay-in-days":40,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We address the problem of verifying the satisfiability of Constrained Horn Clauses (CHCs) based on theories of inductively defined data structures, such as lists and trees. We propose a transformation technique whose objective is the removal of these data structures from CHCs, hence reducing their satisfiability to a satisfiability problem for CHCs on integers and booleans. We propose a transformation algorithm and identify a class of clauses where it always succeeds. We also consider an extension of that algorithm, which combines clause transformation with reasoning on integer constraints. Via an experimental evaluation we show that our technique greatly improves the effectiveness of applying the Z3 solver to CHCs. We also show that our verification technique based on CHC transformation followed by CHC solving, is competitive with respect to CHC solvers extended with induction.<\/jats:p>","DOI":"10.1017\/s1471068418000157","type":"journal-article","created":{"date-parts":[[2018,8,10]],"date-time":"2018-08-10T05:44:17Z","timestamp":1533879857000},"page":"452-469","source":"Crossref","is-referenced-by-count":23,"title":["Solving Horn Clauses on Inductive Data Types Without Induction"],"prefix":"10.1017","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7319-8439","authenticated-orcid":false,"given":"EMANUELE","family":"DE ANGELIS","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1268-7829","authenticated-orcid":false,"given":"FABIO","family":"FIORAVANTI","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7858-4032","authenticated-orcid":false,"given":"ALBERTO","family":"PETTOROSSI","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3835-4931","authenticated-orcid":false,"given":"MAURIZIO","family":"PROIETTI","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2018,8,10]]},"reference":[{"key":"S1471068418000157_ref28","unstructured":"Mordvinov D. and Fedyukovich G. 2017. Synchronizing constrained Horn clauses. In Proc. of LPAR-21 EPiC Series in Computing Vol. 46. EasyChair, 338\u2013355."},{"key":"S1471068418000157_ref10","unstructured":"De Angelis E. , Fioravanti F. , Pettorossi A. , and Proietti M. 2017a. Predicate pairing for program verification. Theory and Practice of Logic Programming, 1\u201341. Published online, to appear in press (https:\/\/arxiv.org\/abs\/1708.01473)."},{"key":"S1471068418000157_ref21","doi-asserted-by":"crossref","unstructured":"Hojjat H. , Konecn\u00fd F. , Garnier F. , Iosif R. , Kuncak V. , and R\u00fcmmer P. 2012. A verification toolkit for numerical transition systems. In Proc. of FM '12, LNCS 7436. Springer, 247\u2013251.","DOI":"10.1007\/978-3-642-32759-9_21"},{"key":"S1471068418000157_ref6","doi-asserted-by":"crossref","unstructured":"Cousot P. and Halbwachs N. 1978. Automatic discovery of linear restraints among variables of a program. In Proc. of POPL '78. ACM, 84\u201396.","DOI":"10.1145\/512760.512770"},{"key":"S1471068418000157_ref9","doi-asserted-by":"crossref","unstructured":"De Angelis E. , Fioravanti F. , Pettorossi A. , and Proietti M. 2016. Relational verification through Horn clause transformation. In Proc. of SAS '16, LNCS 9837. Springer, 147\u2013169.","DOI":"10.1007\/978-3-662-53413-7_8"},{"key":"S1471068418000157_ref25","unstructured":"Leroy X. , Doligez D. , Frisch A. , Garrigue J. , R\u00e9my D. , and Vouillon J. 2017. The OCaml system, Release 4.06. INRIA, France."},{"key":"S1471068418000157_ref11","doi-asserted-by":"publisher","DOI":"10.3233\/FI-2017-1461"},{"key":"S1471068418000157_ref26","unstructured":"McMillan K. L. 2003. Interpolation and SAT-based model checking. In Proc. of CAV '03. LNCS 2725. Springer, 1\u201313."},{"key":"S1471068418000157_ref19","doi-asserted-by":"crossref","unstructured":"Grebenshchikov S. , Lopes N. P. , Popeea C. , and Rybalchenko A. 2012. Synthesizing software verifiers from proof rules. In Proc. of ACM SIGPLAN PLDI '12. 405\u2013416.","DOI":"10.1145\/2254064.2254112"},{"key":"S1471068418000157_ref23","doi-asserted-by":"crossref","unstructured":"Kafle B. , Gallagher J. P. , and Morales J. F. 2016. RAHFT: A tool for verifying Horn clauses using abstract interpretation and finite tree automata. In Proc. of CAV '16. LNCS 9779. Springer, 261\u2013268.","DOI":"10.1007\/978-3-319-41528-4_14"},{"key":"S1471068418000157_ref22","doi-asserted-by":"crossref","unstructured":"Jaffar J. , Navas J. A. , and Santosa A. E. 2012. Unbounded symbolic execution for program verification. In Proc. of RV '11. LNCS 7186. Springer, 396\u2013411.","DOI":"10.1007\/978-3-642-29860-8_32"},{"key":"S1471068418000157_ref8","doi-asserted-by":"publisher","DOI":"10.1017\/S1471068415000289"},{"key":"S1471068418000157_ref5","doi-asserted-by":"crossref","unstructured":"Clarke E. M. , Grumberg O. , Jha S. , Lu Y. , and Veith H. 2000. Counterexample-Guided Abstraction Refinement. In Proc. of CAV '00, LNCS 1855. Springer, 154\u2013169.","DOI":"10.1007\/10722167_15"},{"key":"S1471068418000157_ref33","unstructured":"Tamaki H. and Sato T. 1984. Unfold\/fold transformation of logic programs. In Proc. of ICLP '84, S.-\u00c5. T\u00e4rnlund , Ed., Uppsala University, Sweden, 127\u2013138."},{"key":"S1471068418000157_ref4","unstructured":"Bradley A. R. 2011. SAT-based model checking without unrolling. In Proc. of VMCAI '11, LNCS 6538. Springer, 70\u201387."},{"key":"S1471068418000157_ref20","doi-asserted-by":"crossref","unstructured":"Hoder K. and Bj\u00f8rner N. 2012. Generalized property directed reachability. In Proc. of SAT '12, LNCS 7317. Springer, 157\u2013171.","DOI":"10.1007\/978-3-642-31612-8_13"},{"key":"S1471068418000157_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/S0743-1066(99)00030-8"},{"key":"S1471068418000157_ref24","unstructured":"Komuravelli A. , Gurfinkel A. , Chaki S. , and Clarke E. M. 2013. Automatic abstraction in SMT-based unbounded software model checking. In Proc. of CAV '13, LNCS 8044. Springer, 846\u2013862."},{"key":"S1471068418000157_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23534-9_2"},{"key":"S1471068418000157_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90147-A"},{"key":"S1471068418000157_ref34","doi-asserted-by":"crossref","unstructured":"Unno H. , Torii S. , and Sakamoto H. 2017. Automating induction for solving Horn clauses. In Proc. of CAV '17. LNCS 10427. Springer, 571\u2013591.","DOI":"10.1007\/978-3-319-63390-9_30"},{"key":"S1471068418000157_ref1","unstructured":"Albert E. , G\u00f3mez-Zamalloa M. , Hubert L. , and Puebla G. 2007. Verification of Java bytecode using analysis and transformation of logic programs. In Proc. of PADL '07, LNCS 4354. Springer, 124\u2013139."},{"key":"S1471068418000157_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00227-A"},{"key":"S1471068418000157_ref31","doi-asserted-by":"crossref","unstructured":"Reynolds A. and Kuncak V. 2015. Induction for SMT solvers. In Proc. of VMCAI '15, LNCS 8931. Springer, 80\u201398.","DOI":"10.1007\/978-3-662-46081-8_5"},{"key":"S1471068418000157_ref18","doi-asserted-by":"crossref","unstructured":"Felsing D. , Grebing S. , Klebanov V. , R\u00fcmmer P. , and Ulbrich M. 2014. Automating regression verification. In Proc. of ACM\/IEEE Conf. ASE '14. 349\u2013360.","DOI":"10.1145\/2642937.2642987"},{"key":"S1471068418000157_ref7","doi-asserted-by":"crossref","unstructured":"De Angelis E. , Fioravanti F. , Pettorossi A. , and Proietti M. 2014. VeriMAP: A tool for verifying programs through transformations. In Proc. of TACAS '14, LNCS 8413. Springer, 568\u2013574.","DOI":"10.1007\/978-3-642-54862-8_47"},{"key":"S1471068418000157_ref12","doi-asserted-by":"crossref","unstructured":"De Angelis E. , Fioravanti F. , Pettorossi A. , and Proietti M. 2017c. Semantics-based generation of verification conditions via program specialization. Science of Computer Programming 147, 78\u2013108.","DOI":"10.1016\/j.scico.2016.11.002"},{"key":"S1471068418000157_ref13","unstructured":"de Moura L. M. and Bj\u00f8rner N. 2008. Z3: An efficient SMT solver. In Proc. of TACAS '08. LNCS 4963. Springer, 337\u2013340."},{"key":"S1471068418000157_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00148-4"},{"key":"S1471068418000157_ref15","doi-asserted-by":"crossref","unstructured":"Dixon L. and Fleuriot J. D. 2003. IsaPlanner: A prototype proof planner in Isabelle. In Proc. of CADE-19, LNCS 2741. Springer, 279\u2013283.","DOI":"10.1007\/978-3-540-45085-6_22"},{"key":"S1471068418000157_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2007.08.001"},{"key":"S1471068418000157_ref16","volume-title":"A Mathematical Introduction to Logic","author":"Enderton","year":"1972"},{"key":"S1471068418000157_ref29","doi-asserted-by":"crossref","unstructured":"Peralta J. C. , Gallagher J. P. , and Saglam H. 1998. Analysis of imperative programs through analysis of constraint logic programs. In Proc. of SAS '98, LNCS 1503. Springer, 246\u2013261.","DOI":"10.1007\/3-540-49727-7_15"},{"key":"S1471068418000157_ref32","doi-asserted-by":"crossref","unstructured":"Suter P. , K\u00f6ksal A. S. , and Kuncak V. 2011. Satisfiability modulo recursive programs. In Proc. of SAS '11, LNCS 6887. Springer, 298\u2013315.","DOI":"10.1007\/978-3-642-23702-7_23"},{"key":"S1471068418000157_ref27","unstructured":"M\u00e9ndez-Lojo M. , Navas J. A. , and Hermenegildo M. V. 2008. A flexible, (C)LP-based approach to the analysis of object-oriented programs. In Proc. of LOPSTR'07. LNCS 4915. Springer, 154\u2013168."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068418000157","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,14]],"date-time":"2019-04-14T15:19:03Z","timestamp":1555255143000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068418000157\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":35,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["S1471068418000157"],"URL":"https:\/\/doi.org\/10.1017\/s1471068418000157","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}