Počet záznamů: 1
A sorting network in bounded arithmetic
- 1.
SYSNO ASEP 0353276 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název A sorting network in bounded arithmetic Tvůrce(i) Jeřábek, Emil (MU-W) RID, SAI, ORCID Zdroj.dok. Annals of Pure and Applied Logic. - : Elsevier - ISSN 0168-0072
Roč. 162, č. 4 (2011), s. 341-355Poč.str. 15 s. Jazyk dok. eng - angličtina Země vyd. NL - Nizozemsko Klíč. slova bounded arithmetic ; sorting network ; proof complexity ; monotone sequent calculus Vědní obor RIV BA - Obecná matematika CEP IAA1019401 GA AV ČR - Akademie věd 1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy CEZ AV0Z10190503 - MU-W (2005-2011) UT WOS 000287276800004 EID SCOPUS 78650262884 DOI 10.1016/j.apal.2010.10.002 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2011
Počet záznamů: 1