Bloem, Roderick ; Greimel, Karin ; Henzinger, Thomas AIST Austria ; Jobstmann, Barbara
Many specifications include assumptions on the environment. If the environment satisfies the assumptions then a correct system reacts as intended. However, when the environment deviates from its expected behavior, a correct system can behave arbitrarily. We want to synthesize robust systems that degrade gracefully, i.e., a small number of environment failures should induce a small number of system failures. We define ratio games and show that an optimal robust system corresponds to the winning strategy of a ratio game, where the system minimizes the ratio of system errors to environment errors. We show that ratio games can be solved in pseudopolynomial time.
This research was supported in part by the Swiss National Science Foundation under the Indo-Swiss Joint Research Programme, by the European Network of Excellence on Embedded Systems Design (ArtistDesign), by the European Combest, Quasimodo, and Gasics projects, by the PAI program Moves funded by the Belgian Federal Government, and by the CFV (Federated Center in Verification) funded by the F.R.S.-FNRS.
85 - 92
FMCAD: Formal Methods in Computer-Aided Design
Bloem R, Greimel K, Henzinger TA, Jobstmann B. Synthesizing robust systems. In: Springer; 2009:85-92. doi:10.1109/FMCAD.2009.5351139
Bloem, R., Greimel, K., Henzinger, T. A., & Jobstmann, B. (2009). Synthesizing robust systems (pp. 85–92). Presented at the FMCAD: Formal Methods in Computer-Aided Design, Springer. https://doi.org/10.1109/FMCAD.2009.5351139
Bloem, Roderick, Karin Greimel, Thomas A Henzinger, and Barbara Jobstmann. “Synthesizing Robust Systems,” 85–92. Springer, 2009. https://doi.org/10.1109/FMCAD.2009.5351139.
R. Bloem, K. Greimel, T. A. Henzinger, and B. Jobstmann, “Synthesizing robust systems,” presented at the FMCAD: Formal Methods in Computer-Aided Design, 2009, pp. 85–92.
Bloem R, Greimel K, Henzinger TA, Jobstmann B. 2009. Synthesizing robust systems. FMCAD: Formal Methods in Computer-Aided Design 85–92.
Bloem, Roderick, et al. Synthesizing Robust Systems. Springer, 2009, pp. 85–92, doi:10.1109/FMCAD.2009.5351139.