On transformations of constant depth propositional proofs

Annals of Pure and Applied Logic 170 (10):1176-1187 (2019)
  Copy   BIBTEX

Abstract

This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier paper about transformations from proofs with polylogarithmic height and constantly many formulas per cedent.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,400

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

The three dimensions of proofs.Yves Guiraud - 2006 - Annals of Pure and Applied Logic 141 (1):266-295.
A note on propositional proof complexity of some Ramsey-type statements.Jan Krajíček - 2011 - Archive for Mathematical Logic 50 (1-2):245-255.
Matrix identities and the pigeonhole principle.Michael Soltys & Alasdair Urquhart - 2004 - Archive for Mathematical Logic 43 (3):351-357.
The Depth of Resolution Proofs.Alasdair Urquhart - 2011 - Studia Logica 99 (1-3):349-364.
Propositional consistency proofs.Samuel R. Buss - 1991 - Annals of Pure and Applied Logic 52 (1-2):3-29.
Simplified Lower Bounds for Propositional Proofs.Alasdair Urquhart & Xudong Fu - 1996 - Notre Dame Journal of Formal Logic 37 (4):523-544.
The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
The complexity of propositional proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
Some remarks on lengths of propositional proofs.Samuel R. Buss - 1995 - Archive for Mathematical Logic 34 (6):377-394.

Analytics

Added to PP
2019-05-17

Downloads
16 (#670,075)

6 months
1 (#452,962)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations