Soutenance mémoire
Notations et premières définitions
Espace de configurations
Soit A un alphabet et M un monoïde abélien, généralement, on considère N,Z, NE, ZD ou NE×ZD avec D, E ∈ N. Dans notre cas il sera essentiellement question de Z. Un élément du monoïde est appelé cellule. L’espace de configurations AM est l’espace des fonctions définies de M dans A que nous pouvons considérer comme des configurations d’éléments de A indexées par M .
Quelques classes d’automates cellulaires
Dans ce qui suit M = Z à l’exception de quelques cas signalés, pour ne pas alourdir la notation on notera directement ( AZ, F) un automate cellulaire.
Automates cellulaires permutatifs
Les automates cellulaires permutatifs se caractérisent par de fortes propriétés combinatoires. Shereshevsky [She92a] fut le premier à étudier les propriétés de cette catégorie d’automates cellulaires.
Définition 17 Soit (AZ, F) un automate cellulaire avec la règle locale f :
Ad+1 → A.
1- On dit que F est permutatif à gauche si ∀u ∈ Ad , ∀b ∈ A, ∃!a ∈ A, f (au) =b.
2- On dit que F est permutatif à droite si ∀u ∈ Ad, ∀b ∈ A, ∃!a ∈ A, f (ua) =b.
3- On dit que F est bi-permutatif s’il est à la fois permutatif à gauche et à droite.
Proposition 18 ([Hed69]) Un automate cellulaire permutatif à gauche ou à droite est surjectif.
Automates cellulaires fermants
Définition 20 1- Les points x, y sont dit asymptotiques à gauche si x(−∞,n) =y(−∞,n) pour un certain n ∈ Z.
2- Les points x, y sont dit asymptotiques à droite si x(n,+∞) = y(n,+∞) pour un certain n ∈ Z.
Automates cellulaires expansifs
Dans le cas des automates cellulaires unidimensionnels l’expansivité peut être vue comme une généralisation de la permutativité [SA93]. En dimension supérieure Shereshevsky [She93] relève l’impossibilité d’existence de tels systèmes.
Proposition 24 Tout automate cellulaire (AZ, F) expansif de rayon r est conjugué à (Σ[−r,r] (F), σ).
Théorème 25 ([Kur97],[Nas95]) Tout automate cellulaire expansif est ouvert et conjugué à un sous-décalage de type fini.
Proposition 26 ([BM00],[Nas95]) Un automate cellulaire expansif est mélangeant.
Dynamique topologique des automates cellulaires
Dans le cadre des automates cellulaires plusieurs particularités sont à signaler. D’abord la dichotomie établie par la proposition 4 parmi les systèmes dynamiques transitifs se généralise à tous les automates cellulaires grâce au résultat suivant, dû à Codenotti et Margara [CM96] :
Proposition 27 Un automate cellulaire transitif est sensible aux conditions initiales.
Une autre particularité des automates cellulaires concerne la caractérisation de l’existence de points d’équicontinuités : elle est synonyme de l’existence de mots bloquants. Un mot bloquant est un mot dont les images successives par l’action de l’automate sont insensibles aux changements de son voisinage.
Définition 28 Soit s > 0, un mot w de longueur ≥ s est dit s-bloquant pour l’automate cellulaire (A Z , F) s’il existe un entier p ∈ |w| − s tel que :
∀x, y ∈ [w]0, ∀n ≥ 0, F n(x) [p,p+s) = Fn (y) [p,p+s)
Proposition 29 ([Kur97]) Soit (AZ , F) un automate cellulaire de rayon r > 0, les conditions suivantes sont équivalentes : 1. (AZ , F) n’est pas sensible aux conditions initiales. 2. (AZ , F) admet un mot r-bloquant. 3. ( AZ , F) est topologiquement presque équicontinu..
|
Table des matières
I Introduction
1 Généralités
1.1 Notions de dynamique topologique
1.2 Rappels topologiques et ergodiques
1.3 Propriétés spectrales des systèmes dynamiques
1.3.1 Valeurs propres topologiques
1.3.2 Valeurs propres ergodiques
2 Propriétés spectrales des automates cellulaires
2.1 Notations et premières définitions
2.1.1 Espace de configurations
2.1.2 Décalage et sous-décalage
2.2 Quelques classes d’automates cellulaires
2.2.1 Automates cellulaires permutatifs
2.2.2 Automates cellulaires fermants
2.2.3 Automates cellulaires expansifs
2.3 Dynamique topologique des automates cellulaires
2.4 Théorie ergodique des automates cellulaires
2.4.1 Mesures invariantes pour les automates cellulaires
2.5 Classification de Gilman
2.6 Densité des points périodiques
2.7 Systèmes sturmiens
2.8 Propriétés spectrales des automates cellulaires
II Valeurs propres des automates cellulaires
3 Exemples et premiers résultats
4 Valeurs propres topologiques des automates cellulaires
5 Valeurs propres mesurables des automates cellulaires
