Mathematical Logic Quarterly 58 (3):177-187 (2012)

Authors
Abstract
Atserias, Galesi, and Pudlák have shown that the monotone sequent calculus MLK quasipolynomially simulates proofs of monotone sequents in the full sequent calculus LK . We generalize the simulation to the fragment MCLK of LK which can prove arbitrary sequents, but restricts cut-formulas to be monotone. We also show that MLK as a refutation system for CNFs quasipolynomially simulates LK
Keywords monotone sequent calculus. msc (2010) 03F20  Proof complexity
Categories (categorize this paper)
DOI 10.1002/malq.201020071
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,385
Through your library

References found in this work BETA

Dual Weak Pigeonhole Principle, Boolean Complexity, and Derandomization.Emil Jeřábek - 2004 - Annals of Pure and Applied Logic 129 (1-3):1-37.
Syntactical and Semantical Properties of Simple Type Theory.Kurt Schütte - 1960 - Journal of Symbolic Logic 25 (4):305-326.
A Sorting Network in Bounded Arithmetic.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):341-355.

View all 6 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

Type Two Cuts, Bad Cuts and Very Bad Cuts.Renling Jin - 1997 - Journal of Symbolic Logic 62 (4):1241-1252.
Monotone Reducibility and the Family of Infinite Sets.Douglas Cenzer - 1984 - Journal of Symbolic Logic 49 (3):774-782.
Cardinal Invariants of Monotone and Porous Sets.Michael Hrušák & Ondřej Zindulka - 2012 - Journal of Symbolic Logic 77 (1):159-173.
Degrees of Monotone Complexity.William C. Calhoun - 2006 - Journal of Symbolic Logic 71 (4):1327 - 1341.
Monotone Majorizable Functionals.Helmut Schwichtenberg - 1999 - Studia Logica 62 (2):283-289.
Normal Derivations and Sequent Derivations.Mirjana Borisavljevi - 2008 - Journal of Philosophical Logic 37 (6):521 - 548.
Probabilistic Proofs and Transferability.Kenny Easwaran - 2009 - Philosophia Mathematica 17 (3):341-362.
Monotone Inductive Definitions in Explicit Mathematics.Michael Rathjen - 1996 - Journal of Symbolic Logic 61 (1):125-146.
Cuts in Hyperfinite Time Lines.Renling Jin - 1992 - Journal of Symbolic Logic 57 (2):522-527.
Unary Quantifiers on Finite Models.Jouko Väänänen - 1997 - Journal of Logic, Language and Information 6 (3):275-304.

Analytics

Added to PP index
2013-10-31

Total views
11 ( #779,534 of 2,362,053 )

Recent downloads (6 months)
1 ( #553,136 of 2,362,053 )

How can I increase my downloads?

Downloads

My notes