Efficient controller synthesis for consumption games with multiple resource types

B. Brázdil, K. Chatterjee, A. Kučera, P. Novotny, in:, Springer, 2012, pp. 23–38.


Conference Paper | Published | English
Author
; ; ;
Department
Series Title
LNCS
Abstract
We introduce consumption games, a model for discrete interactive system with multiple resources that are consumed or reloaded independently. More precisely, a consumption game is a finite-state graph where each transition is labeled by a vector of resource updates, where every update is a non-positive number or ω. The ω updates model the reloading of a given resource. Each vertex belongs either to player □ or player ◇, where the aim of player □ is to play so that the resources are never exhausted. We consider several natural algorithmic problems about consumption games, and show that although these problems are computationally hard in general, they are solvable in polynomial time for every fixed number of resource types (i.e., the dimension of the update vectors) and bounded resource updates.
Publishing Year
Date Published
2012-07-01
Acknowledgement
Tomas Brazdil, Antonin Kucera, and Petr Novotny are supported by the Czech Science Foundation, grant No. P202/10/1469. Krishnendu Chatterjee is supported by the FWF (Austrian Science Fund) NFN Grant No S11407-N23 (RiSE) and ERC Start grant (279307: Graph Games).
Volume
7358
Page
23 - 38
Conference
CAV: Computer Aided Verification
Conference Location
Berkeley, CA, USA
Conference Date
2012-07-07 – 2012-07-13
IST-REx-ID

Cite this

Brázdil B, Chatterjee K, Kučera A, Novotny P. Efficient controller synthesis for consumption games with multiple resource types. In: Vol 7358. Springer; 2012:23-38. doi:10.1007/978-3-642-31424-7_8
Brázdil, B., Chatterjee, K., Kučera, A., & Novotny, P. (2012). Efficient controller synthesis for consumption games with multiple resource types (Vol. 7358, pp. 23–38). Presented at the CAV: Computer Aided Verification, Berkeley, CA, USA: Springer. https://doi.org/10.1007/978-3-642-31424-7_8
Brázdil, Brázdil, Krishnendu Chatterjee, Antonín Kučera, and Petr Novotny. “Efficient Controller Synthesis for Consumption Games with Multiple Resource Types,” 7358:23–38. Springer, 2012. https://doi.org/10.1007/978-3-642-31424-7_8.
B. Brázdil, K. Chatterjee, A. Kučera, and P. Novotny, “Efficient controller synthesis for consumption games with multiple resource types,” presented at the CAV: Computer Aided Verification, Berkeley, CA, USA, 2012, vol. 7358, pp. 23–38.
Brázdil B, Chatterjee K, Kučera A, Novotny P. 2012. Efficient controller synthesis for consumption games with multiple resource types. CAV: Computer Aided Verification, LNCS, vol. 7358. 23–38.
Brázdil, Brázdil, et al. Efficient Controller Synthesis for Consumption Games with Multiple Resource Types. Vol. 7358, Springer, 2012, pp. 23–38, doi:10.1007/978-3-642-31424-7_8.

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

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar