{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:52:29Z","timestamp":1764557549349,"version":"3.40.5"},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"6","license":[{"start":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T00:00:00Z","timestamp":1600732800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In sequent calculi, cut elimination is a property that guarantees that any provable formula can be proven analytically. For example, Gentzen\u2019s classical and intuitionistic calculi <jats:bold>LK<\/jats:bold> and <jats:bold>LJ<\/jats:bold> enjoy cut elimination. The property is less studied in coinductive extensions of sequent calculi. In this paper, we use coinductive Horn clause theories to show that cut is not eliminable in a coinductive extension of <jats:bold>LJ<\/jats:bold>, a system we call <jats:bold>CLJ<\/jats:bold>. We derive two further practical results from this study. We show that CoLP by Gupta et al. gives rise to cut-free proofs in <jats:bold>CLJ<\/jats:bold> with fixpoint terms, and we formulate and implement a novel method of coinductive theory exploration that provides several heuristics for discovery of cut formulae in <jats:bold>CLJ<\/jats:bold>.<\/jats:p>","DOI":"10.1017\/s1471068420000423","type":"journal-article","created":{"date-parts":[[2020,9,22]],"date-time":"2020-09-22T02:43:15Z","timestamp":1600742595000},"page":"990-1005","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":3,"title":["The New Normal: We Cannot Eliminate Cuts in Coinductive Calculi, But We Can Explore Them"],"prefix":"10.1017","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3240-0987","authenticated-orcid":false,"given":"Ekaterina","family":"Komendantskaya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dmitry","family":"Rozplokhas","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Henning","family":"Basold","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2020,9,22]]},"reference":[{"key":"S1471068420000423_ref14","unstructured":"14. Komendantskaya, E. and Li, Y. 2017. Productive corecursion in logic programming. J. TPLP (ICLP\u201917 post-proc.) 17, 5-6, 906\u2013923."},{"key":"S1471068420000423_ref18","doi-asserted-by":"crossref","unstructured":"18. Saotome, K. , Nakazawa, K. , and Kimura, D. 2020. Restriction on cut in cyclic proof system for symbolic heaps. In FLOPS\u201920.","DOI":"10.1007\/978-3-030-59025-3_6"},{"key":"S1471068420000423_ref15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139021326","volume-title":"Programming with Higher-order logic","author":"Miller","year":"2012"},{"key":"S1471068420000423_ref3","unstructured":"3. Blanchette, J. et al. 2017. Foundational nonuniform (co)datatypes for higher-order logic. In LICS\u201917. IEEE Computer Society, 1\u201312."},{"key":"S1471068420000423_ref17","unstructured":"17. Plotkin, G. D. 1970. A note on inductive generalization. Machine intelligence."},{"key":"S1471068420000423_ref5","first-page":"1177","article-title":"Sequent calculi for induction and infinite descent","volume":"6","author":"Brotherston","year":"2011","journal-title":"JLC 21"},{"year":"2007","author":"Gupta","key":"S1471068420000423_ref12"},{"volume-title":"ACM Monograph Series","year":"1979","author":"Boyer","key":"S1471068420000423_ref4"},{"key":"S1471068420000423_ref8","unstructured":"8. Endrullis, J. , Hansen, H. H. , Hendriks, D. , Polonsky, A. , and Silva, A. 2015. A coinductive framework for infinitary rewriting and equational reasoning. In RTA\u201915. 143\u2013159."},{"key":"S1471068420000423_ref16","volume-title":"Annals of Pure and Applied Logic","volume":"51","author":"Miller","year":"1991"},{"key":"S1471068420000423_ref13","first-page":"39","article-title":"Failure of cut-elimination in cyclic proofs of separation logic","author":"Kimura","year":"2020","journal-title":"Computer Software 37"},{"key":"S1471068420000423_ref19","doi-asserted-by":"crossref","first-page":"673","DOI":"10.1017\/S147106841800008X","article-title":"First-order answer set programming as constructive proof search","volume":"3","author":"Schubert","year":"2018","journal-title":"Theory Pract. Log. Program. 18,"},{"key":"S1471068420000423_ref22","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1017\/S0956796806006137","article-title":"Understanding functional dependencies via constraint handling rules","volume":"1","author":"Sulzmann","year":"2007","journal-title":"J. Funct. Program. 17"},{"key":"S1471068420000423_ref1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139032636","volume-title":"Lambda Calculus with Types","author":"Barendregt","year":"2013"},{"key":"S1471068420000423_ref11","unstructured":"11. Gentzen, G. 1969. Investigations into logical deduction. In The Collected Papers of Gerhard Gentzen, M. Szabo, Ed. Studies in Logic and the Foundations of Mathematics, vol. 55. Elsevier, 68\u2013131."},{"key":"S1471068420000423_ref7","doi-asserted-by":"crossref","unstructured":"7. Dagnino, F. , Ancona, D. , and E.Zucca. 2020. Flexible coinductive logic programming. TPLP.","DOI":"10.1017\/S147106842000023X"},{"key":"S1471068420000423_ref6","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(83)90059-2","article-title":"Fundamental properties of infinite trees","author":"Courcelle","year":"1983","journal-title":"TCS 25"},{"key":"S1471068420000423_ref2","doi-asserted-by":"crossref","unstructured":"2. Basold, H. , Komendantskaya, E. , and Li, Y. 2019. Coinduction in uniform: Foundations for corecursive proof search with horn clauses. In ESOP 2019. 783\u2013813.","DOI":"10.1007\/978-3-030-17184-1_28"},{"key":"S1471068420000423_ref23","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139168717","volume-title":"Basic Proof Theory","author":"Troelstra","year":"2000"},{"key":"S1471068420000423_ref10","unstructured":"10. Fu, P. , Komendantskaya, E. , Schrijvers, T. , and Pond, A. 2016. Proof relevant corecursive resolution. In FLOPS\u201916. Springer, 126\u2013143."},{"key":"S1471068420000423_ref9","doi-asserted-by":"crossref","unstructured":"9. Fu, P. and Komendantskaya, E. 2016. Operational semantics of resolution and productivity in Horn clause logic. Formal Aspects of Computing.","DOI":"10.1007\/s00165-016-0403-1"},{"key":"S1471068420000423_ref21","doi-asserted-by":"crossref","unstructured":"21. Sorensen, M. H. and Urzyczyn, P. 2006. Lectures on the Curry-Howard Isomorphism. Studies in Logic. Elsevier.","DOI":"10.1016\/S0049-237X(06)80005-4"},{"key":"S1471068420000423_ref20","doi-asserted-by":"crossref","unstructured":"20. Simon, L. , Mallya, A. , Bansal, A. , and Gupta, G. 2006. Coinductive logic programming. In ICLP. 330\u2013345.","DOI":"10.1007\/11799573_25"}],"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\/S1471068420000423","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,19]],"date-time":"2020-10-19T10:44:39Z","timestamp":1603104279000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068420000423\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,22]]},"references-count":23,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["S1471068420000423"],"URL":"https:\/\/doi.org\/10.1017\/s1471068420000423","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2020,9,22]]},"assertion":[{"value":"\u00a9 The Author(s), 2020. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}