Number of the records: 1
Winning concurrent reachability games requires doubly-exponential patience
- 1.
SYSNO ASEP 0336087 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper Title Winning concurrent reachability games requires doubly-exponential patience Author(s) Hansen, K.A. (DK)
Koucký, Michal (MU-W) RID, SAI, ORCID
Miltersen, P.B. (DK)Source Title 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 Pages s. 332-341 Number of pages 10 s. Action 24th Annual IEEE Symposium on Logic in Computer Science Event date 11.08.2009-14.08.2009 VEvent location Los Angeles Country US - United States Event type WRD Language eng - English Country US - United States Keywords concurrent reachability game ; patience ; winning strategies Subject RIV BA - General Mathematics R&D Projects GP201/07/P276 GA ČR - Czech Science Foundation (CSF) IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) 1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS) CEZ AV0Z10190503 - MU-W (2005-2011) Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2010
Number of the records: 1