J 2011

Qualitative Reachability in Stochastic BPA Games

BRÁZDIL, Tomáš, Václav BROŽEK, Antonín KUČERA a Jan OBDRŽÁLEK

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

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Nizozemské království

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ěněno: 15. 5. 2011 20:14, prof. RNDr. Antonín Kučera, Ph.D.

Anotace

ORIG CZ

V originále

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.

Č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ěr
Název: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy
P202/10/1469, interní kód MU
Název: Formální metody pro analýzu a verifikaci komplexních systémů
1M0545, projekt VaV
Název: Institut Teoretické Informatiky
Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky