2026-07-23T03:26:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4381 2024-03-06T10:34:59Z ddc:004 open_access

Emptiness Of Alternating Tree Automata Using Games With Imperfect Information Fijalkow, Nathanaël Pinchinat, Sophie Serre, Olivier Alternating Automata Emptiness checking Two-player games Imperfect Information Games 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathanaël Fijalkow and Sophie Pinchinat and Olivier Serre 2013 Is Part Of LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2013.299 urn:nbn:de:0030-drops-43812 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.299 eng https://creativecommons.org/licenses/by/3.0/legalcode