License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2018.28
URN: urn:nbn:de:0030-drops-99277
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9927/
Go to the corresponding LIPIcs Volume Portal

Busatto-Gaston, Damien ; Monmege, Benjamin ; Reynier, Pierre-Alain

Symbolic Approximation of Weighted Timed Games

pdf-format:
LIPIcs-FSTTCS-2018-28.pdf (0.5 MB)

Abstract

Weighted timed games are zero-sum games played by two players on a timed automaton equipped with weights, where one player wants to minimise the accumulated weight while reaching a target. Weighted timed games are notoriously difficult and quickly undecidable, even when restricted to non-negative weights. For non-negative weights, the largest class that can be analysed has been introduced by Bouyer, Jaziri and Markey in 2015. Though the value problem is undecidable, the authors show how to approximate the value by considering regions with a refined granularity. In this work, we extend this class to incorporate negative weights, allowing one to model energy for instance, and prove that the value can still be approximated, with the same complexity. In addition, we show that a symbolic algorithm, relying on the paradigm of value iteration, can be used as an approximation schema on this class.

BibTeX - Entry

@InProceedings{busattogaston_et_al:LIPIcs:2018:9927,
  author =	{Damien Busatto-Gaston and Benjamin Monmege and Pierre-Alain Reynier},
  title =	{{Symbolic Approximation of Weighted Timed Games}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9927},
  URN =		{urn:nbn:de:0030-drops-99277},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.28},
  annote =	{Keywords: Weighted timed games, Real-time systems, Game theory, Approximation}
}

Keywords: Weighted timed games, Real-time systems, Game theory, Approximation
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI