Regularity in PDA Games Revisited

BROŽEK, Václav. Regularity in PDA Games Revisited. In MEMICS 2008 proceedings. Brno: L. Matyska, D. Antoš, M. Češka, Z. Kotásek, T. Vojnar, M. Křetínský (Eds.), 2008, s. 21-28. ISBN 978-80-7355-082-0.

Základní údaje

Originální název

Regularity in PDA Games Revisited

Název česky

Regularita v PDA hrách ještě jednou

Autoři

BROŽEK, Václav (203 Česká republika, garant)

Vydání

Brno, MEMICS 2008 proceedings, od s. 21-28, 8 s. 2008

Nakladatel

L. Matyska, D. Antoš, M. Češka, Z. Kotásek, T. Vojnar, M. Křetínský (Eds.)

---

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Česká republika

Utajení

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

Odkazy

URL

Kód RIV

RIV/00216224:14330/08:00026782

Organizační jednotka

Fakulta informatiky

ISBN

978-80-7355-082-0

Klíčová slova anglicky

regular languages; probabilistic pushdown games; reachability

Štítky

probabilistic pushdown games, reachability, regular languages

Příznaky

Mezinárodní význam, Recenzováno

---

Anotace

V originále

We study the regularity of sets of winning configurations in countable-state stochastic games played on transition graphs of pushdown automata (PDA games) with reachability objectives. Our main result is proving the regularity of the sets of winning configurations for qualitative reachability objectives. This completes the classification partially given in a previous paper on this topic. We also improve the upper bounds on the regular representation in cases already solved. We further mention a problem which has also been studied recently: determining the \emph{value} of a reachability game. Using our methods we prove the regularity of the set of configurations with value 1 and 0. Our work is related to recent results for stochastic games on countable graphs and sheds more light on some open problems in this area.

Česky

Věnujeme se regularitě výherních množin v PDA hrách s dosažitelností. Hlavním výsledkem je důkaz regularity pro kvalitativní kritéria. To zúplňuje klasifikaci z předchozího článku na toto téma. Rovněž jsme vylepšili horní odhad na velikost reprezentace těchto množin u případů, které jsou již vyřešeny. Dále zmiňujeme problém studvaný v poslední době: počítání hodnoty hry. Pomocí našich metod dokazujeme regularitu množin konfigurací s hodnotou 0 a 1. Práce souvisí s nedávnými výsledky pro stochastické hry na spočetných grafech a vrhá více světla na některé otevřené problémy z této oblasti.

---

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
1M0545, projekt VaV	Název: Institut Teoretické Informatiky Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky