LDR 02769nac  22003491u 4500
010    _bbr.
090    _a12158
101    _aeng
102    _aFR
100    _a20091130              frey50       
200    _aAlgèbre et combinatoire des jeux de parité
       _bTHES
       _fWalid Belkhir
       _gsous la direction de Luigi Santocanale
210    _a[S.l.]
       _c[s.n.]
       _d2008
215    _a1 vol. (VIII-214 p.)
       _d30
       _cfig.
320    _aBibliogr. p. [203]-214
328    _bThèse de doctorat
       _cinformatique
       _d2008
       _eAix-Marseille 1
330    _aLes 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
336    _aConsultable en ligne au format html. Également disponible au format pdf : 1 fichier (1,5 Mo) 
676    _a2010
686    _20
       _9161141
       _a03Bxx
       _bMathematical logic and foundations
       _xGeneral logic
686    _20
       _9161210
       _a03D55
       _bMathematical logic and foundations -- Computability and recursion theory
       _xHierarchies
686    _20
       _9161342
       _a05C85
       _bCombinatorics -- Graph theory
       _xGraph algorithms
686    _20
       _9165908
       _a68Q60
       _bComputer science -- Theory of computing
       _xSpecification and verification (program logics, model checking, etc.)
686    _20
       _9167104
       _a97A70
       _bMathematics education - General, mathematics and education
       _xTheses and postdoctoral theses
700    _aBelkhir
       _bWalid
       _4070
       _f1980-
       _9169137
702    _9169138
       _aSantocanale
       _bLuigi
       _f1967-
       _4727
712    _4295
       _9167375
       _aUniversité de Provence
856    _uhttp://www.lif.univ-mrs.fr/~belkhir/these.pdf
       _zLIF
905    _avm
       _b2009-01-06
906    _aec
       _b2012-04-03
906    _aec
       _b2013-06-26
995    _f05414-01
       _xdon
       _916499
       _cCMI
       _20
       _kThèses BEL
       _o0
       _eSalle S
       _bCMI
001     12158
Languages: English | Français | |