Počet záznamů: 1
Winning concurrent reachability games requires doubly-exponential patience
- 1.
SYSNO ASEP 0336087 Druh ASEP C - Konferenční příspěvek (mezinárodní konf.) Zařazení RIV D - Článek ve sborníku Název Winning concurrent reachability games requires doubly-exponential patience Tvůrce(i) Hansen, K.A. (DK)
Koucký, Michal (MU-W) RID, SAI, ORCID
Miltersen, P.B. (DK)Zdroj.dok. Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LISC 2009. - Los Angeles : IEEE Computer Society, 2009 - ISSN 1043-6871 - ISBN 978-0-7695-3746-7 Rozsah stran s. 332-341 Poč.str. 10 s. Akce 24th Annual IEEE Symposium on Logic in Computer Science Datum konání 11.08.2009-14.08.2009 Místo konání Los Angeles Země US - Spojené státy americké Typ akce WRD Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova concurrent reachability game ; patience ; winning strategies Vědní obor RIV BA - Obecná matematika CEP GP201/07/P276 GA ČR - Grantová agentura ČR IAA100190902 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) Anotace We exhibit a deterministic concurrent reachability game PURGATORY_n with n non-terminal positions and a binary choice for both players in every position so that any positional strategy for Player 1 achieving the value of the game within given /epsilon <1/2 must use non-zero behavior probabilities that are less than (/epsilon^2/1-/epsilon))^{2^{n-2}}. Also, even to achieve the value within say 1 - 2^{-n/2}, doubly exponentially small behavior probabilities in the number of positions must be used. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2010
Počet záznamů: 1