Emptiness Of Alternating Parity Tree Automata Using Games With Imperfect Information
Sophie Pinchinat, Olivier Serre · 2012
Abstract: We focus on the emptiness problem for alternating parity tree automata. The usual technique to tackle this problem first removes alternation, going to non-determinism, and then checks emptiness by reduction to a two-player perfect-information parity game. In this note, we give an alternative roadmap to this problem by providing a direct reduction to the emptiness problem to solving an imperfect-information two-player parity game. Key-words: Alternating Tree Automata; Emptiness; Imperfect Information Games; Positional Determinacy Le problème du vide pour les automates d’arbres alternant à parité via des jeux à information imparfaite Résumé: Nous considérons le problème du test du vide pour les automates d’arbres alternants à parité. La méthode usuelle pour résoudre ce problème, commence par supprimer l’alternance ce qui conduit à un automate non-déterministe dont le vide est ensuite testé par réduction à un jeux de parité à information parfaite. Dans cette note, nous proposons une approche alternative pour ce problème, en proposant une réduction directe du problème du vide à un jeu de parité à information imparfaite. Mots clés: Automates d’arbres alternants; test du vide; jeux à information imparfaite; déterminaison positionnelle