Počet záznamů: 1  

A sorting network in bounded arithmetic

  1. 1.
    0353276 - MÚ 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. E-ISSN 1873-2461
    Grant CEP: GA AV ČR IAA1019401; GA MŠMT(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
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.