Regularity in PDA Games Revisited

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Název česky	Regularita v PDA hrách ještě jednou
Autoři	BROŽEK Václav
Rok publikování	2009
Druh	Článek v odborném periodiku
Časopis / Zdroj	Electronic Notes in Theoretical Computer Science
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	http://dx.doi.org/10.1016/j.entcs.2009.08.024
Obor	Informatika
Klíčová slova	regular languages; probabilistic pushdown games; reachability
Popis	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.
Související projekty:	Institut Teoretické Informatiky Vysoce paralelní a distribuované výpočetní systémy