Quantified propositional logic and the number of lines of tree-like proofs

Studia Logica 64 (3):315-321 (2000)
  Copy   BIBTEX

Abstract

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.

Categories

Keywords

Reprint years

2004

DOI

10.1023/a:1005281425560

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,881

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Socratic proofs.Andrzej Wiśniewski - 2004 - Journal of Philosophical Logic 33 (3):299-326.
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.
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.
Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
Tree formulations of tense logic.Jack Copeland - manuscript
The cost of a cycle is a square.A. Carbone - 2002 - Journal of Symbolic Logic 67 (1):35-60.
Polynomial size proofs of the propositional pigeonhole principle.Samuel R. Buss - 1987 - Journal of Symbolic Logic 52 (4):916-927.
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.
Lower Bounds for Modal Logics.Pavel Hrubeš - 2007 - Journal of Symbolic Logic 72 (3):941 - 958.
Implicit Proofs.Jan Krajíček - 2004 - Journal of Symbolic Logic 69 (2):387 - 397.

Analytics

Added to PP
2009-01-28

Downloads
78 (#213,340)

6 months
6 (#520,934)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references