Algèbre et combinatoire des jeux de parité / Walid Belkhir

Auteur: Belkhir, Walid (1980-) - AuteurAuteur secondaire : Santocanale, Luigi (1967-) - Directeur de thèseCollectivité secondaire: Université de Provence - Etablissement de soutenanceType de document: ThèseLangue: anglaisPays: FranceÉditeur: [S.l.] : [s.n.], 2008Description: 1 vol. (VIII-214 p.) : fig. ; 30 cmRé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 μ-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 μ-calcul des treillis. Des travaux antérieurs sur ce problème dans le cas du μ-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.Bibliographie: Bibliogr. p. [203]-214.Thèse: Thèse de doctorat en informatique, soutenue en 2008, organisme : Aix-Marseille 1 Sujets MSC: 03Bxx Mathematical logic and foundations -- General logic
03D55 Mathematical logic and foundations -- Computability and recursion theory -- Hierarchies
05C85 Combinatorics -- Graph theory -- Graph algorithms
68Q60 Computer science -- Theory of computing -- Specification and verification (program logics, model checking, etc.)
97A70 Mathematics education - General, mathematics and education -- Theses and postdoctoral theses
En-ligne: LIF

Bibliogr. p. [203]-214

Thèse de doctorat informatique 2008 Aix-Marseille 1

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 μ-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 μ-calcul des treillis. Des travaux antérieurs sur ce problème dans le cas du μ-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

Consultable en ligne au format html. Également disponible au format pdf : 1 fichier (1,5 Mo)

There are no comments for this item.

Log in to your account to post a comment.
Languages: English | Français | |