A sorting network in bounded arithmetic

Annals of Pure and Applied Logic 162 (4):341-355 (2011)
  Copy   BIBTEX

Abstract

We formalize the construction of Paterson’s variant of the Ajtai–Komlós–Szemerédi sorting network of logarithmic depth in the bounded arithmetical theory , under the assumption of the existence of suitable expander graphs. We derive a conditional p-simulation of the propositional sequent calculus in the monotone sequent calculus

Categories

Keywords

Reprint years

DOI

10.1016/j.apal.2010.10.002

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,127

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

Expander construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
Monotone Proofs of the Pigeon Hole Principle.R. Gavalda, A. Atserias & N. Galesi - 2001 - Mathematical Logic Quarterly 47 (4):461-474.
2-Sequent calculus: a proof theory of modalities.Andrea Masini - 1992 - Annals of Pure and Applied Logic 58 (3):229-246.
On theories of bounded arithmetic for NC 1.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):322-340.
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
Proofs with monotone cuts.Emil Jeřábek - 2012 - Mathematical Logic Quarterly 58 (3):177-187.
Interpolation theorems, lower Bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
On transformations of constant depth propositional proofs.Arnold Beckmann & Sam Buss - 2019 - Annals of Pure and Applied Logic 170 (10):1176-1187.
A sequent calculus for relation algebras.Roger Maddux - 1983 - Annals of Pure and Applied Logic 25 (1):73-101.
A minimal classical sequent calculus free of structural rules.Dominic Hughes - 2010 - Annals of Pure and Applied Logic 161 (10):1244-1253.

Analytics

Added to PP
2013-10-27

Downloads
39 (#421,600)

6 months
2 (#1,259,876)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

On theories of bounded arithmetic for NC 1.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):322-340.
Expander construction in VNC1.Sam Buss, Valentine Kabanets, Antonina Kolokolova & Michal Koucký - 2020 - Annals of Pure and Applied Logic 171 (7):102796.
Proofs with monotone cuts.Emil Jeřábek - 2012 - Mathematical Logic Quarterly 58 (3):177-187.

Add more citations

References found in this work

On theories of bounded arithmetic for NC 1.Emil Jeřábek - 2011 - Annals of Pure and Applied Logic 162 (4):322-340.
Notes on polynomially bounded arithmetic.Domenico Zambella - 1996 - Journal of Symbolic Logic 61 (3):942-966.

Add more references