Ebook: Methods of cut-elimination

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. M.  Read more...
1. Preface --
2. Introduction --
3. Preliminaries --
4. Complexity of cut-elimination --
5. Reduction and elimination --
6. Cut-elimination by resolution --
7. Extensions of CERES --
8. Applications of CERES --
9. CERES in nonclassical logics --
10. Related research.