Attributes | Values |
---|
rdf:type
| |
Description
| - Zkoumáme důkazovou složitost analytických systémů důkazového systému hluboké inference SKSg (kalkulus struktur). S využitím faktu, že pravidlo řezu (i {uparrow} ) v SKSg odpovídá zavedení negace vlevo v sekventovém kalkulu, ukážeme, že %22analytický%22 systém KSg + c{uparrow} ; má v podstatě stejnou složitost jako monotónní Gentzenův kalkulus MLK. Speciálně, KSg + c{uparrow} ; kvazipolynomiálně simuluje SKSg a dovoluje polynomiální důkazy některých variant principu PHP. (cs)
- We investigate the proof complexity of analytic subsystems of the deep inference proof system SKSg (the calculus of structures). Exploiting the fact that the cut rule (i {uparrow} )of SKSg corresponds to the left rule in the sequent calculus, we establish that the %22analytic%22 system KSg + c{uparrow} has essentially the same complexity as the monotone Gentzen calculus MLK. In particular, KSg + c{uparrow} quasipolynomially simulates SKSg, and admits polynomial-size proofs of some variants of the pigeonhole principle.
- We investigate the proof complexity of analytic subsystems of the deep inference proof system SKSg (the calculus of structures). Exploiting the fact that the cut rule (i {uparrow} )of SKSg corresponds to the left rule in the sequent calculus, we establish that the %22analytic%22 system KSg + c{uparrow} has essentially the same complexity as the monotone Gentzen calculus MLK. In particular, KSg + c{uparrow} quasipolynomially simulates SKSg, and admits polynomial-size proofs of some variants of the pigeonhole principle. (en)
|
Title
| - Proof Complexity of the Cut-free Calculus of Structures
- Důkazová složitost bezřezového kalkulu struktur (cs)
- Proof Complexity of the Cut-free Calculus of Structures (en)
|
skos:prefLabel
| - Proof Complexity of the Cut-free Calculus of Structures
- Důkazová složitost bezřezového kalkulu struktur (cs)
- Proof Complexity of the Cut-free Calculus of Structures (en)
|
skos:notation
| - RIV/67985840:_____/09:00323402!RIV09-AV0-67985840
|
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| |
http://linked.open...iv/cisloPeriodika
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/67985840:_____/09:00323402
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - proof complexity; calculus of structures; monotone sequent calculus (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...odStatuVydavatele
| - GB - Spojené království Velké Británie a Severního Irska
|
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...i/riv/nazevZdroje
| - Journal of Logic and Computation
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...v/svazekPeriodika
| |
http://linked.open...iv/tvurceVysledku
| |
http://linked.open...ain/vavai/riv/wos
| |
http://linked.open...n/vavai/riv/zamer
| |
issn
| |
number of pages
| |
is http://linked.open...avai/riv/vysledek
of | |