Emptiness Of Alternating Parity Tree Automata Using Games With Imperfect Information
Résumé
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.
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...