Les travaux présentés ici s'intéressent aux coloriages du plan discret. Ce modèle d'inspiration géométrique est intrinsèquement lié aux modèles de calcul, et son étude se décline ici suivant deux axes complémentaires: calculabilité et combinatoire. Nous montrons en particulier ici comment de nombreux résultats récents s'expriment naturellement à travers le concept de bases, propriétés vérifiées par au moins un point de tout ensemble de coloriages, et d'antibases, contre-exemples à ce concept. Nous examinons ensuite les différents codages du calcul par des jeux de tuiles et exhibons en particulier un nouveau codage épars, permettant de caractériser les degrés Turing des ensembles de coloriages. Enfin nous revenons aux origines en étudiant les pavages du point de vue de la logique. Nous caractérisons ainsi les grandes familles d'ensembles de coloriages par des fragments de la logique monadique du second ordre.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00653343 |
| Date | 13 December 2011 |
| Creators | Jeandel, Emmanuel |
| Publisher | Université Montpellier II - Sciences et Techniques du Languedoc |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | habilitation ࠤiriger des recherches |
Page generated in 0.0024 seconds