Počet záznamů: 1

A sorting network in bounded arithmetic

  1. 1.
    0353276 - MU-W 2011 RIV NL eng J - Článek v odborném periodiku
    Jeřábek, Emil
    A sorting network in bounded arithmetic.
    Annals of Pure and Applied Logic. Roč. 162, č. 4 (2011), s. 341-355 ISSN 0168-0072
    Grant CEP: GA AV ČR IAA1019401; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: bounded arithmetic * sorting network * proof complexity * monotone sequent calculus
    Kód oboru RIV: BA - Obecná matematika
    Impakt faktor: 0.450, rok: 2011
    http://www.sciencedirect.com/science/article/pii/S0168007210001272

    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 VNC1 (an extension of VNC1), 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 MLK.
    Trvalý link: http://hdl.handle.net/11104/0192567
    Název souboruStaženoVelikostKomentářVerzePřístup
    Jerabek.pdf1306.7 KBVydavatelský postprintvyžádat