Synthesis from component libraries with costs

G. Avni, O. Kupferman, Theoretical Computer Science 712 (2018) 50–72.

Download
No fulltext has been uploaded. References only!

Journal Article | Published | English
Author
;
Department
Abstract
Synthesis is the automated construction of a system from its specification. In real life, hardware and software systems are rarely constructed from scratch. Rather, a system is typically constructed from a library of components. Lustig and Vardi formalized this intuition and studied LTL synthesis from component libraries. In real life, designers seek optimal systems. In this paper we add optimality considerations to the setting. We distinguish between quality considerations (for example, size - the smaller a system is, the better it is), and pricing (for example, the payment to the company who manufactured the component). We study the problem of designing systems with minimal quality-cost and price. A key point is that while the quality cost is individual - the choices of a designer are independent of choices made by other designers that use the same library, pricing gives rise to a resource-allocation game - designers that use the same component share its price, with the share being proportional to the number of uses (a component can be used several times in a design). We study both closed and open settings, and in both we solve the problem of finding an optimal design. In a setting with multiple designers, we also study the game-theoretic problems of the induced resource-allocation game.
Publishing Year
Date Published
2018-02-15
Journal Title
Theoretical Computer Science
Volume
712
Page
50 - 72
IST-REx-ID

Cite this

Avni G, Kupferman O. Synthesis from component libraries with costs. Theoretical Computer Science. 2018;712:50-72. doi:10.1016/j.tcs.2017.11.001
Avni, G., & Kupferman, O. (2018). Synthesis from component libraries with costs. Theoretical Computer Science, 712, 50–72. https://doi.org/10.1016/j.tcs.2017.11.001
Avni, Guy, and Orna Kupferman. “Synthesis from Component Libraries with Costs.” Theoretical Computer Science 712 (2018): 50–72. https://doi.org/10.1016/j.tcs.2017.11.001.
G. Avni and O. Kupferman, “Synthesis from component libraries with costs,” Theoretical Computer Science, vol. 712, pp. 50–72, 2018.
Avni G, Kupferman O. 2018. Synthesis from component libraries with costs. Theoretical Computer Science. 712, 50–72.
Avni, Guy, and Orna Kupferman. “Synthesis from Component Libraries with Costs.” Theoretical Computer Science, vol. 712, Elsevier, 2018, pp. 50–72, doi:10.1016/j.tcs.2017.11.001.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar