Algebra and Combinatorics of Parity Games

Walid Belkhir 1, 2
2 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Résumé : Les jeux de parité sont la représentation combinatoire de la théorie des infimums, suprimums, et du plus petit point fixe et du plus grand point fixe sur les treillis complets. En gros, le formalisme des jeux de parité peut être considéré comme un $\mu$-calcul sur les treillis complets. Les hiérarchies et le pouvoir expressif sont un thème centrale dans la théorie des points fixes. La première partie de cette thèse est consacrée à l'étude du problème de la hiérarchie des variables sur le $\mu$-calcul des treillis. Des travaux antérieurs sur ce problème dans le cas du $\mu$-calcul propositionnel modal ont dégagé une mesure de complexité des graphes: c'est \emph{l'enchevêtrement}. Le dernier est la partie combinatoire de la hiérarchie des variables. La deuxième partie de cette thèse est consacrée à l'étude de l'enchevêtrement dans le contexte de la théorie des graphes, indépendamment de son origine dans la théorie des points fixes. Plusieurs résultats seront démontrés dans cette direction, tels que la reconnaissance des graphes d'enchevêtrement borné, la décomposition arborescente de tels graphes, et la fermeture par mineurs.
Type de document :
Thèse
Computer Science and Game Theory [cs.GT]. Aix-Marseille université, 2008. English
Liste complète des métadonnées

Littérature citée [74 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/tel-01277878
Contributeur : Walid Belkhir <>
Soumis le : mardi 23 février 2016 - 12:49:56
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : mardi 24 mai 2016 - 12:42:12

Fichier

Identifiants

  • HAL Id : tel-01277878, version 1

Citation

Walid Belkhir. Algebra and Combinatorics of Parity Games. Computer Science and Game Theory [cs.GT]. Aix-Marseille université, 2008. English. 〈tel-01277878〉

Partager

Métriques

Consultations de la notice

279

Téléchargements de fichiers

71