Complexity of translations from resolution to sequent calculus
- 16 January 2019
- journal article
- conference paper
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 29 (8) , 1061-1091
Abstract
Resolution and sequent calculus are two well-known formal proof systems. Their differences make them suitable for distinct tasks. Resolution and its variants are very efficient for automated reasoning and are in fact the theoretical basis of many theorem provers. However, being intentionally machine oriented, the resolution calculus is not as natural for human beings and the input problem needs to be pre-processed to clause normal form. Sequent calculus, on the other hand, is a modular formalism that is useful for analysing meta-properties of various logics and is, therefore, popular among proof theorists. The input problem does not need to be pre-processed, and proofs are more detailed. However, proofs also tend to be larger and more verbose. When the worlds of proof theory and automated theorem proving meet, translations between resolution and sequent calculus are often necessary. In this paper, we compare three translation methods and analyse their complexity.Keywords
This publication has 22 references indexed in Scilit:
- System Description: E 1.8Lecture Notes in Computer Science, 2013
- Atomic Cut Introduction by Resolution: Proof Structuring and CompressionLecture Notes in Computer Science, 2010
- Resolution is Cut-FreeJournal of Automated Reasoning, 2009
- iProver – An Instantiation-Based Theorem Prover for First-Order Logic (System Description)2008
- The Complexity of Propositional ProofsThe Bulletin of Symbolic Logic, 2007
- Short proofs are narrow—resolution made simpleJournal of the ACM, 2001
- The Inverse Method2001
- Lower bounds for increasing complexity of derivations after cut eliminationJournal of Mathematical Sciences, 1982
- Gerhard Gentzen. Investigations into logical deduction. English translation of 4422 by M. E. Szabo. American philosophical quarterly, vol. 1 (1964), pp. 288–306, and vol. 2 (1965), pp. 204–218. - Paul Bernays. Introduction. Therein, vol. 1, p. 288.The Journal of Symbolic Logic, 1970
- A Machine-Oriented Logic Based on the Resolution PrincipleJournal of the ACM, 1965