Mathematical Logic Quarterly 57 (5):524-532 (2011)

Authors
Abstract
We show that the quantified propositional proof systems Gi are polynomially equivalent to their restricted versions that require all cut formulas to be prenex Σqi . Previously this was known only for the treelike systems G*i. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim
Keywords MSC (2010) 03F20  Proof complexity  prenex cuts  quantified propositional calculus
Categories (categorize this paper)
DOI 10.1002/malq.201020093
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


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

References found in this work BETA

Quantified Propositional Calculi and Fragments of Bounded Arithmetic.Jan Krajíček & Pavel Pudlák - 1990 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 36 (1):29-46.
Logical Foundations of Proof Complexity.Stephen Cook & Phuong Nguyen - 2011 - Bulletin of Symbolic Logic 17 (3):462-464.

Add more references

Citations of this work BETA

Induction rules in bounded arithmetic.Emil Jeřábek - 2020 - Archive for Mathematical Logic 59 (3-4):461-501.

Add more citations

Similar books and articles

Proofs with Monotone Cuts.Emil Jeřábek - 2012 - Mathematical Logic Quarterly 58 (3):177-187.
Examining Fragments of the Quantified Propositional Calculus.Steven Perron - 2008 - Journal of Symbolic Logic 73 (3):1051-1080.
Implicit Proofs.Jan Krajíček - 2004 - Journal of Symbolic Logic 69 (2):387 - 397.
Type Two Cuts, Bad Cuts and Very Bad Cuts.Renling Jin - 1997 - Journal of Symbolic Logic 62 (4):1241-1252.
An Approach to Infinitary Temporal Proof Theory.Stefano Baratella & Andrea Masini - 2004 - Archive for Mathematical Logic 43 (8):965-990.

Analytics

Added to PP index
2013-12-01

Total views
7 ( #988,427 of 2,385,586 )

Recent downloads (6 months)
2 ( #373,814 of 2,385,586 )

How can I increase my downloads?

Downloads

My notes