On the complexity of proof deskolemization

Journal of Symbolic Logic 77 (2):669-686 (2012)

We consider the following problem: Given a proof of the Skolemization of a formula F, what is the length of the shortest proof of F? For the restriction of this question to cut-free proofs we prove corresponding exponential upper and lower bounds
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1333566645
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 47,299
Through your library

References found in this work BETA

Cut Normal Forms and Proof Complexity.Matthias Baaz & Alexander Leitsch - 1999 - Annals of Pure and Applied Logic 97 (1-3):127-177.
A Compact Representation of Proofs.Dale A. Miller - 1987 - Studia Logica 46 (4):347 - 370.

Add more references

Citations of this work BETA

Cut-Elimination: Syntax and Semantics.M. Baaz & A. Leitsch - 2014 - Studia Logica 102 (6):1217-1244.

Add more citations

Similar books and articles


Added to PP index

Total views
52 ( #172,075 of 2,290,752 )

Recent downloads (6 months)
6 ( #184,585 of 2,290,752 )

How can I increase my downloads?


My notes

Sign in to use this feature