Often one has a preference order among the different systems that satisfy a given specification. Under a probabilistic assumption about the possible inputs, such a preference order is naturally expressed by a weighted automaton, which assigns to each word a value, such that a system is preferred if it generates a higher expected value. We solve the following optimal-synthesis problem: given an omega-regular specification, a Markov chain that describes the distribution of inputs, and a weighted automaton that measures how well a system satisfies the given specification tinder the given input assumption, synthesize a system that optimizes the measured value. For safety specifications and measures that are defined by mean-payoff automata, the optimal-synthesis problem amounts to finding a strategy in a Markov decision process (MDP) that is optimal for a long-run average reward objective, which can be done in polynomial time. For general omega-regular specifications, the solution rests on a new, polynomial-time algorithm for computing optimal strategies in MDPs with mean-payoff parity objectives. We present some experimental results showing optimal systems that were automatically generated in this way.
This research was supported by the European Union project COMBEST and the European Network of Excellence ArtistDesign.
380 - 395
CAV: Computer Aided Verification
Edinburgh, United Kingdom
201-07-15 – 2010-07-19
Chatterjee K, Henzinger TA, Jobstmann B, Singh R. Measuring and synthesizing systems in probabilistic environments. In: Vol 6174. Springer; 2010:380-395. doi:10.1007/978-3-642-14295-6_34
Chatterjee, K., Henzinger, T. A., Jobstmann, B., & Singh, R. (2010). Measuring and synthesizing systems in probabilistic environments (Vol. 6174, pp. 380–395). Presented at the CAV: Computer Aided Verification, Edinburgh, United Kingdom: Springer. https://doi.org/10.1007/978-3-642-14295-6_34
Chatterjee, Krishnendu, Thomas A Henzinger, Barbara Jobstmann, and Rohit Singh. “Measuring and Synthesizing Systems in Probabilistic Environments,” 6174:380–95. Springer, 2010. https://doi.org/10.1007/978-3-642-14295-6_34.
K. Chatterjee, T. A. Henzinger, B. Jobstmann, and R. Singh, “Measuring and synthesizing systems in probabilistic environments,” presented at the CAV: Computer Aided Verification, Edinburgh, United Kingdom, 2010, vol. 6174, pp. 380–395.
Chatterjee K, Henzinger TA, Jobstmann B, Singh R. 2010. Measuring and synthesizing systems in probabilistic environments. CAV: Computer Aided Verification, LNCS, vol. 6174. 380–395.
Chatterjee, Krishnendu, et al. Measuring and Synthesizing Systems in Probabilistic Environments. Vol. 6174, Springer, 2010, pp. 380–95, doi:10.1007/978-3-642-14295-6_34.
Link(s) to Main File(s)
Material in IST: