J 2011

Qualitative Reachability in Stochastic BPA Games

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

Basic information

Original name

Qualitative Reachability in Stochastic BPA Games

Authors

BRÁZDIL, Tomáš (203 Czech Republic, belonging to the institution), Václav BROŽEK (276 Germany, belonging to the institution), Antonín KUČERA (203 Czech Republic, guarantor, belonging to the institution) and Jan OBDRŽÁLEK (203 Czech Republic, belonging to the institution)

Edition

Information and Computation, Elsevier, 2011, 0890-5401

Other information

Language

English

Type of outcome

Článek v odborném periodiku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Netherlands

Confidentiality degree

není předmětem státního či obchodního tajemství

Impact factor

Impact factor: 0.560

RIV identification code

RIV/00216224:14330/11:00051537

Organization unit

Faculty of Informatics

UT WoS

000293868600002

Keywords in English

pushdown automata; turn-based games

Tags

International impact, Reviewed
Změněno: 15/5/2011 20:14, prof. RNDr. Antonín Kučera, Ph.D.

Abstract

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.

In Czech

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áčů.

Links

MSM0021622419, plan (intention)
Name: Vysoce paralelní a distribuované výpočetní systémy
Investor: Ministry of Education, Youth and Sports of the CR, Highly Parallel and Distributed Computing Systems
P202/10/1469, interní kód MU
Name: Formální metody pro analýzu a verifikaci komplexních systémů
1M0545, research and development project
Name: Institut Teoretické Informatiky
Investor: Ministry of Education, Youth and Sports of the CR, Institute for Theoretical Computer Science