文章基本信息

标题：Timed Games and Deterministic Separability
本地全文：下载
作者：Lorenzo Clemente ; SÅ,awomir Lasota ; RadosÅ,aw Pi{'o}rkowski 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：121:1-121:16
DOI：10.4230/LIPIcs.ICALP.2020.121
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study a generalisation of BÃ¼chi-Landweber games to the timed setting. The winning condition is specified by a non-deterministic timed automaton with epsilon transitions and only Player I can elapse time. We show that for fixed number of clocks and maximal numerical constant available to Player II, it is decidable whether she has a winning timed controller using these resources. More interestingly, we also show that the problem remains decidable even when the maximal numerical constant is not specified in advance, which is an important technical novelty not present in previous literature on timed games. We complement these two decidability result by showing undecidability when the number of clocks available to Player II is not fixed. As an application of timed games, and our main motivation to study them, we show that they can be used to solve the deterministic separability problem for nondeterministic timed automata with epsilon transitions. This is a novel decision problem about timed automata which has not been studied before. We show that separability is decidable when the number of clocks of the separating automaton is fixed and the maximal constant is not. The problem whether separability is decidable without bounding the number of clocks of the separator remains an interesting open problem.
关键词：Timed automata; separability problems; timed games