Krishnendu Chatterjee and Thomas A. Henzinger and Vinayak Prabhu

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2008-4

January 10, 2008

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-4.pdf

We consider concurrent two-player timed automaton games with $\omega$-regular objectives specified as parity conditions. These games offer an appropriate model for the synthesis of real-time controllers. Earlier works on timed games focused on pure strategies for each player. We study, for the first time, the use of \emph{randomized} strategies in such games. While pure (i.e., nonrandomized) strategies in timed games require infinite memory for winning even with respect to reachability objectives, we show that randomized strategies can win with finite memory with respect to all parity objectives. Also, the synthesized randomized real-time controllers are much simpler in structure than the corresponding pure controllers, and therefore easier to implement. For safety objectives we prove the existence of pure finite-memory winning strategies. Finally, while randomization helps in simplifying the strategies required for winning timed parity games, we prove that randomization does not help in winning at more states.

---

BibTeX citation:

@techreport{Chatterjee:EECS-2008-4,
    Author= {Chatterjee, Krishnendu and Henzinger, Thomas A. and Prabhu, Vinayak},
    Title= {Trading Infinite Memory for  Uniform Randomness in Timed Games},
    Year= {2008},
    Month= {Jan},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-4.html},
    Number= {UCB/EECS-2008-4},
    Abstract= {We consider concurrent two-player timed automaton games with
$\omega$-regular objectives specified as parity conditions.
These games offer an appropriate  model for the synthesis of real-time controllers. Earlier works on timed games focused on pure strategies for each player. We study, for the first time, the use of \emph{randomized} strategies in such games.
While pure (i.e., nonrandomized) strategies in timed games
require infinite memory for winning even with respect to
reachability objectives, we show that randomized strategies can win with finite memory with respect to all parity objectives. Also, the synthesized randomized real-time controllers are much simpler in structure than the corresponding pure controllers, and therefore easier to implement. For safety objectives we prove the existence of pure finite-memory winning strategies. Finally, while randomization helps in simplifying the strategies required for winning timed parity games, we prove that randomization does not help in winning at more states.},
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu 
%A Henzinger, Thomas A. 
%A Prabhu, Vinayak 
%T Trading Infinite Memory for  Uniform Randomness in Timed Games
%I EECS Department, University of California, Berkeley
%D 2008
%8 January 10
%@ UCB/EECS-2008-4
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-4.html
%F Chatterjee:EECS-2008-4