Počet záznamů: 1
A sorting network in bounded arithmetic
- 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 souboru Staženo Velikost Komentář Verze Přístup Jerabek.pdf 1 306.7 KB Vydavatelský postprint vyžádat
Počet záznamů: 1