{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:21:54Z","timestamp":1751660514732,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2016,5,9]],"date-time":"2016-05-09T00:00:00Z","timestamp":1462752000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["NI 491\/14-1"],"award-info":[{"award-number":["NI 491\/14-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Autom Reasoning"],"published-print":{"date-parts":[[2017,3]]},"DOI":"10.1007\/s10817-016-9372-6","type":"journal-article","created":{"date-parts":[[2016,5,9]],"date-time":"2016-05-09T02:00:56Z","timestamp":1462759256000},"page":"341-362","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["A Decision Procedure for (Co)datatypes in SMT Solvers"],"prefix":"10.1007","volume":"58","author":[{"given":"Andrew","family":"Reynolds","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jasmin Christian","family":"Blanchette","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,5,9]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Barrett, C., Conway, C.L., Deters, M., Hadarean, L., Jovanovi\u0107, D., King, T., Reynolds, A., Tinelli, C.: CVC4. In: Gopalakrishnan, G.,\u00a0Qadeer, S. (eds.) CAV \u201911, LNCS, vol. 6806, pp. 171\u2013177. Springer (2011)","key":"9372_CR1","DOI":"10.1007\/978-3-642-22110-1_14"},{"unstructured":"Barrett, C., Fontaine, P., Tinelli, C.: The SMT-LIB standard: version 2.5. Technical report, University of Iowa (2015). http:\/\/smt-lib.org\/","key":"9372_CR2"},{"key":"9372_CR3","first-page":"21","volume":"3","author":"C Barrett","year":"2007","unstructured":"Barrett, C., Shikanian, I., Tinelli, C.: An abstract decision procedure for satisfiability in the theory of inductive data types. J. Satisf. Boolean Model. Comput. 3, 21\u201346 (2007)","journal-title":"J. Satisf. Boolean Model. Comput."},{"unstructured":"Bj\u00f8rner, N.S.: Integrating decision procedures for temporal verification. Ph.D. thesis, Stanford University (1998)","key":"9372_CR4"},{"issue":"1","key":"9372_CR5","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1007\/s10817-013-9278-5","volume":"51","author":"JC Blanchette","year":"2013","unstructured":"Blanchette, J.C., B\u00f6hme, S., Paulson, L.C.: Extending Sledgehammer with SMT solvers. J. Autom. Reason. 51(1), 109\u2013128 (2013)","journal-title":"J. Autom. Reason."},{"doi-asserted-by":"crossref","unstructured":"Blanchette, J.C., H\u00f6lzl, J., Lochbihler, A., Panny, L., Popescu, A., Traytel, D.: Truly modular (co)datatypes for Isabelle\/HOL. In: Klein, G., Gamboa, R. (eds.) ITP 2014, LNCS, vol. 8558, pp. 93\u2013110. Springer (2014)","key":"9372_CR6","DOI":"10.1007\/978-3-319-08970-6_7"},{"doi-asserted-by":"crossref","unstructured":"Blanchette, J.C., Nipkow, T.: Nitpick: a counterexample generator for higher-order logic based on a relational model finder. In: Kaufmann, M., Paulson, L.C. (eds.) ITP 2010, LNCS, vol. 6172, pp. 131\u2013146. Springer (2010)","key":"9372_CR7","DOI":"10.1007\/978-3-642-14052-5_11"},{"doi-asserted-by":"crossref","unstructured":"Blanchette, J.C., Paskevich, A.: TFF1: the TPTP typed first-order form with rank-1 polymorphism. In: Bonacina, M.P. (ed.) CADE-24, LNCS, vol. 7898, pp. 414\u2013420. Springer (2013)","key":"9372_CR8","DOI":"10.1007\/978-3-642-38574-2_29"},{"doi-asserted-by":"crossref","unstructured":"Blanchette, J.C., Popescu, A., Traytel, D.: Witnessing (co)datatypes. In: Vitek, J. (ed.) ESOP 2015, LNCS, vol. 9032, pp. 359\u2013382. Springer (2015)","key":"9372_CR9","DOI":"10.1007\/978-3-662-46669-8_15"},{"doi-asserted-by":"crossref","unstructured":"Carayol, A., Morvan, C.: On rational trees. In: \u00c9sik, Z. (ed.) CSL 2006, LNCS, vol. 4207, pp. 225\u2013239. Springer (2006)","key":"9372_CR10","DOI":"10.1007\/11874683_15"},{"unstructured":"Cruanes, S.: Extending superposition with integer arithmetic, structural induction, and beyond. Ph.D. thesis, \u00c9cole polytechnique (2015). https:\/\/who.rocq.inria.fr\/Simon.Cruanes\/files\/thesis","key":"9372_CR11"},{"doi-asserted-by":"crossref","unstructured":"de\u00a0Moura, L., Bj\u00f8rner, N.: Efficient E-matching for SMT solvers. In: Pfenning, F. (ed.) CADE-21, LNCS, vol. 4603, pp. 183\u2013198. Springer (2007)","key":"9372_CR12","DOI":"10.1007\/978-3-540-73595-3_13"},{"doi-asserted-by":"crossref","unstructured":"de\u00a0Moura, L., Bj\u00f8rner, N.: Z3: an efficient SMT solver. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008, LNCS, vol. 4963, pp. 337\u2013340. Springer (2008)","key":"9372_CR13","DOI":"10.1007\/978-3-540-78800-3_24"},{"issue":"4","key":"9372_CR14","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1017\/S1471068407003171","volume":"8","author":"K Djelloul","year":"2008","unstructured":"Djelloul, K., Dao, T., Fr\u00fchwirth, T.W.: Theory of finite or infinite trees revisited. Theory Pract. Logic Program. 8(4), 431\u2013489 (2008)","journal-title":"Theory Pract. Logic Program."},{"issue":"28","key":"9372_CR15","doi-asserted-by":"crossref","first-page":"3175","DOI":"10.1016\/j.tcs.2011.04.011","volume":"412","author":"J Endrullis","year":"2011","unstructured":"Endrullis, J., Grabmayer, C., Klop, J.W., van Oostrom, V.: On equal $$\\mu $$ \u03bc -terms. Theor. Comput. Sci. 412(28), 3175\u20133202 (2011)","journal-title":"Theor. Comput. Sci."},{"unstructured":"Gammie, P., Lochbihler, A.: The Stern\u2013Brocot tree. Archive of Formal Proofs (2016). http:\/\/afp.sf.net\/entries\/Stern_Brocot.shtml , Formal proof development","key":"9372_CR16"},{"doi-asserted-by":"crossref","unstructured":"Ganzinger, H., Hagen, G., Nieuwenhuis, R., Oliveras, A., Tinelli, C.: DPLL( $$T$$ T ): fast decision procedures. In: Alur, R., Peled, D. (eds.) CAV \u201904, LNCS, vol. 3114, pp. 175\u2013188. Springer (2004)","key":"9372_CR17","DOI":"10.1007\/978-3-540-27813-9_14"},{"doi-asserted-by":"crossref","unstructured":"Ge, Y., de\u00a0Moura, L.: Complete instantiation for quantified formulas in satisfiability modulo theories. In: CAV \u201909, LNCS, vol. 5643, pp. 306\u2013320. Springer (2009)","key":"9372_CR18","DOI":"10.1007\/978-3-642-02658-4_25"},{"doi-asserted-by":"crossref","unstructured":"Gunter, E.L.: Why we can\u2019t have SML-style datatype declarations in HOL. In: Claesen, L.J.M., Gordon, M.J.C. (eds.) TPHOLs \u201992, IFIP Transactions, vol. A-20, pp. 561\u2013568. North-Holland\/Elsevier (1993)","key":"9372_CR19","DOI":"10.1016\/B978-0-444-89880-7.50042-5"},{"key":"9372_CR20","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/B978-0-12-417750-5.50022-1","volume-title":"Theory of Machines and Computations","author":"J Hopcroft","year":"1971","unstructured":"Hopcroft, J.: An $$n \\log n$$ n log n algorithm for minimizing states in a finite automaton. In: Kohavi, Z., Paz, A. (eds.) Theory of Machines and Computations, pp. 189\u2013196. Academic Press, London (1971)"},{"doi-asserted-by":"crossref","unstructured":"Jovanovi\u0107, D., Barrett, C.: Sharing is caring: combination of theories. In: Tinelli, C., Sofronie-Stokkermans, V. (eds.) FroCoS 2011, LNCS, vol. 6989, pp. 195\u2013210. Springer (2011)","key":"9372_CR21","DOI":"10.1007\/978-3-642-24364-6_14"},{"doi-asserted-by":"crossref","unstructured":"Kersani, A., Peltier, N.: Combining superposition and induction: a practical realization. In: Fontaine, P., Ringeissen, C., Schmidt, R.A. (eds.) FroCoS 2013, LNCS, vol. 8152, pp. 7\u201322. Springer (2013)","key":"9372_CR22","DOI":"10.1007\/978-3-642-40885-4_2"},{"unstructured":"Klein, G., Nipkow, T., Paulson, L. (eds.): Archive of Formal Proofs. http:\/\/afp.sf.net\/","key":"9372_CR23"},{"key":"9372_CR24","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"D Kozen","year":"1983","unstructured":"Kozen, D.: Results on the propositional $$\\mu $$ \u03bc -calculus. Theor. Comput. Sci. 27, 333\u2013354 (1983)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Leino, K.R.M., Moskal, M.: Co-induction simply\u2014automatic co-inductive proofs in a program verifier. In: Jones, C.B., Pihlajasaari, P., Sun, J. (eds.) FM 2014, LNCS, vol. 8442, pp. 382\u2013398. Springer (2014)","key":"9372_CR25","DOI":"10.1007\/978-3-319-06410-9_27"},{"issue":"4","key":"9372_CR26","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1007\/s10817-009-9155-4","volume":"43","author":"X Leroy","year":"2009","unstructured":"Leroy, X.: A formally verified compiler back-end. J. Autom. Reason. 43(4), 363\u2013446 (2009)","journal-title":"J. Autom. Reason."},{"doi-asserted-by":"crossref","unstructured":"Lochbihler, A.: Verifying a compiler for Java threads. In: Gordon, A.D. (ed.) ESOP\u00a02010, LNCS, vol. 6012, pp. 427\u2013447. Springer (2010)","key":"9372_CR27","DOI":"10.1007\/978-3-642-11957-6_23"},{"issue":"4","key":"9372_CR28","first-page":"12:1","volume":"35","author":"A Lochbihler","year":"2014","unstructured":"Lochbihler, A.: Making the Java memory model safe. ACM Trans. Program. Lang. Syst. 35(4), 12:1\u201365 (2014)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"2","key":"9372_CR29","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/357073.357079","volume":"1","author":"G Nelson","year":"1979","unstructured":"Nelson, G., Oppen, D.C.: Simplification by cooperating decision procedures. ACM Trans. Program. Lang. Syst. 1(2), 245\u2013257 (1979)","journal-title":"ACM Trans. Program. Lang. Syst."},{"doi-asserted-by":"crossref","unstructured":"Nipkow, T., Paulson, L.C., Wenzel, M.: Isabelle\/HOL: a\u00a0proof assistant for higher-order logic, LNCS, vol. 2283. Springer (2002)","key":"9372_CR30","DOI":"10.1007\/3-540-45949-9"},{"doi-asserted-by":"crossref","unstructured":"Pham, T., Whalen, M.W.: RADA: a tool for reasoning about algebraic data types with abstractions. In: Meyer, B., Baresi, L., Mezini, M. (eds.) ESEC\/FSE \u201913, pp. 611\u2013614. ACM (2013)","key":"9372_CR31","DOI":"10.1145\/2491411.2494597"},{"doi-asserted-by":"crossref","unstructured":"Reynolds, A., Blanchette, J.C.: A decision procedure for (co)datatypes in SMT solvers. In: Felty, A., Middeldorp, A. (eds.) CADE-25, LNCS, vol. 9195, pp. 197\u2013213. Springer (2015)","key":"9372_CR32","DOI":"10.1007\/978-3-319-21401-6_13"},{"doi-asserted-by":"crossref","unstructured":"Reynolds, A., Blanchette, J.C., Tinelli, C.: Model finding for recursive functions in SMT. In: Ganesh, V., Jovanovi\u0107, D. (eds.) SMT 2015 (2015)","key":"9372_CR33","DOI":"10.1007\/978-3-319-40229-1_10"},{"doi-asserted-by":"crossref","unstructured":"Reynolds, A., Kuncak, V.: Induction for SMT solvers. In: D\u2019Souza, D., Lal, A., Larsen, K.G. (eds.) VMCAI 2015, LNCS, vol. 8931, pp. 80\u201398. Springer (2014)","key":"9372_CR34","DOI":"10.1007\/978-3-662-46081-8_5"},{"doi-asserted-by":"crossref","unstructured":"Reynolds, A., Tinelli, C., Goel, A., Krsti\u0107, S., Deters, M., Barrett, C.: Quantifier instantiation techniques for finite model finding in SMT. In: Bonacina, M.P. (ed.) CADE-24, LNCS, vol. 7898, pp. 377\u2013391. Springer (2013)","key":"9372_CR35","DOI":"10.1007\/978-3-642-38574-2_26"},{"doi-asserted-by":"crossref","unstructured":"Reynolds, A., Tinelli, C., de\u00a0Moura, L.: Finding conflicting instances of quantified formulas in SMT. In: FMCAD 2014, pp. 195\u2013202. IEEE (2014)","key":"9372_CR36","DOI":"10.1109\/FMCAD.2014.6987613"},{"key":"9372_CR37","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/S0304-3975(00)00056-6","volume":"249","author":"JJMM Rutten","year":"2000","unstructured":"Rutten, J.J.M.M.: Universal coalgebra\u2014a theory of systems. Theor. Comput. Sci. 249, 3\u201380 (2000)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Stump, A., Sutcliffe, G., Tinelli, C.: StarExec: a cross-community infrastructure for logic solving. In: Demri, S., Kapur, D., Weidenbach, C. (eds.) IJCAR 2014, LNCS, vol. 8562, pp. 367\u2013373. Springer (2014)","key":"9372_CR38","DOI":"10.1007\/978-3-319-08587-6_28"},{"doi-asserted-by":"crossref","unstructured":"Suter, P., K\u00f6ksal, A.S., Kuncak, V.: Satisfiability modulo recursive programs. In: Yahav, E. (ed.) SAS 2011, LNCS, vol. 6887, pp. 298\u2013315. Springer (2011)","key":"9372_CR39","DOI":"10.1007\/978-3-642-23702-7_23"},{"issue":"3","key":"9372_CR40","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s10817-005-5204-9","volume":"34","author":"C Tinelli","year":"2005","unstructured":"Tinelli, C., Zarba, C.G.: Combining nonstably infinite theories. J. Autom. Reason. 34(3), 209\u2013238 (2005)","journal-title":"J. Autom. Reason."},{"unstructured":"Wand, D.: Polymorphic+typeclass superposition. In: de\u00a0Moura, L., Konev, B., Schulz, S. (eds.) PAAR 2014 (2014)","key":"9372_CR41"},{"unstructured":"Weber, T.: SAT-based finite model generation for higher-order logic. Ph.D. thesis, Technische Universit\u00e4t M\u00fcnchen (2008). http:\/\/mediatum.ub.tum.de\/doc\/676608\/file","key":"9372_CR42"}],"container-title":["Journal of Automated Reasoning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10817-016-9372-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10817-016-9372-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10817-016-9372-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10817-016-9372-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,7]],"date-time":"2019-09-07T08:17:01Z","timestamp":1567844221000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10817-016-9372-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,9]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,3]]}},"alternative-id":["9372"],"URL":"https:\/\/doi.org\/10.1007\/s10817-016-9372-6","relation":{},"ISSN":["0168-7433","1573-0670"],"issn-type":[{"type":"print","value":"0168-7433"},{"type":"electronic","value":"1573-0670"}],"subject":[],"published":{"date-parts":[[2016,5,9]]}}}