Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Optimal Strategy Synthesis in Request-Response Games
verfasst von : Florian Horn, Wolfgang Thomas, Nico Wallmeier
Erschienen in: Automated Technology for Verification and Analysis
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We show the solvability of an optimization problem on infinite two-player games. The winning conditions are of the “request-response” format,
i.e.
conjunctions of conditions of the form “if a state with property
Q
is visited, then later a state with property
P
is visited”. We ask for solutions that do not only guarantee the satisfaction of such conditions but also minimal wait times between visits to
Q
-states and subsequent visits to
P
-states. We present a natural class of valuations of infinite plays that captures this optimization problem, and with respect to this measure show the existence of an optimal winning strategy (if a winning strategy exists at all) and that it can be realized by a finite-state machine. For the latter claim we use a reduction to the solution of mean-payoff games due to Paterson and Zwick.