Automates cellulaires non-uniformes

• 
• 

1. Introduction

Les automates cellulaires non-uniformes sont une généralisation des automates cellulaires. Ils furent introduit par Gianpiero Cattaneo, Alberto Dennunzio, Enrico Formenti et Julien Provillard dans le but d'étudier la stabilité structurelle du modèle classique. Ils donnent également un cadre formel aux nombreux modèles hybrides existants dans la littérature. Tout comme les automates cellulaires classiques, les automates cellulaires non-uniformes agissent en parallèle sur tous les points d'une configuration en fonction de données locales mais, à la différence des premiers, la façon dont un point d'une configuration va évoluer dépend de sa position. C'est ce qui donne le caractère non-uniforme de ce modèle.

Dans les pages qui suivent, nous allons donner une définition du modèle et expliquer son fonctionnement. Plusieurs exemples seront donnés. Ils illustreront l'étude initiale faite sur la stabilité de certaines propriétés des automates cellulaires ainsi que celle effectuée sur les propriétés propres du nouveau modèle.

 

2. Définitions

Nous allons rappeler ici les notions de base qui permettent de comprendre et de manipuler les automates cellulaires non-uniformes. Nous verrons comment est défini leur espace de travail et comment ils agissent sur les éléments de cet espace.

2.1 Configurations

Une configuration représente une donnée sur laquelle l'automate peut travailler. Une configuration est toujours associée à un ensemble fini, son alphabet, et se compose d'une suite bi-infinie d'éléments de cet ensemble, les états. On peut donc voir une configuration comme un ruban dont les positions sont caractérisées par un indice et sur lequel apparaissent successivement des états de l'alphabet.

 

Une configuration sur l'alphabet {0, 1}.

L'ensemble des configurations sur un alphabet A est noté C_A et est appelé espace des configurations. On munit cet espace d'une distance appelée distance de Cantor. Deux configurations x et y sont dites à distance 2^-l si l est le plus petit entier qui permet de différencier x et y. L'entier l représente la taille de la plus petite fenêtre qui, centrée sur la position initiale de chaque ruban, permet des observations différentes.

 

Calcul de la distance entre deux configurations.

Sur l'exemple ci-dessus, les configurations x et y sont à distance d(x,y) = 2^-3 = 1/8. La topologie induite par cette distance a pour ouverts de base les cylindres, c'est à dire les configurations qui sont égales sur un ensemble successif de positions. Cette topologie coïncide avec la topologie produit. L'espace des configurations muni de cette topologie a d'importantes propriétés.

Proposition 1 . L'espace des configurations C_A muni de la topologie induite par la distance de Cantor est compact et donc complet.

2.2 Automates cellulaires non-uniformes

Un automate cellulaire non-uniforme est un système qui va transformer une configuration en une autre. Pour se faire, l'automate va simultanément appliquer une règle locale à chacune des positions de la configuration. Pour chaque position, la règle locale va considérer les états présents dans un voisinage et mettre à jour l'état dans la position courante. La différence par rapport aux automates cellulaires classiques est que la règle que l'on applique dépend de la position, on n'applique plus uniformément une règle unique.

Une règle locale est une fonction caractérisée par son alphabet de travail et par son rayon. L'alphabet détermine sur quel espace de configurations la règle s'applique tandis que le rayon indique la taille du voisinage à considérer. Plus précisément, une règle locale de rayon r sur un alphabet A est une fonction de la forme h : A^2r+1 → A. Une distribution de règles sur un alphabet A est une suite bi-infinie de règles locales sur l'alphabet A.

Un automate cellulaire non-uniforme est entièrement défini par un couple ‹ A, λ › où A est un alphabet et λ une distribution de règles sur A. Un tel couple définit l'automate H : C_A → C_A qui à une configuration x associe la configuration H(x) telle que, pour toute position i, H(x)_i = λ_i( x_-ri , ... , x_ri ) où r_i désigne le rayon de λ_i. On dit alors que H est engendré par λ.

 

Action de l'automate sur une configuration.

L'exemple ci-dessus montre comment s'obtient une nouvelle configuration à partir d'une configuration initiale. L'alphabet de travail est {0, 1} et les règles de la distribution de règles sont

Règle	Rayon	Définition
id	0	id(x) = x
σ	1	σ(x, y, z) = x
ρ	1	ρ(x, y, z) = z

Théorème 2 . Soit A un ensemble fini, une fonction H : C_A → C_A est un automate cellulaire non-uniforme si et seulement si elle est continue pour la topologie de Cantor.

Ce théorème permet de caractériser l'ensemble des automates cellulaires non-uniformes et montre à quel point cette classe est vaste. Dans la pratique, on s'intéresse à des sous-classes pour lesquelles les distributions de règles vérifient certaines propriétés.

Un exemple important de sous-classe est celle des automates cellulaires classiques (dont nous aurons besoin dans la suite). Un automate cellulaire non-uniforme H défini par une distribution de règle λest un automate cellulaire s'il existe une règle locale f telle que, pour toute position i, λ_i = f. Un automate cellulaire est donc entièrement défini par son alphabet et une unique règle locale qui va s'appliquer uniformément en tout point des configurations d'entrée.

 

3. Stabilité structurelle

Dans cette section, nous allons introduire une sous-classe d'automates cellulaires non-uniformes et voir en quoi on peut les considérer comme des modèles perturbés d'automates cellulaires classiques. Nous nous intéresserons alors aux liens qui unissent un automate à sa modélisation perturbée.

Afin d'alléger les notations, dans cette partie et les suivantes nous abrègerons souvent automate cellulaire en CA et automate cellulaire non-uniforme en ν-CA.

3.1 dν-CA et modèles de perturbation

Nous allons nous intéresser à une sous-classe des automates cellulaires non-uniformes, les dν-CA. Un ν-CA H est un dν-CA de règle par défaut f s'il existe une distribution de règles λ qui définit Htelle que le nombre de positions i où λ_i ≠ f est fini.

L'idée intuitive derrière cette définition est qu'un dν-CA H de règle par défaut f a une structure très proche de celle du CA F de règle locale f. La différence étant qu'en un nombre fini d'endroits la règle d'origine a été altérée. On peut par exemple imaginer qu'une règle locale est implémentée par un circuit électronique et qu'il suffirait de les mettre bout à bout pour simuler F. H serait alors une représentation de ce système dans lequel certains circuits seraient en panne ou présenteraient des défauts. C'est pourquoi on dit qu'un dν-CA de règle par défaut f est un modèle de perturbation du CA de règle locale f. En particulier tout automate cellulaire est un modèle de perturbation de lui-même.

3.2 Injectivité et surjectivité

Nous nous intéresserons dans un premier temps aux liens qu'il existe entre un CA et ses modèles de perturbations au niveau de l'injectivité et de la surjectivité.

Une conséquence quasi-immédiate de la compacité de l'espace des configurations donne le théorème suivant.

Théorème 3 . Soit F un CA et H un modèle de perturbation de F, si H est surjectif alors F est surjectif.

Nous allons introduire ici quelques notions supplémentaires sur les automates cellulaires qui nous seront utiles pour les résultats suivants.

Soit A un alphabet et x une configuration de C_A, x est une configuration finie s'il existe une lettre α de A telle que le nombre de positions i où x_i ≠ α est fini, on note CF_A l'ensemble des configurations finies sur l'alphabet A. Si H est un dν-CA sur l'alphabet A, CF_A est stable par H et on note H_|F   : CF_A → CF_A sa restriction aux configurations finies.

Un théorème important relie un automate cellulaire à sa restriction aux configurations finies.

Théorème du jardin d'Eden. [1, 2] Soit F un CA, F est surjectif si et seulement si F_|F   est injectif.

En particulier tout automate cellulaire injectif est surjectif et donc bijectif.

Nous pouvons maintenant donner les principaux théorèmes concernant les liens entre CA et modèles de perturbations.

Théorème 4. Soit F un CA et H un modèle de perturbation de F, 

1. H_|F   injectif implique F surjectif; 
2. H injectif implique F injectif; 
3. H injectif implique H surjectif. 

Le premier point est une conséquence du théorème du jardin d'Eden, si F est un CA non surjectif alors il existe des motifs finis qui ont une même image par F. Il suffit alors de placer ces motifs dans des configurations finies d'un modèle de perturbation H de F suffisamment loin des perturbations pour que leurs images restent identiques, d'où le résultat. Les deux points suivants se montrent par des arguments de dénombrement. Il est intéressant de noter que le dernier point ne fait pas intervenir l'automate cellulaire F et est donc un résultat sur les dν-CA eux-mêmes. C'est en fait une généralisation d'une conséquence du théorème du jardin d'Eden aux dν-CA. Cependant le théorème lui-même ne se généralise pas, il existe des dν-CA H non surjectifs tels que H_|F   est injectif.

3.3 Dynamique

L'intérêt des automates cellulaires et de leur version non-uniforme est de pouvoir les considérer comme des systèmes dynamiques. En effet un tel automate transforme une configuration en une autre, on peut donc étudier la suite de configurations Hⁱ(c) pour un automate H et une configuration initiale c. Cette suite est la trajectoire de c dans l'espace des configurations. On s'intéresse alors aux propriétés de cette trajectoire : convergence, stabilité ou à l'inverse comportement chaotique.

Dans le cas des automates cellulaires, il est possible de visualiser ces trajectoires à l'aide de diagramme espace-temps. Un diagramme espace-temps est une représentation graphique de la trajectoire dans laquelle chaque état d'une configuration est associé à un carré de couleur. Une configuration sera donc représentée par une ligne de carrés de couleur correspondant aux états qu'elle contient et le diagramme est la superposition de ces lignes qui s'assimile donc à la trajectoire.

Voici deux exemples de diagrammes espace-temps pour l'automate cellulaire sur l'alphabet {0, 1} de règle locale f(x, y, z) = x + z (mod 2). Les '0' sont représentés par des carrés blancs et les '1' par des carrés noirs.

 

Diagramme espace-temps à partir d'une configuration ne contenant initialement qu'un '1'.

Diagramme espace-temps à partir d'une configuration quelconque.

Nous allons donner ici quelques notions sur les propriétés qui motivent l'étude des systèmes dynamiques. Nous allons expliquer l'idée générale de ces notions ainsi que la manière dont elles s'interprètent dans notre cadre particulier.

Un point d'équicontinuité d'un système dynamique est une configuration initiale qui engendre une trajectoire stable. Cette stabilité s'exprime par le fait que toute trajectoire issue d'une configuration proche de la configuration initiale reste proche de la trajectoire de celle-ci. Dans notre cadre, la notion de proximité entre deux configurations s'exprime par le fait qu'elles coïncident sur un ensemble de positions centré en 0. Une configuration c sera donc un point d'équicontinuité pour un automate H si, pour tout entier m, il existe un entier n tel que pour toute configuration c' qui coïncide avec c entre les indices -n et n (c' proche de c), on a Hⁱ(c) et Hⁱ(c') qui coïncident entre les indices -m et m à toute étape i (les trajectoires restent proches). Cela signifie entre autres qu'une connaissance partielle de centre deux indices permet de construire toute une colonne de son diagramme espace-temps. C'est bien une notion de stabilité car une petite erreur, sur un état loin de la position centrale, ne pourra pas trop grandir, i.e. s'approcher de la position centrale.

Si c est un point d'équicontinuité alors sa connaissance entre les indices -n et n permet de connaitre la dynamique entre les indices -m et m.

On dira qu'un système dynamique est équicontinu si tous ses points sont des points d'équicontinuité. On dira qu'il est presque-équicontinu si l'ensemble de ses points d'équicontinuité est un ensemble résiduel (complémentaire d'un ensemble maigre).

A l'opposé de ces notions de stabilité, il y a celle de sensibilité aux conditions initiales, propriété qui est très souvent mise en avant dans les systèmes chaotiques. Un système dynamique est dit sensible aux conditions initiales ou plus simplement sensible s'il existe une distance ε > 0 appelée constante de sensibilité telle que pour tout point du système, on peut trouver un point aussi proche que l'on veut tel que les deux trajectoires s'écartent d'une distance au moins ε.

Un système sensible n'admet pas de point d'équicontinuité par contre un système sans point d'équicontinuité peut ne pas être sensible. Cependant dans le cas des automates cellulaires la situation est différente.

Théorème 5. [6] Soit F un CA de rayon r, les propriétés suivantes sont équivalentes :

1. F n'est pas sensible. 
2. F admet un mot r-bloquant. 
3. F est presque-équicontinu. 

Théorème 6. [3] Soit F un CA de rayon r, les propriétés suivantes sont équivalentes :

1. F est équicontinu. 
2. Il existe une taille de mot telle que tout mot de cette taille est r-bloquant pour F. 
3. F est ultimement périodique. 

On voit que les notions de stabilité et d'instabilité sur les automates cellulaires sont très liées à la présence de mots bloquants. Un mot k-bloquant pour un CA F est un motif qui présent dans une configuration bloque la dynamique sur une colonne de largeur k. En particulier, un mot r-bloquant où r est le rayon de F rend les dynamiques à gauche et à droite de la colonne qu'il bloque indépendantes. Une conséquence de ceci est que la présence de deux mots r-bloquants dans une configuration bloque la dynamique sur toute une bande comprise entre les deux motifs.

Une configuration c contenant deux mots r-bloquants.

Pour étudier la stabilité structurelle de l'équicontinuité, de la presque-équicontinuité et de la sensibilité des automates cellulaires, il apparait naturel de s'intéresser à la notion de mots bloquants pour les modèles de perturbations. On développe ainsi la notion de mots fortement bloquants. Un mot fortement k-bloquant pour un CA F de règle locale f est un motif qui, présent dans une configuration d'un modèle de perturbation de F à un endroit où s'applique uniquement la règle f, bloque la dynamique sur une colonne de largeur k. Autrement dit, si H est un modèle de perturbation de F défini par la distribution de règle λ, que u est un mot fortement k-bloquant présent entre les positions i et j d'une configuration c et que λ_i = λ_i+1 = ... = λ_j alors u bloque une colonne de taille k de la trajectoire issue de cpour H.

Un mot fortement bloquant pour un modèle de perturbation d'un CA F joue fondamentalement le même rôle qu'un mot bloquant pour F lorsqu'il est suffisamment éloigné des perturbations. En particulier tout mot fortement k-bloquant est k-bloquant. Si l'inverse était vrai, si les deux notions étaient en fait équivalentes, la presque-équicontinuité et l'équicontinuité seraient des propriétés structurellement stables (si F l'avait, tous ses modèles de perturbations aussi). Mais ce n'est pas le cas, il existe des automates cellulaires presque-équicontinus qui admettent des modèles de perturbation sensible.

On peut donner l'exemple de l'automate cellulaire F de règle locale f sur l'alphabet {0, 1, 2} définie par :

f(x, 0, y) = 1 si x = 1 ou y = 1; 0 sinon 
f(x, 1, y) = 2 si x = 2 ou y = 2; 1 sinon 
f(x, 2, y) = 0 si x = 1 ou y = 1; 2 sinon 

et de son modèle de perturbation H où en toute position on applique f sauf en 0 où on applique la fonction constante égale à 1. F est presque-équicontinu mais H est sensible.

Diagramme espace-temps de F.

Diagramme espace-temps de H sur la même configuration initiale.

En fait cette constatation indique que, malgré ce que l'on pourrait croire, la notion de mot bloquant n'est pas un concept local, ce que l'on a imposé avec la variante des mots fortement bloquants. Cependant on peut établir le théorème suivant :

Théorème 7. [7] Soit F un CA de rayon r et H un modèle de perturbation de F, les propriétés suivantes sont équivalentes :

1. F est équicontinu. 
2. Il existe une taille de mot telle que tout mot de cette taille est fortement r-bloquant pour F. 
3. H est ultimement périodique. 

Comme tout ν-CA ultimement périodique est équicontinu, ce théorème nous donne la stabilité structurelle pour l'équicontinuité. Cependant il existe des automates cellulaires non équicontinus qui admettent des modèles de perturbations équicontinus. Un exemple très simple est l'automate cellulaire F sur {0, 1} de règle locale f définie par f(x, y, z) = x * y * z. Toute configuration qui contient au moins un '0' va se voir envahir par des '0' dans la dynamique. Donc la seule configuration qui ne soit pas un point d'équicontinuité est celle qui ne contient que des '1'. On définit alors un modèle de perturbation H de F où, en toute position, on applique f, sauf en 0, où on applique la fonction constante égale à 0. H est alors trivialement équicontinu sans que F ne le soit.

A l'opposé, il existe des automates cellulaires sensibles qui admettent des modèles de perturbation presque-équicontinu. C'est le cas de l'AC dont nous présentons un diagramme espace-temps ci dessous suivi de celui d'un de ses modèles de perturbation.

Diagramme espace-temps d'un CA sensible.

Diagramme espace-temps d'un de ses modèles de perturbation presque-équicontinu.

Ainsi parmi les propriétés que nous avons présentées, seule l'équicontinuité est structurellement stable. Nous avons vu que la presque-équicontinuité ne l'était que dans certains cas et que la sensibilité ne l'était pas forcément non plus.

 

4. Distributions de règles

Dans la partie précédente, nous avons utilisé les automates cellulaires non-uniformes pour modéliser des perturbations sur le modèle classique. Cependant, les ν-CA forment une nouvelle classe de systèmes dynamiques qu'il est intéressant d'étudier en soi. Par exemple les automates cellulaires classiques sont utilisés en physique ou en biologie en tant que modèles. Libérer les contraintes d'uniformité d'application d'une règle locale peut apporter plus de souplesse à ces modèles.

4.1 Ensemble fini de règles et rν-CA

Une hypothèse raisonnable que nous pouvons faire sur les ν-CA qui peuvent effectivement servir de modèles est qu'ils n'utilisent qu'un jeu fini de règles locales différentes. Nous allons donc nous restreindre aux ν-CA qui peuvent se définir ainsi.

Dans la suite, nous allons supposer que nous disposons d'un ensemble fini J de règles locales sur un même alphabet A et nous allons considérer les distributions de règles λ telles que pour toute position i la règle λ_i est une règle de J. Nous notons Λ_J l'ensemble des distributions ainsi définies et, pour λ dans Λ_J, H_λ désigne le ν-CA défini par λ.

Parallèlement nous introduisons la classe des rν-CA. Un ν-CA H est un rν-CA de rayon r s'il existe une distribution de règles λ qui définit H telle que, pour toute position i, λ_i est une règle de rayon r.

En particulier, tout rν-CA de rayon r est défini sur un ensemble fini de règles, le nombre de règles de rayon r sur un alphabet fini étant en nombre fini. Par ailleurs, comme J est fini, le rayon des règles locales dans J est borné par un entier r. On peut alors considérer que toutes les règles de J sont en fait de rayon r en créant des dépendances fictives. Si f est une règle de J de rayon r_f, on l'identifie à la règle f' de rayon r définie par f'( x_-r , ..., x_r ) = f( x_-rf , ..., x_rf ), cela ne change pas les ν-CA définis par les distributions de règles de Λ_J et que ce sont bien des rν-CA.

On peut donc désormais considérer que toutes les règles de J ont le même rayon r et donc que les distributions de Λ_J définissent des rν-CA de rayon r.

4.2 Conservation du nombre

Dans des domaines telles que la physique, les lois qui régissent les transformations se doivent de conserver certaines quantités (masse, énergie, charge, ...). Cette conservation doit bien sûr se retrouver dans les modèles sensés représenter les phénomènes mis en jeu. C'est pourquoi nous nous intéressons à la propriété de conservation du nombre dans les automates cellulaires.

Dans cette partie, nous considérons que l'alphabet A, sur lequel sont définies les règles locales de J, est un alphabet numérique de la forme {0, 1, ..., s-1} où s est la taille de l'alphabet. Cette hypothèse n'est pas réellement restrictive car tous les résultats que nous présentons se généralisent à un alphabet quelconque muni d'une fonction de valuation φ : A →ℕ.

Soit H un rν-CA sur l'alphabet A, H est dit conservatif sur les configurations finies (FNC) si pour toute configuration c qui contient un nombre fini d'états non-nuls, H(c) contient un nombre fini d'états non-nuls et la somme de ces états est égale dans c et H(c).

∑ i ∈ ℤ

H(c)i =

∑ i ∈ ℤ

ci

Les deux sommes sont bien définies car leur support est en fait fini. On ne peut pas étendre directement cette notion aux configurations ayant un nombre infini d'états non-nuls. A la place, on regarde le rapport des sommes des états sur un cylindre entre une configuration c et son image H(c) et on étudie le comportement asymptotique de ce rapport. Plus précisément, on introduit les quantités suivantes:

µn(c) =

n ∑ i = −n  H(c)i   n ∑ i = −n  ci

m(c) =

liminf n → ∞

µn(c)      M(c) =

limsup n → ∞

µn(c)

On note 0 la configuration dont tous les états sont 0. Alors μ_n(c) est bien définie pour toute configuration c différente de 0 à partir d'un certain rang et donc m(c) et M(c) sont bien définies pour toute configuration différente de 0.

H est dit conservatif (NC) si H( 0 ) = 0 et si, pour toute configuration c différente de 0, m(c) = M(c) = 1.

Théorème 8. Un rν-CA H est NC si et seulement s'il est NFC.

Ce résultat a été montré dans [5] pour les automates cellulaires classiques et nous l'avons généralisé aux rν-CA.

On peut par la suite caractériser les distributions λ de Λ_J qui définissent des rν-CA conservatifs. En fait H_λ sera conservatif si et seulement si tout facteur de taille 2r+1 de λ vérifie une certaine propriété. Autrement dit, H_λ est conservatif si et seulement si λ évite un ensemble de mots de taille 2r+1, donc l'ensemble des distributions de règles de Λ_J qui définissent des rν-CA conservatifs est un sous-shift de type fini. De plus on peut déterminer un ensemble de mots interdits qui définit ce sous-shift.

4.3 Surjectivité

Nous avons réussi à caractériser les distributions de règles qui définissent des rν-CA conservatifs. Suite à ce premier résultat, nous avons cherché à caractériser d'autres propriétés en terme de contraintes sur les distributions. Celle que nous étudions dans cette section est la surjectivité.

Comme l'espace des configurations est compact, on peut montrer que l'ensemble des distributions de règles qui définissent des rν-CA surjectifs est un sous-shift. Pour étudier plus en détail ce sous-shift, on utilise une version modifiée des graphes de De Bruijn sur les CA [4]. Les états de ce graphe sont étiquetés par les mots de A^2r et il y a une flèche de l'état α à l'état β s'il existe des lettres a et b deA et un mot u de A^2r-1 tels que l'étiquette de α est au et l'étiquette de β est ub. Ces flèches sont alors étiquetées par l'ensemble des couples ( c, f ) tels que c = f(aub) pour f dans J.

Voici par exemple le graphe de De Bruijn pour A={0, 1} et J={id, ⊕} où id(x,y,z) = y et ⊕(x,y,z) = x + z (mod 2).

 

Exemple de graphe de De Bruijn.

L'intérêt de ce graphe est de permettre de suivre une configuration et son image par une distribution donnée. Si on considère un chemin biinfini dans le graphe, la suite des états traversés correspond à une configuration c, tandis que la suite des étiquettes des flèches définit une configuration c' et une distribution λ (on choisit un seul couple par flèche, ce qui revient en fait à considérer le graphe comme un multigraphe). On a alors H_λ(c) = c'.

 

Image par un graphe de De Bruijn.

En manipulant ce graphe, on parvient à obtenir un automate fini qui reconnait un langage L tel que L est un langage de mots interdits qui définit le sous-shift des distributions d'automates surjectifs.

Pour reprendre l'exemple précédent, J={id, ⊕}, l'étude montre que le sous-shift des distributions définissant des automates surjectifs est l'ensemble des distributions dans lesquels n'apparaissent pas les mots de la forme id⊕^2k+1id pour tout entier k. C'est à dire le sous-shift pair qui est un exemple typique de sous-shift sofique qui n'est pas de type fini. Avec la méthode qui utilise les graphes de De Bruijn, on construit l'automate suivant pour définir un langage de mots interdits :

 

Automate des mots interdits.

Il est aisé de voir qu'un mot est reconnu par cet automate fini si et seulement s'il contient un facteur de la forme id⊕^2k+1id pour un certain entier k. Le sous-shift défini par ce langage est donc bien le même que celui donné par l'étude pure.

De façon générale, pour tout ensemble de règles J, on peut construire un tel automate. Ceci nous permet de dire que l'ensemble des distributions donnant des rν-CA surjectifs est un sous-shift de type sofique. De plus, nous disposons d'un moyen automatisé pour déterminer un langage de mots interdits.

4.4 Travaux en cours

Des travaux sont en cours pour caractériser les ensembles de distributions qui définissent des rν-CA possédant certaines propriétés. L'injectivité semble pouvoir être caractérisée en utilisant des graphes généralisant les graphes de De Bruijn : les graphes produits [4]. Par ailleurs, nous essayons de caractériser les distributions donnant des automates sensibles pour un ensemble de règles additives dans la continuité des travaux effectués sur les automates cellulaires classiques.

 

Bibliographie

[1]	E. F. Moore : Machine models of self-reproduction. Proceedings of Symposia in Applied Mathematics 14:17−33, 1962.
[2]	J. Myhill : The converse of Moore’s garden-of-Eden theorem. Proceedings of the american mathematical society 14(4):685−686, 1963.
[3]	P. Kůrka : Languages, equicontinuity and attractors in cellular automata. Ergodic Theory and Dynamical Systems 17(2):417−433, 1997.
[4]	B. Durand : Global properties of cellular automata, in E. Goles et S. Martinez : Cellular Automata and Complex Systems, Kluwer, Dordrecht, 1998.
[5]	B. Durand, E. Formenti et Z. Róka : Number-conserving cellular automata I: decidability, Theoretical computer science 299:523−535, 2003.
[6]	P. Kůrka : Topological and symbolic dynamics, vol. 11 of Cours spécialisés. Société mathématique de France, 2003.
[7]	G. Cattaneo, A. Dennunzio, E. Formenti et J. Provillard : Non-uniform cellular automata. Lecture Notes in Computer Science, 5457:302−313, 2009.