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.MFCS.2018.42
URN: urn:nbn:de:0030-drops-96248
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9624/
Go to the corresponding LIPIcs Volume Portal

Carayol, Arnaud ; Hague, Matthew

Optimal Strategies in Pushdown Reachability Games

pdf-format:
LIPIcs-MFCS-2018-42.pdf (0.4 MB)

Abstract

An algorithm for computing optimal strategies in pushdown reachability games was given by Cachat. We show that the information tracked by this algorithm is too coarse and the strategies constructed are not necessarily optimal. We then show that the algorithm can be refined to recover optimality. Through a further non-trivial argument the refined algorithm can be run in 2EXPTIME by bounding the play-lengths tracked to those that are at most doubly exponential. This is optimal in the sense that there exists a game for which the optimal strategy requires a doubly exponential number of moves to reach a target configuration.

BibTeX - Entry

@InProceedings{carayol_et_al:LIPIcs:2018:9624,
  author =	{Arnaud Carayol and Matthew Hague},
  title =	{{Optimal Strategies in Pushdown Reachability Games}},
  booktitle =	{43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Igor Potapov and Paul Spirakis and James Worrell},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9624},
  URN =		{urn:nbn:de:0030-drops-96248},
  doi =		{10.4230/LIPIcs.MFCS.2018.42},
  annote =	{Keywords: Pushdown Systems, Reachability Games, Optimal Strategies, Formal Methods, Context Free}
}

Keywords: Pushdown Systems, Reachability Games, Optimal Strategies, Formal Methods, Context Free
Collection: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)
Issue Date: 2018
Date of publication: 27.08.2018

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