Publication details
Approximating the Termination Value of One-Counter MDPs and Stochastic Games
Authors | |
---|---|
Year of publication | 2011 |
Type | Article in Proceedings |
Conference | Proceedings of 38th International Colloquium on Automata, Languages and Programming (ICALP 2011) |
MU Faculty or unit | |
Citation | |
Field | Informatics |
Keywords | stochastic games; one-counter automata |
Description | We show that all quantitative approximation problems for the termination value for one-counter MDPs and one-counter stochastic games are computable. Specifically, given a one-counter game, and given e > 0, we can compute a value v that approximates the value of the termination game within additive error e, and furthermore we can compute e-optimal strategies for both players in the game. |
Related projects: |