Memoryless Determinacy of Finite Parity Games: Another Simple Proof

Serge Haddad 1, 2, 3
2 MEXICO - Modeling and Exploitation of Interaction and Concurrency
LSV - Laboratoire Spécification et Vérification [Cachan], ENS Cachan - École normale supérieure - Cachan, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8643
Abstract : Memoryless determinacy of (infinite) parity games is an important result with numerous applications. It was first independently established by Emerson and Jutla [1] and Mostowski [2] but their proofs involve elaborate developments. The elegant and simpler proof of Zielonka [3] still requires a nested induction on the finite number of priorities and on ordinals for sets of vertices. There are other proofs for finite games like the one of Björklund, Sandberg and Vorobyovin [4] that relies on relating infinite and finite duration games. We present here another simple proof that finite parity games are determined with memoryless strategies using induction on the number of relevant states. The closest proof that relies on induction over non absorbing states is the one of Grädel [5]. However instead of focusing on a single appropriate vertex for induction as we do here, he considers two reduced games per vertex, for all the vertices of the game. The idea of reasoning about a single state has been inspired to me by the analysis of finite stochastic priority games by Karelovic and Zielonka [6].
Type de document :
Article dans une revue
Information Processing Letters, Elsevier, 2018, pp.3
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger
Contributeur : Serge Haddad <>
Soumis le : lundi 19 juin 2017 - 11:14:53
Dernière modification le : vendredi 21 décembre 2018 - 01:17:32
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 16:38:55


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01541508, version 1


Serge Haddad. Memoryless Determinacy of Finite Parity Games: Another Simple Proof. Information Processing Letters, Elsevier, 2018, pp.3. 〈hal-01541508〉



Consultations de la notice


Téléchargements de fichiers