Regularity in PDA Games Revisited

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F09%3A00043830" target="_blank" >RIV/00216224:14330/09:00043830 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

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
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

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)

Publication year
2009
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)