Towards a Clausal Analysis of Proof Schemata
David M. Cerna, Michael Lettmann · 2017
Proof schemata are a variant of LK-proofs able to simulate various induction schemes in first-order logic by adding so called links to the standard first-order LK-calculus. Links allow proofs to reference other proofs, and thus give schemata a recursive structure. Gentzen style cut-elimination methods, which reduce cuts locally, does not work in the presence of links. However, an alternative method, such as cut-elimination by resolution (CERES), which eliminate cuts globally, is able to reduce cuts over the entire recursive structure simultaneously. Unfortunately, analysis of the cut structure of a proof after partial cut-elimination is non-trivial. By extending local methods to proof schemata, we provide such an analysis.