Trading infinite memory for uniform randomness in timed games

K. Chatterjee, T.A. Henzinger, V. Prabhu, in:, Springer, 2008, pp. 87–100.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Series Title
LNCS
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 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.
Publishing Year
Date Published
2008-04-03
Acknowledgement
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.
Volume
4981
Page
87 - 100
Conference
HSCC: Hybrid Systems - Computation and Control
IST-REx-ID

Cite this

Chatterjee K, Henzinger TA, Prabhu V. Trading infinite memory for uniform randomness in timed games. In: Vol 4981. Springer; 2008:87-100. doi:10.1007/978-3-540-78929-1_7
Chatterjee, K., Henzinger, T. A., & Prabhu, V. (2008). Trading infinite memory for uniform randomness in timed games (Vol. 4981, pp. 87–100). Presented at the HSCC: Hybrid Systems - Computation and Control, Springer. https://doi.org/10.1007/978-3-540-78929-1_7
Chatterjee, Krishnendu, Thomas A Henzinger, and Vinayak Prabhu. “Trading Infinite Memory for Uniform Randomness in Timed Games,” 4981:87–100. Springer, 2008. https://doi.org/10.1007/978-3-540-78929-1_7.
K. Chatterjee, T. A. Henzinger, and V. Prabhu, “Trading infinite memory for uniform randomness in timed games,” presented at the HSCC: Hybrid Systems - Computation and Control, 2008, vol. 4981, pp. 87–100.
Chatterjee K, Henzinger TA, Prabhu V. 2008. Trading infinite memory for uniform randomness in timed games. HSCC: Hybrid Systems - Computation and Control, LNCS, vol. 4981. 87–100.
Chatterjee, Krishnendu, et al. Trading Infinite Memory for Uniform Randomness in Timed Games. Vol. 4981, Springer, 2008, pp. 87–100, doi:10.1007/978-3-540-78929-1_7.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar