Regularity in PDA Games Revisited
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F08%3A00026782" target="_blank" >RIV/00216224:14330/08:00026782 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Regularity in PDA Games Revisited
Original language description
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 problemwhich 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 countablegraphs and sheds more light on some open problems in this area.
Czech name
Regularita v PDA hrách ještě jednou
Czech description
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é hryna spočetných grafech a vrhá více světla na některé otevřené problémy z této oblasti.
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
MEMICS 2008 proceedings
ISBN
978-80-7355-082-0
ISSN
—
e-ISSN
—
Number of pages
8
Pages from-to
—
Publisher name
L. Matyska, D. Antoš, M. Češka, Z. Kotásek, T. Vojnar, M. Křetínský (Eds.)
Place of publication
Brno
Event location
Znojmo
Event date
Jan 1, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—