Winning concurrent reachability games requires doubly-exponential patience

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F09%3A00336087" target="_blank" >RIV/67985840:_____/09:00336087 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Winning concurrent reachability games requires doubly-exponential patience

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Winning concurrent reachability games requires doubly-exponential patience

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2009

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, LISC 2009

ISBN

978-0-7695-3746-7

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

—

Název nakladatele

IEEE Computer Society

Místo vydání

Los Angeles

Místo konání akce

Los Angeles

Datum konání akce

11. 8. 2009

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—