Coloriage du plan discret par jeux de tuiles déterministes
Nous étudions dans ce mémoire les propriétés des ensembles de pavages engendrés par des jeux de tuiles de Wang exhibant une ou plusieurs directions de déterminisme local, en accordant une importance toute particulière aux jeux déterministes dans les quatre directions diagonales simultanément, dits 4...
Đã lưu trong:
| Tác giả chính: | |
|---|---|
| Tác giả khác: | , , , , , , |
| Định dạng: | Thèse numérique |
| Ngôn ngữ: | Français |
| Được phát hành: |
2014.
|
| Những chủ đề: | |
| Truy cập trực tuyến: | Accès au texte intégral https://theses.univ-orleans.fr/public/2014ORLE2069_va.pdf http://www.theses.fr/2014ORLE2069/abes https://theses.hal.science/tel-01288501 |
| Chú thích: |
Titre provenant de l'écran-titre Ecole(s) Doctorale(s) : École doctorale Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes (Centre-Val de Loire ; 2012-....) Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) Autre(s) contribution(s) : Anne Siegel (Président du jury) ; Nicolas Ollinger, Anne Siegel, Fabien Durand, Bruno Durand, Olivier Bournez, Emmanuel Jeandel, Inès Klimann (Membre(s) du jury) ; Fabien Durand, Bruno Durand (Rapporteur(s)) |
| Autres localisations: | Voir dans le Sudoc |
| Variante du titre: | Coloring the discrete plane using deterministic tilesets |
| LEADER | 05150nam a22004577a 4500 | ||
|---|---|---|---|
| 001 | 583474 | ||
| 008 | 160315s2014 xxe ||| |||| 00| 0 fre d | ||
| 009 | PPN191922404 | ||
| 041 | 0 | |a fre |b fre |b eng | |
| 082 | |a 004.015 1 | ||
| 084 | |a 004 | ||
| 100 | 1 | |a Le Gloannec, Bastien, |d 1986- | |
| 240 | 1 | 0 | |a Coloring the discrete plane using deterministic tilesets |
| 245 | 1 | 0 | |a Coloriage du plan discret par jeux de tuiles déterministes |c Bastien Le Gloannec ; sous la direction de Nicolas Ollinger. |
| 256 | |a Données textuelles | ||
| 260 | |c 2014. | ||
| 500 | |a Titre provenant de l'écran-titre | ||
| 500 | |a Ecole(s) Doctorale(s) : École doctorale Mathématiques, Informatique, Physique Théorique et Ingénierie des Systèmes (Centre-Val de Loire ; 2012-....) | ||
| 500 | |a Partenaire(s) de recherche : Laboratoire d'informatique fondamentale d'Orléans (Orléans ; 1987-....) (Laboratoire) | ||
| 500 | |a Autre(s) contribution(s) : Anne Siegel (Président du jury) ; Nicolas Ollinger, Anne Siegel, Fabien Durand, Bruno Durand, Olivier Bournez, Emmanuel Jeandel, Inès Klimann (Membre(s) du jury) ; Fabien Durand, Bruno Durand (Rapporteur(s)) | ||
| 502 | |a Thèse de doctorat. Informatique. Orléans. 2014 | ||
| 520 | |a Nous étudions dans ce mémoire les propriétés des ensembles de pavages engendrés par des jeux de tuiles de Wang exhibant une ou plusieurs directions de déterminisme local, en accordant une importance toute particulière aux jeux déterministes dans les quatre directions diagonales simultanément, dits 4-way déterministes. Après avoir proposé une construction alternative d un jeu de tuiles apériodique 4-way déterministe, nous étudions plusieurs problèmes de décision sur ces objets et complétons en particulier le résultat d indécidabilité du problème du pavage dans le cadre 4-way déterministe établi par Lukkarila en montrant l indécidabilité du problème du pavage périodique 4-way déterministe. Nous montrons également que des familles complexes de coloriages du plan telles que celles engendrées par les substitutions restent sofiques dans un cadre 4-way déterministe. Nous proposons une bi-déterminisation des constructions de jeux de tuiles point-fixe de Durand, Romashchenko et Shen et en tirons quelques premières applications. Enfin, nous considérons l opportunité d élargir le rayon de la règle locale de déterminisme afin de limiter les directions d expansivité et ainsi de permettre la construction localement déterministe de systèmes de particules et collisions non triviaux. Nous introduisons un nouveau modèle syntaxique commode afin de travailler à rayon deux et revisitons des problématiques de Lukkarila dans ce cadre. | ||
| 520 | |a In this thesis, we study some properties of the sets of tilings generated by Wang tilesets that exhibit one or more directions of local determinism, focusing in particular on tilesets that are simultaneously deterministic in the four diagonal directions, referred to as 4-way deterministic. After having exposed an alternative construction of a 4-way deterministic aperiodic tileset, we study several decision problems on these objects and complete in particular Lukkarila s result of undecidability of the Domino Problem in the 4-way deterministic setting proving the undecidability of the 4-way deterministic periodic Domino Problem. We also prove that some complex families of colorings of the plane such that those generated by substitutions remain sofic in the 4-way deterministic setting. We propose a bi-determinization of the constructions by Durand, Romashchenko and Shen of fixed-point tilesets and give some first applications. Finally, we investigate the idea of extending the radius of the local rule of determinism in order to reduce the set of directions of expansiveness and thus allow the local realization of non-trivial particles and collisions systems. We introduce a new and convenient syntactic model to deal with radius two and revisit some of Lukkarila s problems in this setting. | ||
| 538 | |a Configuration requise : un logiciel capable de lire un fichier au format : PDF | ||
| 650 | |a Pavage (mathématiques) | ||
| 650 | |a Coloriage (mathématiques) | ||
| 650 | |a Permutations (mathématiques) | ||
| 650 | |a Thèses et écrits académiques | ||
| 700 | 1 | |a Ollinger, Nicolas, |d 19..- |4 ths |4 opn | |
| 700 | 1 | |a Siegel, Anne, |d 1975-...., |c chercheuse en bioinformatique. |4 opn | |
| 700 | 1 | |a Durand, Fabien, |d 1969-...., |c mathématicien. |4 opn | |
| 700 | 1 | |a Durand, Bruno, |d 1968-...., |c informaticien. |4 opn | |
| 700 | 1 | |a Bournez, Olivier. |4 opn | |
| 700 | 1 | |a Jeandel, Emmanuel, |d 1980- |4 opn | |
| 700 | 1 | |a Klimann, Inès. |4 opn | |
| 710 | 2 | |a Université d'Orléans. |4 dgg | |
| 856 | 4 | |q PDF |s 3179425 |u http://www.theses.fr/2014ORLE2069/document |z Accès au texte intégral | |
| 856 | 4 | |u https://theses.univ-orleans.fr/public/2014ORLE2069_va.pdf | |
| 856 | 4 | |u http://www.theses.fr/2014ORLE2069/abes | |
| 856 | 4 | |u https://theses.hal.science/tel-01288501 | |
| 997 | |0 583474 |1 Thèse numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||