In Egon Börger, Yuri Gurevich & Karl Meinke (eds.), Computer Science Logic. 7th Workshop, CSL '93, Swansea. Selected Papers. Berlin: Springer. pp. 33-35 (1994)

Richard Zach
University of Calgary
It is shown how the schema of equivalence can be used to obtain short proofs of tautologies A , where the depth of proofs is linear in the number of variables in A .
Keywords proof theory  proof complexity
Categories (categorize this paper)
Buy the book Find it on
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Translate to english
Revision history

Download options

PhilArchive copy

 PhilArchive page | Other versions
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Beweistheorie.[author unknown] - 1960 - Journal of Symbolic Logic 25 (3):243-249.
Some Results on Speed-Up.Tsuyoshi Yukami - 1984 - Annals of the Japan Association for Philosophy of Science 6 (4):195-205.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Algorithmic Structuring of Cut-Free Proofs.Matthias Baaz & Richard Zach - 1993 - In Egon Börger, Hans Kleine Büning, Gerhard Jäger, Simone Martini & Michael M. Richter (eds.), Computer Science Logic. CSL’92, San Miniato, Italy. Selected Papers. Berlin: Springer. pp. 29–42.
Resolution Over Linear Equations and Multilinear Proofs.Ran Raz & Iddo Tzameret - 2008 - Annals of Pure and Applied Logic 155 (3):194-224.
The Complexity of Propositional Proofs.Alasdair Urquhart - 1995 - Bulletin of Symbolic Logic 1 (4):425-467.
The Complexity of Propositional Proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.
The Depth of Resolution Proofs.Alasdair Urquhart - 2011 - Studia Logica 99 (1-3):349-364.
Generalizing Proofs in Monadic Languages.Matthias Baaz & Piotr Wojtylak - 2008 - Annals of Pure and Applied Logic 154 (2):71-138.
On Me Number of Steps in Proofs.Jan Krajíèek - 1989 - Annals of Pure and Applied Logic 41 (2):153-178.
On the Number of Steps in Proofs.Jan Kraj\mIček - 1989 - Annals of Pure and Applied Logic 41 (2):153-178.
On the Complexity of Proof Deskolemization.Matthias Baaz, Stefan Hetzl & Daniel Weller - 2012 - Journal of Symbolic Logic 77 (2):669-686.
Describing Proofs by Short Tautologies.Stefan Hetzl - 2009 - Annals of Pure and Applied Logic 159 (1-2):129-145.
Provability Logics with Quantifiers on Proofs.Rostislav E. Yavorsky - 2001 - Annals of Pure and Applied Logic 113 (1-3):373-387.


Added to PP index

Total views
207 ( #56,504 of 2,517,916 )

Recent downloads (6 months)
16 ( #50,362 of 2,517,916 )

How can I increase my downloads?


My notes