Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Trading Infinite Memory for Uniform Randomness in Timed Games

Krishnendu ChatterjeeContact Information, Thomas A. Henzinger1, 2 Contact Information and Vinayak S. PrabhuContact Information

(1)  EECS, UC Berkeley,  
(2)  CCS, EPFL,  
Abstract
We consider concurrent two-player timed automaton games with ω-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 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.
This research was supported in part by the NSF grants CCR-0208875, CCR-0225610, CCR-0234690, by the Swiss National Science Foundation, and by the Artist2 European Network of Excellence.

Contact Information Krishnendu Chatterjee
Email: c_krish@eecs.berkeley.edu

Contact Information Thomas A. Henzinger
Email: tah@epfl.ch

Contact Information Vinayak S. Prabhu
Email: vinayak@eecs.berkeley.edu
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.111 • Server: mpweb16
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)