Un automate cellulaire est un système dynamique discret qui modélise des objets ayant une évolution parallèle synchrone: l'espace est divisé en cellules ayant chacune un état et qui évoluent toutes selon une même règle locale, qui ne dépend que d'un nombre fini de cellules voisines. Malgré la simplicité de la formalisation de ce système, des comportements très complexes peuvent apparaître, qui en font notamment un modèle de calcul. Cette complexité a été rattachée à diverses théories: topologie, mesure, décidabilité, information...Nous adoptons ici une approche basée sur la dynamique symbolique, c'est à dire l'étude des mots infinis sur un alphabet donné auxquels on applique un décalage, suppression de la première lettre. À chaque automate cellulaire peut en effet être associé son tracé, l'ensemble des mots infinis représentant la séquence des états successifs pris par la cellule centrale de l'espace - ou un groupe de cellules centrales. On a alors une factorisation topologique: la lecture d'une lettre dans un de ces mots correspond exactement à une étape de l'évolution de l'automate. De nombreuses propriétés topologiques sont alors transmises par cette factorisation. Inversement, le fait que les cellules évoluent toutes de la même manière permet de déduire certaines propriétés de l'automate à partir de celles de son tracé. La première partie de la thèse est consacrée à ces nombreux liens. Une deuxième partie présente des conditions suffisantes pour qu'un ensemble de mots infinis soit le tracé d'un automate cellulaire. Enfin, une troisième partie donne un point de vue plus informatique, en récapitulant les principaux résultats d'indécidabilité sur le sujet et en prouvant que toutes les propriétés du tracé qui peuvent se voir infiniment tard sont indécidables
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00432058 |
| Date | 24 November 2008 |
| Creators | Guillon, Pierre |
| Publisher | Université Paris-Est |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | fra |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0017 seconds