Timed Parity Games: Complexity and Robustness

Details Timed Parity Games: Complexity and Robustness Timed Parity Games: Complexity and Robustness

Publishing date

2010-11-02

URL

arxiv.org/abs/1011.0688v2

Science

Computer Science

Field

Logic in Computer Science

Type

Scientific paper

Digital Object Identifier

10.2168/LMCS-7(4:08)2011

Abstract

We consider two-player games played in real time on game structures with clocks where the objectives of players are described using parity conditions. The games are \emph{concurrent} in that at each turn, both players independently propose a time delay and an action, and the action with the shorter delay is chosen. To prevent a player from winning by blocking time, we restrict each player to play strategies that ensure that the player cannot be responsible for causing a zeno run. First, we present an efficient reduction of these games to \emph{turn-based} (i.e., not concurrent) \emph{finite-state} (i.e., untimed) parity games. Our reduction improves the best known complexity for solving timed parity games. Moreover, the rich class of algorithms for classical parity games can now be applied to timed parity games. The states of the resulting game are based on clock regions of the original game, and the state space of the finite game is linear in the size of the region graph. Second, we consider two restricted classes of strategies for the player that represents the controller in a real-time synthesis problem, namely, \emph{limit-robust} and \emph{bounded-robust} winning strategies. Using a limit-robust winning strategy, the controller cannot choose an exact real-valued time delay but must allow for some nonzero jitter in each of its actions. If there is a given lower bound on the jitter, then the strategy is bounded-robust winning. We show that exact strategies are more powerful than limit-robust strategies, which are more powerful than bounded-robust winning strategies for any bound. For both kinds of robust strategies, we present efficient reductions to standard timed automaton games. These reductions provide algorithms for the synthesis of robust real-time controllers.

Affiliated with

Also associated with

No associations

Rating

Timed Parity Games: Complexity and Robustness does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Timed Parity Games: Complexity and Robustness, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Timed Parity Games: Complexity and Robustness will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-595973