Algèbre et combinatoire des jeux de parité / par Walid Belkhir ; sous la direction de M. Luigi Santocanale

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Théorie des jeux

Treillis, Théorie des

Théorie des graphes

Variables (mathématiques)

Santocanale, Luigi (Directeur de thèse / thesis advisor)

Université de Provence. Section sciences (Autre partenaire associé à la thèse / thesis associated third party)

Université de Provence (1970-2011) (Organisme de soutenance / degree-grantor)

Relation : Algèbre et combinatoire des jeux de parité / par Walid Belkhir / Villeurbanne : [CCSD] , 2016

Relation : Algèbre et combinatoire des jeux de parité / par Walid Belkhir ; sous la direction de M. Luigi Santocanale / Lille : Atelier national de reproduction des thèses , 2008

Résumé / Abstract : Les jeux de parité sont la représentation combinatoire de la théorie des infimums, suprimum, 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 central 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 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.