A sorting network in bounded arithmetic

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F11%3A00353276" target="_blank" >RIV/67985840:_____/11:00353276 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

A sorting network in bounded arithmetic

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

A sorting network in bounded arithmetic

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2011

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Annals of Pure and Applied Logic

ISSN

0168-0072

e-ISSN

—

Svazek periodika

162

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

15

Strana od-do

—

Kód UT WoS článku

000287276800004

EID výsledku v databázi Scopus

—