Počet záznamů: 1

Winning concurrent reachability games requires doubly-exponential patience

  1. 1.
    0336087 - MU-W 2010 RIV US eng C - Konferenční příspěvek (zahraniční konf.)
    Hansen, K.A. - Koucký, Michal - Miltersen, P.B.
    Winning concurrent reachability games requires doubly-exponential patience.
    Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LISC 2009. Los Angeles: IEEE Computer Society, 2009, s. 332-341. ISBN 978-0-7695-3746-7. ISSN 1043-6871.
    [24th Annual IEEE Symposium on Logic in Computer Science. Los Angeles (US), 11.08.2009-14.08.2009]
    Grant CEP: GA ČR GP201/07/P276; GA AV ČR IAA100190902; GA MŠk(CZ) 1M0545
    Výzkumný záměr: CEZ:AV0Z10190503
    Klíčová slova: concurrent reachability game * patience * winning strategies
    Kód oboru RIV: BA - Obecná matematika

    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.
    Trvalý link: http://hdl.handle.net/11104/0180404
    Název souboruStaženoVelikostKomentářVerzePřístup
    Koucky1.pdf1284 KBVydavatelský postprintvyžádat