文章基本信息

标题：Optimal Strategies in Pushdown Reachability Games
本地全文：下载
作者：Arnaud Carayol ; Matthew Hague
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2018
卷号：117
页码：1-14
DOI：10.4230/LIPIcs.MFCS.2018.42
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Pushdown Systems; Reachability Games; Optimal Strategies; Formal Methods; Context Free