Studia Logica 64 (3):315-321 (2000)
There is an exponential speed-up in the number of lines of the quantified propositional sequent calculus over Substitution Frege Systems, if one considers proofs as trees. Whether this is true also for the number of symbols, is still an open problem.
|Keywords||Philosophy Logic Mathematical Logic and Foundations Computational Linguistics|
|Categories||categorize this paper)|
References found in this work BETA
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Decidability of Quantified Propositional Intuitionistic Logic and S4 on Trees of Height and Arity ≤Ω.Richard Zach - 2004 - Journal of Philosophical Logic 33 (2):155-164.
Polynomial Size Proofs of the Propositional Pigeonhole Principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
Bounded Arithmetic, Propositional Logic, and Complexity Theory.Jan Krajíček - 1995 - Cambridge University Press.
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate.Michael Alekhnovich, Sam Buss, Shlomo Moran & Toniann Pitassi - 2001 - Journal of Symbolic Logic 66 (1):171-191.
The Deduction Rule and Linear and Near-Linear Proof Simulations.Maria Luisa Bonet & Samuel R. Buss - 1993 - Journal of Symbolic Logic 58 (2):688-709.
Added to index2009-01-28
Total downloads34 ( #144,726 of 2,143,797 )
Recent downloads (6 months)3 ( #227,273 of 2,143,797 )
How can I increase my downloads?
There are no threads in this forum
Nothing in this forum yet.