Games, time, and probability: Graph models for system design and analysis

T.A. Henzinger, in:, Springer, 2007, pp. 103–110.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Series Title
LNCS
Abstract
Digital technology is increasingly deployed in safety-critical situations. This calls for systematic design and verification methodologies that can cope with three major sources of system complexity: concurrency, real time, and uncertainty. We advocate a two-step process: formal modeling followed by algorithmic analysis (or, “model building” followed by “model checking”). We model the concurrent components of a reactive system as potential collaborators or adversaries in a multi-player game with temporal objectives, such as system safety. The real-time aspect of embedded systems requires models that combine discrete state transitions and continuous state evolutions. Uncertainty in the environment is naturally modeled by probabilistic state changes. As a result, we obtain three orthogonal extensions of the basic state-transition graph model for reactive systems —game graphs, timed graphs, and stochastic graphs— as well as combinations thereof. In this short text, we provide a uniform exposition of the underlying definitions. For verification algorithms, we refer the reader to the literature.
Publishing Year
Date Published
2007-01-04
Acknowledgement
This research was supported in part by the Swiss National Science Foundation, and by the NSF ITR grant CCR-0225610.
Volume
4362
Page
103 - 110
Conference
SOFSEM: Current Trends in Theory and Practice of Computer Science
IST-REx-ID

Cite this

Henzinger TA. Games, time, and probability: Graph models for system design and analysis. In: Vol 4362. Springer; 2007:103-110. doi:10.1007/978-3-540-69507-3_7
Henzinger, T. A. (2007). Games, time, and probability: Graph models for system design and analysis (Vol. 4362, pp. 103–110). Presented at the SOFSEM: Current Trends in Theory and Practice of Computer Science, Springer. https://doi.org/10.1007/978-3-540-69507-3_7
Henzinger, Thomas A. “Games, Time, and Probability: Graph Models for System Design and Analysis,” 4362:103–10. Springer, 2007. https://doi.org/10.1007/978-3-540-69507-3_7.
T. A. Henzinger, “Games, time, and probability: Graph models for system design and analysis,” presented at the SOFSEM: Current Trends in Theory and Practice of Computer Science, 2007, vol. 4362, pp. 103–110.
Henzinger TA. 2007. Games, time, and probability: Graph models for system design and analysis. SOFSEM: Current Trends in Theory and Practice of Computer Science, LNCS, vol. 4362. 103–110.
Henzinger, Thomas A. Games, Time, and Probability: Graph Models for System Design and Analysis. Vol. 4362, Springer, 2007, pp. 103–10, doi:10.1007/978-3-540-69507-3_7.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar