Better quality in synthesis through quantitative objectives

Bloem R, Chatterjee K, Henzinger TA, Jobstmann B. 2009. Better quality in synthesis through quantitative objectives. CAV: Computer Aided Verification, LNCS, vol. 5643, 140–156.

Download (ext.)

Conference Paper | Published | English
Author
Bloem, Roderick; Chatterjee, KrishnenduISTA ; Henzinger, Thomas AISTA ; Jobstmann, Barbara
Department
Series Title
LNCS
Abstract
Most specification languages express only qualitative constraints. However, among two implementations that satisfy a given specification, one may be preferred to another. For example, if a specification asks that every request is followed by a response, one may prefer an implementation that generates responses quickly but does not generate unnecessary responses. We use quantitative properties to measure the “goodness” of an implementation. Using games with corresponding quantitative objectives, we can synthesize “optimal” implementations, which are preferred among the set of possible implementations that satisfy a given specification. In particular, we show how automata with lexicographic mean-payoff conditions can be used to express many interesting quantitative properties for reactive systems. In this framework, the synthesis of optimal implementations requires the solution of lexicographic mean-payoff games (for safety requirements), and the solution of games with both lexicographic mean-payoff and parity objectives (for liveness requirements). We present algorithms for solving both kinds of novel graph games.
Publishing Year
Date Published
2009-06-19
Publisher
Springer
Acknowledgement
This research was supported by the Swiss National Science Foundation (Indo-Swiss Research Program and NCCR MICS) and the European Union projects COMBEST and COCONUT.
Volume
5643
Page
140 - 156
Conference
CAV: Computer Aided Verification
Conference Location
Grenoble, France
Conference Date
2009-06-26 – 2009-07-02
IST-REx-ID

Cite this

Bloem R, Chatterjee K, Henzinger TA, Jobstmann B. Better quality in synthesis through quantitative objectives. In: Vol 5643. Springer; 2009:140-156. doi:10.1007/978-3-642-02658-4_14
Bloem, R., Chatterjee, K., Henzinger, T. A., & Jobstmann, B. (2009). Better quality in synthesis through quantitative objectives (Vol. 5643, pp. 140–156). Presented at the CAV: Computer Aided Verification, Grenoble, France: Springer. https://doi.org/10.1007/978-3-642-02658-4_14
Bloem, Roderick, Krishnendu Chatterjee, Thomas A Henzinger, and Barbara Jobstmann. “Better Quality in Synthesis through Quantitative Objectives,” 5643:140–56. Springer, 2009. https://doi.org/10.1007/978-3-642-02658-4_14.
R. Bloem, K. Chatterjee, T. A. Henzinger, and B. Jobstmann, “Better quality in synthesis through quantitative objectives,” presented at the CAV: Computer Aided Verification, Grenoble, France, 2009, vol. 5643, pp. 140–156.
Bloem R, Chatterjee K, Henzinger TA, Jobstmann B. 2009. Better quality in synthesis through quantitative objectives. CAV: Computer Aided Verification, LNCS, vol. 5643, 140–156.
Bloem, Roderick, et al. Better Quality in Synthesis through Quantitative Objectives. Vol. 5643, Springer, 2009, pp. 140–56, doi:10.1007/978-3-642-02658-4_14.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 0904.2638

Search this title in

Google Scholar