This is the first book on cut-elimination in first-order predicate logic from an algorithmic point of view. Instead of just proving the existence of cut-free proofs, it focuses on the algorithmic methods transforming proofs with arbitrary cuts to proofs with only atomic cuts (atomic cut normal forms, so-called ACNFs). The first part investigates traditional reductive methods from the point of view of proof rewriting. Within this general framework, generalizations of Gentzen's and Sch\"utte-Tait's cut-elimination methods are defined and shown terminating with ACNFs of the original proof. Moreover, a complexity theoretic comparison of Gentzen's and Tait's methods is given.
The core of the book centers around the cut-elimination method CERES (cut elimination by resolution) developed by the authors. CERES is based on the resolution calculus and radically differs from the reductive cut-elimination methods. The book shows that CERES asymptotically outperforms all reductive methods based on Gentzen's cut-reduction rules. It obtains this result by heavy use of subsumption theorems in clause logic. Moreover, several applications of CERES are given (to interpolation, complexity analysis of cut-elimination, generalization of proofs, and to the analysis of real mathematical proofs). Lastly, the book demonstrates that CERES can be extended to nonclassical logics, in particular to finitely-valued logics and to G\"odel logic.
Band 1
Fester Einband | 1997
Band 1
Kartonierter Einband (Kt) | 2010
Band 11
Fester Einband | 2001
Band 11
Kartonierter Einband (Kt) | 2010
Band 15
Fester Einband | 2002
Band 15
Kartonierter Einband (Kt) | 2002
Band 16
Kartonierter Einband (Kt) | 2012
Band 17
Fester Einband | 2003
Band 17
Kartonierter Einband (Kt) | 2010
Band 178
Fester Einband | 2025
Band 18
Kartonierter Einband (Kt) | 2013
Band 2
Kartonierter Einband (Kt) | 2012
Band 21
Kartonierter Einband (Kt) | 2010
Band 23
Fester Einband | 2005
Band 24
Fester Einband | 2005
Band 24
Kartonierter Einband (Kt) | 2010
Band 25
Kartonierter Einband (Kt) | 2010
Band 26
Fester Einband | 2008
Band 26
Kartonierter Einband (Kt) | 2010
Band 27
Kartonierter Einband (Kt) | 2010
Band 28
Kartonierter Einband (Kt) | 2010
Band 3
Fester Einband | 1998
Band 3
Kartonierter Einband (Kt) | 2010
Band 30
Kartonierter Einband (Kt) | 2012
Band 31
Kartonierter Einband (Kt) | 2013
Band 32
Kartonierter Einband (Kt) | 2013
Band 33
Kartonierter Einband (Kt) | 2013
Band 34
Kartonierter Einband (Kt) | 2013
Band 37
Fester Einband | 2013
Band 37
Kartonierter Einband (Kt) | 2016
Band 38
Kartonierter Einband (Kt) | 2016
Band 39
Kartonierter Einband (Kt) | 2016
Band 4
Fester Einband | 1998
Band 4
Kartonierter Einband (Kt) | 2001
Band 41
Fester Einband | 2014
Band 41
Kartonierter Einband (Kt) | 2016
Band 42
Kartonierter Einband (Kt) | 2016
Band 44
Fester Einband | 2015
Band 45
Kartonierter Einband (Kt) | 2018
Band 47
Fester Einband | 2018
Band 48
Fester Einband | 2018
Band 49
Fester Einband | 2018
Band 49
Kartonierter Einband (Kt) | 2019
Band 5
Kartonierter Einband (Kt) | 2012
Band 50
Fester Einband | 2019
Band 51
Fester Einband | 2019
Band 53
Kartonierter Einband (Kt) | 2021
Band 53
Fester Einband | 2020
Band 56
Fester Einband | 2020
Band 56
Kartonierter Einband (Kt) | 2021
Band 57
Kartonierter Einband (Kt) | 2022
Band 57
Fester Einband | 2021
Band 59
Fester Einband | 2022
Band 6
Fester Einband | 1999
Band 60
Kartonierter Einband (Kt) | 2023
Band 60
Fester Einband | 2023