BRÁZDIL, Tomáš, Václav BROŽEK, Antonín KUČERA a Jan OBDRŽÁLEK. Qualitative Reachability in Stochastic BPA Games. Information and Computation, Elsevier, 2011, roč. 209, č. 8, s. 1160-1183. ISSN 0890-5401.
Další formáty:   BibTeX LaTeX RIS
Základní údaje
Originální název Qualitative Reachability in Stochastic BPA Games
Autoři BRÁZDIL, Tomáš (203 Česká republika, domácí), Václav BROŽEK (276 Německo, domácí), Antonín KUČERA (203 Česká republika, garant, domácí) a Jan OBDRŽÁLEK (203 Česká republika, domácí).
Vydání Information and Computation, Elsevier, 2011, 0890-5401.
Další údaje
Originální jazyk angličtina
Typ výsledku Článek v odborném periodiku
Obor Computer sciences, information science, bioinformatics
Stát vydavatele Nizozemsko
Utajení není předmětem státního či obchodního tajemství
Impakt faktor Impact factor: 0.560
Kód RIV RIV/00216224:14330/11:00051537
Organizační jednotka Fakulta informatiky
UT WoS 000293868600002
Klíčová slova anglicky pushdown automata; turn-based games
Příznaky Mezinárodní význam, Recenzováno
Změnil Změnil: prof. RNDr. Antonín Kučera, Ph.D., učo 2508. Změněno: 15. 5. 2011 20:14.
Anotace
We consider a class of infinite-state stochastic games generated by stateless pushdown automata (or, equivalently, 1-exit recursive state machines), where the winning objective is specified by a regular set of target configurations and a qualitative probability constraint `>0' or `=1'. The goal of one player is to maximize the probability of reaching the target set so that the constraint is satisfied, while the other player aims at the opposite. We show that the winner in such games can be determined in PTIME for the `>0' constraint, and in NP intersect. coNP for the `=1' constraint. Further, we prove that the winning regions for both players are regular, and we design algorithms which compute the associated finite-state automata. Finally, we show that winning strategies can be synthesized effectively.
Anotace česky
V článku je uvažována třída nekonečně-stavových her generovaných zásobníkovými automaty bez stavové jednotky, kde je výherní kritérium specifikováno jako regulární množina cílových konfigurací a omezením tvaru `>0' nebo `=1'. Cílem jednoho hráče je maximalizovat pravděpodobnost dosažení cílové konfigurace tak, aby bylo uvedené omezení splněno, zatímco druhý hráč se snaží o opak. Je dokázáno, problém určení vítěze v takovéto hře je řešitelný v polynomiálním čase pro omezení `>0', resp. v polynomiálním čase pomocí NP int. co-NP orákula pro omezení `=1'. Dále je ukázáno, že výherní region obou hráčů je regulární, a je podán algoritmus pro syntézu výherních strategií obou hráčů.
Návaznosti
MSM0021622419, záměrNázev: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumné záměry
P202/10/1469, interní kód MUNázev: Formální metody pro analýzu a verifikaci komplexních systémů
1M0545, projekt VaVNázev: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Výzkumná centra (Národní program výzkumu)
VytisknoutZobrazeno: 17. 10. 2019 09:02