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.2014.379
URN: urn:nbn:de:0030-drops-48571
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4857/
Go to the corresponding LIPIcs Volume Portal

Colcombet, Thomas ; Fijalkow, Nathanael ; Horn, Florian

Playing Safe

pdf-format:
33.pdf (0.4 MB)

Abstract

We consider two-player games over graphs and give tight bounds on the memory size of strategies ensuring safety conditions. More specifically, we show that the minimal number of memory states of a strategy ensuring a safety condition is given by the size of the maximal antichain of left quotients with respect to language inclusion. This result holds for all safety conditions without any regularity assumptions, and for all (finite or infinite) graphs of finite degree.

We give several applications of this general principle. In particular, we characterize the exact memory requirements for the opponent in generalized reachability games, and we prove the existence of positional strategies in games with counters.

BibTeX - Entry

@InProceedings{colcombet_et_al:LIPIcs:2014:4857,
  author =	{Thomas Colcombet and Nathanael Fijalkow and Florian Horn},
  title =	{{Playing Safe}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{379--390},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4857},
  URN =		{urn:nbn:de:0030-drops-48571},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.379},
  annote =	{Keywords: Game Theory, Synthesis, Safety Specifications, Program Verification}
}

Keywords: Game Theory, Synthesis, Safety Specifications, Program Verification
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

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