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

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


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.



    Upload a copy of this work     Papers currently archived: 74,310

External links

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

Through your library

Similar books and articles

Socratic Proofs.Andrzej Wiśniewski - 2004 - Journal of Philosophical Logic 33 (3):299-326.
The Cost of a Cycle is a Square.A. Carbone - 2002 - Journal of Symbolic Logic 67 (1):35-60.
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.


Added to PP

70 (#169,591)

6 months
1 (#415,900)

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

The Lengths of Proofs.Toshiyasu Arai - 2000 - Bulletin of Symbolic Logic 6 (4):473-475.

Add more references