---
res:
bibo_abstract:
- '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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Chatterjee, Krishnendu
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Henzinger, Thomas A
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
- foaf_Person:
foaf_givenName: Barbara
foaf_name: Jobstmann, Barbara
foaf_surname: Jobstmann
- foaf_Person:
foaf_givenName: Rohit
foaf_name: Singh, Rohit
foaf_surname: Singh
bibo_doi: 10.1007/978-3-642-14295-6_34
bibo_volume: 6174
dct_date: 2010^xs_gYear
dct_language: eng
dct_publisher: Springer@
dct_title: Measuring and synthesizing systems in probabilistic environments@
...