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. |
Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{794333, author = {Brožek, Václav}, address = {Brno}, booktitle = {MEMICS 2008 proceedings}, keywords = {regular languages; probabilistic pushdown games; reachability}, language = {eng}, location = {Brno}, isbn = {978-80-7355-082-0}, pages = {21-28}, publisher = {L. Matyska, D. Antoš, M. Češka, Z. Kotásek, T. Vojnar, M. Křetínský (Eds.)}, title = {Regularity in PDA Games Revisited}, url = {http://is.muni.cz/www/99081/6046298/reg_rev.pdf}, year = {2008} }
TY - JOUR ID - 794333 AU - Brožek, Václav PY - 2008 TI - Regularity in PDA Games Revisited PB - L. Matyska, D. Antoš, M. Češka, Z. Kotásek, T. Vojnar, M. Křetínský (Eds.) CY - Brno SN - 9788073550820 KW - regular languages KW - probabilistic pushdown games KW - reachability UR - http://is.muni.cz/www/99081/6046298/reg_rev.pdf N2 - 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. ER -
BROŽEK, Václav. Regularity in PDA Games Revisited. In \textit{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.
|