Synthesizing robust systems
| Autor: | Karin Greimel, Thomas A. Henzinger, Roderick Bloem, Barbara Jobstmann |
|---|---|
| Rok vydání: | 2009 |
| Předmět: |
Mathematical optimization
Computational complexity theory Computer science Small number 020207 software engineering Probability density function 0102 computer and information sciences 02 engineering and technology 01 natural sciences Automaton 010201 computation theory & mathematics Robustness (computer science) Formal specification 0202 electrical engineering electronic engineering information engineering 621 Applied physics Game theory Algorithm |
| Zdroj: | FMCAD |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|