Energy and mean-payoff timed games

Romain Brenguier; Franck Cassez; Jean-François Raskin

doi:10.1145/2562059.2562116

Energy and mean-payoff timed games

Romain Brenguier, Franck Cassez, Jean-François Raskin

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

14 Citations (Scopus)

Abstract

In this paper, we study energy and mean-payoff timed games. The decision problems that consist in determining the existence of winning strategies in those games are undecidable, and we thus provide semi-algorithms for solving these strategy synthesis problems. We then identify a large class of timed games for which our semi-algorithms terminate and are thus complete. We also study in detail the relation between mean-payoff and energy timed games. Finally, we provide a symbolic algorithm to solve energy timed games and demonstrate its use on small examples using HYTECH.

Original language	English
Title of host publication	Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control
Place of Publication	New York
Publisher	Association for Computing Machinery
Pages	283-292
Number of pages	10
ISBN (Print)	9781450327329
DOIs	https://doi.org/10.1145/2562059.2562116
Publication status	Published - 2014
Externally published	Yes
Event	International Conference on Hybrid Systems: Computation and Control (17th : 2014) - Berlin, Germany Duration: 15 Apr 2014 → 17 Apr 2014 Conference number: 17th

Conference

Conference	International Conference on Hybrid Systems: Computation and Control (17th : 2014)
Abbreviated title	HSCC'14
Country/Territory	Germany
City	Berlin
Period	15/04/14 → 17/04/14

Access to Document

10.1145/2562059.2562116

Cite this

@inproceedings{6da7498446f745e3bf34060af45fec15,

title = "Energy and mean-payoff timed games",

abstract = "In this paper, we study energy and mean-payoff timed games. The decision problems that consist in determining the existence of winning strategies in those games are undecidable, and we thus provide semi-algorithms for solving these strategy synthesis problems. We then identify a large class of timed games for which our semi-algorithms terminate and are thus complete. We also study in detail the relation between mean-payoff and energy timed games. Finally, we provide a symbolic algorithm to solve energy timed games and demonstrate its use on small examples using HYTECH. ",

author = "Romain Brenguier and Franck Cassez and Jean-Fran{\c c}ois Raskin",

year = "2014",

doi = "10.1145/2562059.2562116",

language = "English",

isbn = "9781450327329",

pages = "283--292",

booktitle = "Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control",

publisher = "Association for Computing Machinery",

note = "International Conference on Hybrid Systems: Computation and Control (17th : 2014), HSCC'14 ; Conference date: 15-04-2014 Through 17-04-2014",

}

Brenguier, R, Cassez, F & Raskin, J-F 2014, Energy and mean-payoff timed games. in Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control. Association for Computing Machinery, New York, pp. 283-292, International Conference on Hybrid Systems: Computation and Control (17th : 2014), Berlin, Germany, 15/04/14. https://doi.org/10.1145/2562059.2562116

Energy and mean-payoff timed games. / Brenguier, Romain; Cassez, Franck; Raskin, Jean-François.
Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control. New York: Association for Computing Machinery, 2014. p. 283-292.

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

TY - GEN

T1 - Energy and mean-payoff timed games

AU - Brenguier, Romain

AU - Cassez, Franck

AU - Raskin, Jean-François

N1 - Conference code: 17th

PY - 2014

Y1 - 2014

N2 - In this paper, we study energy and mean-payoff timed games. The decision problems that consist in determining the existence of winning strategies in those games are undecidable, and we thus provide semi-algorithms for solving these strategy synthesis problems. We then identify a large class of timed games for which our semi-algorithms terminate and are thus complete. We also study in detail the relation between mean-payoff and energy timed games. Finally, we provide a symbolic algorithm to solve energy timed games and demonstrate its use on small examples using HYTECH.

AB - In this paper, we study energy and mean-payoff timed games. The decision problems that consist in determining the existence of winning strategies in those games are undecidable, and we thus provide semi-algorithms for solving these strategy synthesis problems. We then identify a large class of timed games for which our semi-algorithms terminate and are thus complete. We also study in detail the relation between mean-payoff and energy timed games. Finally, we provide a symbolic algorithm to solve energy timed games and demonstrate its use on small examples using HYTECH.

UR - https://www.scopus.com/pages/publications/84899745197

UR - http://2014.hscc-conference.org/

U2 - 10.1145/2562059.2562116

DO - 10.1145/2562059.2562116

M3 - Conference proceeding contribution

AN - SCOPUS:84899745197

SN - 9781450327329

SP - 283

EP - 292

BT - Proceedings of the 17th International Conference on Hybrid Systems: Computation and Control

PB - Association for Computing Machinery

CY - New York

T2 - International Conference on Hybrid Systems: Computation and Control (17th : 2014)

Y2 - 15 April 2014 through 17 April 2014

ER -

Energy and mean-payoff timed games

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this