文章基本信息

标题：Emptiness Of Alternating Tree Automata Using Games With Imperfect Information
本地全文：下载
作者：Nathana{\"e}l Fijalkow ; Sophie Pinchinat ; Olivier Serre 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：24
页码：299-311
DOI：10.4230/LIPIcs.FSTTCS.2013.299
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider the emptiness problem for alternating tree automata, with two acceptance semantics: classical (all branches are accepted) and qualitative (almost all branches are accepted). For the classical semantics, the usual technique to tackle this problem relies on a Simulation Theorem which constructs an equivalent non-deterministic automaton from the original alternating one, and then checks emptiness by a reduction to a two-player perfect information game. However, for the qualitative semantics, no simulation of alternation by means of non-determinism is known. We give an alternative technique to decide the emptiness problem of alternating tree automata, that does not rely on a Simulation Theorem. Indeed, we directly reduce the emptiness problem to solving an imperfect information two-player parity game. Our new approach can successfully be applied to both semantics, and yields decidability results with optimal complexity; for the qualitative semantics, the key ingredient in the proof is a positionality result for stochastic games played over infinite graphs.
关键词：Alternating Automata; Emptiness checking; Two-player games; Imperfect Information Games