Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950712 | Information and Computation | 2017 | 37 Pages |
Abstract
We study the beyond worst-case synthesis problem for two important quantitative settings: the mean-payoff and the shortest path. In both cases, we show how to decide the existence of finite-memory strategies satisfying the problem and how to synthesize one if one exists. We establish algorithms and we study complexity bounds and memory requirements.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Véronique Bruyère, Emmanuel Filiot, Mickael Randour, Jean-François Raskin,