The New Normal: We Cannot Eliminate Cuts in Coinductive Calculi, But We Can Explore Them

Ekaterina Komendantskaya, Dmitry Rozplokhas, Henning Basold

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
26 Downloads (Pure)


In sequent calculi, cut elimination is a property that guarantees that any provable formula can be proven analytically. For example, Gentzen’s classical and intuitionistic calculi LK and LJ 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 LJ, a system we call CLJ. We derive two further practical results from this study. We show that CoLP by Gupta et al. gives rise to cut-free proofs in CLJ 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 CLJ.
Original languageEnglish
Pages (from-to)990-1005
Number of pages16
JournalTheory and Practice of Logic Programming
Issue number6
Early online date22 Sept 2020
Publication statusPublished - Nov 2020


  • Coinduction
  • Cut Elimination
  • Horn Clauses
  • Sequent Calculus
  • Theory Exploration

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics
  • Artificial Intelligence


Dive into the research topics of 'The New Normal: We Cannot Eliminate Cuts in Coinductive Calculi, But We Can Explore Them'. Together they form a unique fingerprint.

Cite this