Počet záznamů: 1
Parity games and propositional proofs
- 1.
SYSNO ASEP 0422131 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Parity games and propositional proofs Tvůrce(i) Beckmann, A. (GB)
Pudlák, Pavel (MU-W) RID, SAI
Thapen, Neil (MU-W) RID, SAIZdroj.dok. Mathematical Foundations of Computer Science 2013. - Berlin : Springer, 2013 / Chatterjee K. ; Sgall J. - ISBN 978-3-642-40312-5 Rozsah stran s. 111-122 Poč.str. 12 s. Forma vydání Tištěná - P Akce International Symposium on Mathematical Foundations of Computer Science 2013 /38./ Datum konání 26.08.2013-30.08.2013 Místo konání Klosterneuburg Země AT - Rakousko Typ akce WRD Jazyk dok. eng - angličtina Země vyd. DE - Německo Klíč. slova resolution proof systems ; parity games ; game equivalent to resolution Vědní obor RIV BA - Obecná matematika CEP IAA100190902 GA AV ČR - Akademie věd Institucionální podpora MU-W - RVO:67985840 UT WOS 000342994500012 EID SCOPUS 84885230768 DOI 10.1007/978-3-642-40313-2_12 Anotace A propositional proof system is weakly automatizable if there is a polynomial time algorithm which separates satisfiable formulas from formulas which have a short refutation in the system, with respect to a given length bound. We show that if the resolution proof system is weakly automatizable, then parity games can be decided in polynomial time. We also define a combinatorial game and prove that resolution is weakly automatizable if and only if one can separate, by a set decidable in polynomial time, the games in which the first player has a positional winning strategy from the games in which the second player has a positional winning strategy. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2014
Počet záznamů: 1