Simulating non-prenex cuts in quantified propositional calculus

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

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

Categories

Keywords

Reprint years

DOI

10.1002/malq.201020093

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,874

External links

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

Through your library

My notes

Similar books and articles

Nisan-Wigderson generators in proof systems with forms of interpolation.Ján Pich - 2011 - Mathematical Logic Quarterly 57 (4):379-383.
Notes on Craig interpolation for LJ with strong negation.Norihiro Kamide - 2011 - Mathematical Logic Quarterly 57 (4):395-399.
Spatiality and classical logic.Milena Stefanova & Silvio Valentini - 2011 - Mathematical Logic Quarterly 57 (4):432-440.
Quantified propositional calculus and a second-order theory for NC1.Stephen Cook & Tsuyoshi Morioka - 2005 - Archive for Mathematical Logic 44 (6):711-749.
Examining fragments of the quantified propositional calculus.Steven Perron - 2008 - Journal of Symbolic Logic 73 (3):1051-1080.
Powers of positive elements in C *-algebras.Hiroki Takamura - 2011 - Mathematical Logic Quarterly 57 (5):481-484.
On the correspondence between arithmetic theories and propositional proof systems – a survey.Olaf Beyersdorff - 2009 - Mathematical Logic Quarterly 55 (2):116-137.
Weak saturation of ideals on Pκ(λ).Pierre Matet - 2011 - Mathematical Logic Quarterly 57 (2):149-165.
Biprobability logic with conditional expectation.Vladimir Ristić, Radosav Đorđević & Nebojša Ikodinović - 2011 - Mathematical Logic Quarterly 57 (4):400-408.
Proofs with monotone cuts.Emil Jeřábek - 2012 - Mathematical Logic Quarterly 58 (3):177-187.

Analytics

Added to PP
2013-12-01

Downloads
20 (#1,015,924)

6 months
4 (#1,227,078)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Citations of this work

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

Add more citations

References found in this work

Bounded arithmetic, propositional logic, and complexity theory.Jan Krajíček - 1995 - New York, NY, USA: Cambridge University Press.
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