About: A sorting network in bounded arithmetic

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: A sorting network in bounded arithmetic Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	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. 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. (en)
Title	A sorting network in bounded arithmetic A sorting network in bounded arithmetic (en)
skos:prefLabel	A sorting network in bounded arithmetic A sorting network in bounded arithmetic (en)
skos:notation	RIV/67985840:_____/11:00353276!RIV11-MSM-67985840
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), P(IAA1019401), Z(AV0Z10190503)
http://linked.open...iv/cisloPeriodika	4
http://linked.open...vai/riv/dodaniDat	2011
http://linked.open...aciTvurceVysledku	Jeřábek, Emil
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Matematický ústav AV ČR, v. v. i.
http://linked.open...dnocenehoVysledku	184164
http://linked.open...ai/riv/idVysledku	RIV/67985840:_____/11:00353276
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	bounded arithmetic; sorting network; proof complexity; monotone sequent calculus (en)
http://linked.open.../riv/klicoveSlovo	bounded arithmetic monotone sequent calculus proof complexity sorting network
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[C77EC7840DC4]
http://linked.open...i/riv/nazevZdroje	Annals of Pure and Applied Logic
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	1 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science Theories, proofs and computational complexity
http://linked.open...UplatneniVysledku	2011
http://linked.open...v/svazekPeriodika	162
http://linked.open...iv/tvurceVysledku	Jeřábek, Emil
http://linked.open...ain/vavai/riv/wos	000287276800004
http://linked.open...n/vavai/riv/zamer	Rozvoj a prohloubení obecných matematických poznatků a jejich užití v dalších vědních oborech a v praxi
issn	0168-0072
number of pages	15 (xsd:int)

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 67 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software