Ce problème est aussi connu sous l'appellation de problème de la majorité (majority problem) et a été étudié principalement pour le cas des automates binaires unidimensionnels finis. Différents travaux ont été conduits sur des systèmes bidimensionnels [8], sur des réseaux [53, 20, 43], ou sur des systèmes à états continus que l'on discrétise [31]. On trouvera dans l'article d'état de l'art d'Oliveira un bon aperçu des différents cas qui ont été traités au cours du temps [185].

Ce problème rentre dans la catégorie des problèmes de synthèse de comportement, appelés aussi problèmes inverses. Il fut initialement formulé par Packard [189] comme un moyen de stimuler la communauté de chercheurs qui s'intéresse à l'exploration de grands espaces d'automates cellulaires. Il faut toutefois noter qu'originellement, la recherche est motivée par le problème de savoir s'il existe des règles unidimensionnelles non-ergodiques et robustes au bruit [115].

En 1995, Land et Belew ont donné un résultat-clé : il n'existe pas de règle pouvant classer la densité de manière parfaite [146]. Notons que dans l'article publié dans la revue *Electronic Journal of Probability*, nous avons présenté un théorème plus général et qui s'appuie sur une démonstration plus simple [35].

Fukś fut le premier auteur à penser à utiliser de l'aléa pour résoudre ce problème. Sa solution revient à faire une copie aléatoire d'un des états du voisinage [110]. Le problème de cette règle, analysée formellement ci-dessous, est qu'elle ne produit pas de « force » qui attire un système vers le bon point fixe. Une deuxième étape fut franchie par Schüle et al. qui ont également proposé d'utiliser l'aléa pour résoudre le problème avec l'introduction de la fonction XOR, qui « mélange » les états de manière locale [226]. Ceci permet au système d'arriver à une solution plus rapidement mais la qualité générale reste limitée (cf. ci-dessous).

La construction que nous présentons a pour principe de mélanger deux règles qui tra vaillent en des sens opposés : la règle de majorité a tendance à homogénéiser localement les configurations et à les attirer vers le point fixe le plus « proche » alors que la règle de circu lation a tendance à créer des inhomogénéités en espaçant autant que possible la répartition d'états différents. C'est par un bon dosage des deux règles que l'on parvient à trouver une ré ponse au dilemme qui consiste à aller vers plus d'homogénéité au niveau global (pour aller vers la solution) et vers plus d'hétérogénéité au niveau local (pour rompre l'uniformité).

## 7.1 Formalisation du problème

Dans cette partie, on supposera que $n$ est impair; ceci nous permettra d'éviter de traiter le cas des conditions initiales avec un nombre égal de 0 et de 1.

Pour une fonction globale donnée, soit $T(x)$ la variable aléatoire prenant ses valeurs dans $N \cup \infty$ et définie par :

$$T(x) = \min \{t : x^t \in \{0, 1\}\}.$$

On dira qu'une fonction globale $C$ est un classificateur de la densité si $0$ et $1$ sont ses seuls points fixes et si $T(x)$ est presque sûrement fini pour toute configuration $x \in \mathcal{E}_n$.

On définit l'événement « C classe correctement $x$ » selon : $T(x)$ est fini et $x^{T(x)} = 1$ pour $\rho(x) > 1/2$ et $x^{T(x)} = 0$ pour $\rho(x) < 1/2$, où $\rho(x) = |x|_1/n$ est la densité d'une configuration $x$. La probabilité de bonne classification $B(x)$ d'une configuration $x$ est donc la probabilité que cet événement se réalise.

Afin d'évaluer correctement une règle qui classe la densité, il est nécessaire de bien définir la distribution initiale. On trouve dans la littérature plusieurs types de distributions initiales — et parfois aucune description explicite — et il arrive parfois que des résultats différents soient donnés pour une même règle! (Voir par exemple les ref. [41] et [146]). Dans ce qui suit, on se
<table><caption>TABLE 7.1 – Rappel du code par transitions.</caption><thead><tr><th>A</th><th>B</th><th>C</th><th>D</th><th>E</th><th>F</th><th>G</th><th>H</th></tr></thead><tbody><tr><td>000</td><td>001</td><td>100</td><td>101</td><td>010</td><td>011</td><td>110</td><td>111</td></tr><tr><td>1</td><td>1</td><td>1</td><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

restreindra au cas des configurations initiales choisies de manière uniforme dans l'espace des configurations, ce qui revient à initialiser chaque cellule indépendamment avec équiprobabilité d'être 0 ou 1.

## 7.2 Structure de l'espace des AC probabilistes

On peut décrire l'espace des ACE probabilistes (ACEP) comme un hypercube de dimension 8. Les sommets de cet hypercube sont les 256 automates cellulaires élémentaires. On peut donc considérer l'espace des ACEP comme analogue à $[0, 1]^8$ et munir cet espace de l'opération d'addition et multiplication par un réel.

Soient $k$ ACEP $f_1, \dots, f_k$ et $w_1, \dots, w_k$ des nombres réels dans $[0, 1]$ tels que $\sum_{i=1}^k w_i = 1$, le barycentre des ACEP $(f_i)$ avec les poids $w_i$ est l'ACEP $g$ défini par :

$$ \forall a, b, c \in \{0, 1\}, \ g(a, b, c) = \sum_{i=0}^{k} w_i f_i(a, b, c). $$

Notons que cette définition nous donne deux façons équivalentes d'interpréter le comportement de l'ACEP $g$ : soit avec une table transition classique, soit en disant que pour chaque cellule, de façon indépendante, la règle $f_i$ est appliquée avec la probabilité $w_i$. Ceci sera illustré plus concrètement avec l'examen de règles précises.

L'espace des ACEP peut donc être décrit avec la base des 8 ACE déterministes qui ont une seule transition qui mène à l'état 1 (cf. la définition ci-dessus avec $f(x, y, z)$). Nous pouvons également, en suivant la démarche qui a été proposée au chapitre 1, décrire un ACEP comme le barycentre des 8 ACE qui ont une unique transition active, c'est-à-dire ceux dont le code par transitions est décrit par une unique lettre.

Ces ACE sont $A, B, \dots, H$ (cf. tableau 7.1) et pour tout ACEP $f$, il existe un octuplet $(\omega_A, \omega_B, \dots, \omega_H) \in [0, 1]^8$ tel que : $f = \omega_A \cdot A + \omega_B \cdot B + \dots + \omega_H \cdot H$.

Nous notons cette égalité de manière plus compacte : $f = [\omega_A, \omega_B, \dots, \omega_H]_T$, où l'indice T rappelle les transitions actives.

Notons qu'avec cette notation les opérations de symétrie s'obtiennent de façon analogue au cas déterministe : la symétrie de réflexion s'obtient en permutant les valeurs des probabilités $\omega_B$ et $\omega_C$, d'une part, et $\omega_F$ et $\omega_G$, d'autre part; la symétrie de conjugaison s'obtient en permutant les valeurs des probabilités $\omega_A$ et $\omega_H$, $\omega_B$ et $\omega_G$, $\omega_C$ et $\omega_F$, $\omega_D$ et $\omega_E$.

Pour comparer différentes règles entre elles, on définit $Q_b$ la qualité d'un classificateur C pour une taille $n$ comme la probabilité de réaliser une bonne classification en partant d'une distribution uniforme :

$$ Q_b(n) = \frac{1}{2^n} \sum_{x \in \mathcal{E}_n} B(x). $$
<figure><img src="image_40.png" /><figcaption>FIGURE 7.1 – Diagrammes espace-temps montrant l'évolution de la règle de Fukś. On a pris $n = 25$, $p = 0.48$ et une condition initiale avec huit cellules à l'état 1.</figcaption></figure>

## 7.3 Règles de Fukś et Schüle

Examinons maintenant comment l'utilisation de l'aléa permet de construire des solutions, plus ou moins bonnes. Comme point de départ, considérons la règle proposée par Fukś [110]. Pour $p \in (0, 1/2]$, la règle locale $C_F$ se définit selon la table de transition « classique » :

$$ \begin{array}{lcccccccc} (x, y, z) & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ C_F(x, y, z) & 0 & p & 1-2p & 1-p & p & 2p & 1-p & 1 \end{array} $$

où les valeurs exprimées sont les probabilités de prendre l'état 1. On remarquera que 0 et 1 sont les seuls points fixes.

Avec la notation par transitions, le changement de base expliqué plus haut donne :

$$ \begin{aligned} C_F &= [0, p, p, 2p, 2p, p, p, 0]_T \\ &= p \cdot \text{BDEG} + p \cdot \text{CDEF} + (1-2p) \cdot I \end{aligned} $$

On voit donc que la règle de Fukś peut s'interpréter comme l'application pour chaque cellule de manière indépendante : (a) d'un décalage à gauche (170-BDEG) avec probabilité $p$, (b) d'un décalage à droite (240-CDEF) avec probabilité $p$, et (c) de l'identité avec probabilité $1-2p$ (voir fig. 7.1).

**Théorème 12.** Pour la règle de Fukś $C_F$ avec $p \in (0, 1/2]$, on a :

$$ \forall x \in \mathcal{E}_n, \quad B(x) = \max \{\rho(x), 1-\rho(x)\} \quad \text{et} \quad \mathbb{E}\{T(x)\} \le \frac{|x|_1 (n-|x|_1)}{p}. $$

On reconnaît là un résultat analogue à celui qui avait été présenté pour les règles quadra-tiques avec mise à jour totalement asynchrone (cf. § 1.5, p. 26). La démonstration repose sur le lemme suivant :
**Lemme 7.** Soit $(X_t)$ une suite de variables aléatoires qui représente l'évolution d'un processus de Markov dans $\{0, \dots, m\}$ où $m$ est un entier. Soit $T(x) = \min\{t : X_t = 0 \text{ or } X_t = m\}$ le temps d'absorption du processus.

Si $X_t$ et $\Delta X_{t+1} = X_{t+1} - X_t$ sont tels que :

— $(X_t)$ est une martingale,

— pour $t < T$, $\mathbb{E}\{\Delta X_{t+1}^2 | X_t\} > v$,

alors :

$$ \mathrm{Pr}\{X_T = m\} = \frac{q}{m} $$

et $T$ est presque sûrement fini et vérifie :

$$ \mathbb{E}\{T(x)\} \le \frac{q(m-q)}{v} \le \frac{m^2}{4v} $$

où $q = \mathbb{E}\{X_0\}$.

Le résultat sur $\mathbf{B}(x)$ permet de calculer la qualité du classificateur de Fukś $\mathbf{C}_F$

$$ Q_b(n) = \frac{1}{2} + \frac{1}{2^n} \cdot \left( \frac{n-1}{\frac{n-1}{2}} \right). $$

Concrètement, pour $n = 49$, on a : $Q_b(n) = 0.557$, autrement dit le gain par rapport à un choix purement aléatoire est de moins de 6%. Pour la valeur de référence $n = 149$, ce gain descend à 3,3%. On voit donc que la qualité de classification s'approche très vite du seuil $1/2$ lorsque $n$ grandit.

Le temps moyen de classification est quadratique : $T_b \in \mathcal{O}(n^2)$. Ceci n'est pas une coïncidence, le fait que la règle de Fukś conserve en moyenne la densité induit une convergence qui ne peut pas être plus rapide que le temps quadratique. Comme nous l'avons vu au chapitre 1, ce comportement résulte d'une tendance qu'ont les zones à faire des marches aléatoires non biaisées, ce qui fait que la fusion des zones ne peut s'établir que lorsque deux de ces frontières se rencontrent. On voit là un point important de l'étude des systèmes complexes : des comportements qualitatifs similaires peuvent apparaître, indépendamment des mécanismes microscopiques qui leur donnent naissance.

Passons maintenant à la règle de Schüle $\mathbf{C}_S$. Celle-ci s'exprime, pour $\varepsilon \in (0, 1)$, selon la table de transition suivante :

<table><tr><td>(x, y, z)</td><td>000</td><td>001</td><td>010</td><td>011</td><td>100</td><td>101</td><td>110</td><td>111</td></tr><tr><td>C<sub>S</sub>(x, y, z)</td><td>0</td><td>1 - ε</td><td>1 - ε</td><td>ε</td><td>1 - ε</td><td>ε</td><td>ε</td><td>1</td></tr></table>

Dans la base des transitions actives, on peut également l'écrire :

$$ \begin{aligned} \mathbf{C}_S &= [0, 1 - \varepsilon, 1 - \varepsilon, \varepsilon, 1 - \varepsilon, 1 - \varepsilon, 0]_T \\ &= (1 - \varepsilon) \cdot \mathbf{BCFG} + \varepsilon \cdot \mathbf{DE}. \end{aligned} $$

Cette règle peut donc s'interpréter comme l'application, pour chaque cellule, de manière indépendante, de : (a) la règle du XOR 150-BCFG avec probabilité $1 - \varepsilon$ et (b) la règle de majorité 232-DE avec probabilité $\varepsilon$ (voir fig. 7.2).

On appelle *diploïde* un ACEP qui peut, comme ci-dessus, être décomposé en l'application d'un ACE avec probabilité $p$ et d'un ACE avec probabilité $1 - p$. En 2017, nous avons consacré une étude expérimentale aux diploïdes, en nous concentrant particulièrement sur l'apparition de transitions de phase liées aux variations du taux de mélange $p$ [83].

Il n'est pas aisé de donner une estimation analytique du comportement du système pour toute valeur de $\varepsilon$. Toutefois, pour $\varepsilon = 2/3$, nous pouvons énoncer le résultat suivant :
<figure><img src="image_41.png" /><figcaption>FIGURE 7.2 – Diagrammes espace-temps montrant l'évolution de la règle de $C_S$. On a pris $n = 25$, $\epsilon = 0.75$ et une condition initiale avec huit cellules à l'état 1.</figcaption></figure>

**Théorème 13.** Pour la règle de Schüle $C_S$ avec $\epsilon = 2/3$, on a :

$$ \forall x \in \mathcal{E}_n, \quad \mathcal{B}(x) = \max \{\rho(x), 1 - \rho(x)\} \quad \text{et} \quad \mathbb{E}\{T(x)\} \le \frac{|x|_1(n - |x|_1)}{\epsilon(1 - \epsilon)}. $$

Par conséquent, pour la valeur $\epsilon = 2/3$, la qualité de cette règle est identique à celle de Fukś. Par ailleurs, son temps moyen de classification $T_b$ est du même ordre de grandeur : $T_b \in \mathcal{O}(n^2)$. Il est à noter que Schüle avait obtenu ce résultat en faisant appel à l'approximation du champ moyen [226] et que nous avons confirmé ce résultat en l'obtenant de façon exacte à l'aide des techniques de martingales exposées plus haut [76].

Pour ne pas alourdir ce document, nous ne développons pas davantage l'analyse de cette règle. Notons toutefois les conjectures suivantes [76] :

- Pour $\epsilon < 2/3$, le système est métastable. Informellement, cela signifie qu'il n'a pas tendance à être attiré vers un des deux points fixes. Formellement, on peut tenter de démontrer que le temps de convergence croît de manière exponentielle avec la taille de l'anneau.

- Pour $\epsilon > 2/3$, la probabilité de bonne classification d'une configuration $x$ de densité inférieure à $1/2$ est proche de $1 - \rho^*$, où $\rho^*$ est la densité de la configuration obtenue en itérant la règle de majorité sur $x$ de façon synchrone. Le cas où la densité est supérieur à $1/2$ est symétrique.

En somme, cette combinaison, si elle améliore les choses par rapport à la règle Fukś (pour $\epsilon > 2/3$), ne permet pas encore de saut qualitatif. Les mesures expérimentales de la qualité et du temps de convergence en fonction du paramètre $\epsilon$ sont données sur la figure 7.4.
<figure><img src="image_42.png" /><figcaption>FIGURE 7.3 – Diagrammes espace-temps montrant l'évolution de la règle de $C_{CM}$. On a pris $n = 25$, $\eta = 0.30$ et une condition initiale avec huit cellules à l'état 1.</figcaption></figure>

## 7.4 Règle de Circulation-Majorité

Nous arrivons maintenant au résultat principal de ce chapitre. La règle dite de circulation-majorité est le diploïde formé du couple ACE 184 (circulation) et ACE 232 (majorité). Notons que l'association de ces deux règles avait déjà été considérée par Fukś qui a montré que pour des anneaux de taille $n$ donnée, on obtient une classification parfaite en appliquant d'abord la circulation pendant $n/2$ pas de temps puis la majorité pendant $n/2$ pas de temps [109]<fnref n="18" />.

Pour $\eta \in (0, 1]$, considérons la règle $C_{CM}$ définie avec le tableau suivant :

<table><tr><td>(x, y, z)</td><td>000</td><td>001</td><td>010</td><td>011</td><td>100</td><td>101</td><td>110</td><td>111</td></tr><tr><td>C<sub>CM</sub>(x, y, z)</td><td>0</td><td>0</td><td>0</td><td>1</td><td>1 - η</td><td>1</td><td>η</td><td>1</td></tr></table>

Avec les transitions actives, il vient :

$$ 
\begin{aligned}
C_{CM} &= [0, 0, 1 - \eta, 1, 1, 0, 1 - \eta, 0]_{T} \\
&= \eta \cdot DE + (1 - \eta) \cdot CDEG.
\end{aligned}
 $$

Pour $\eta \in (0, 1)$, l'effet de la règle revient donc à appliquer pour chaque cellule et de manière indépendante : (a) la règle dite de « circulation » 184-CDEG avec probabilité $1 - \eta$ et (b) la règle de majorité 232-DE avec probabilité $\eta$. Nous appelons donc cette règle la règle de Circulation-Majorité. Son comportement peut être observé sur la figure 7.3.

La propriété centrale de cette règle est qu'il existe des configurations qui peuvent être clas- sées sans erreur, et ce en dépit de l'aléa des transitions.

**Définition 6.** Pour un état $q \in \{0, 1\}$, on dira qu'une configuration $x$ est un q-archipel si toutes les cellules à l'état $q$ sont isolées, c'est-à-dire, si $x$ ne contient pas deux cellules adjacentes à l'état $q$.

<footnote n="18">18. Cependant, nous n'avions pas connaissance de ce résultat au moment où nous avons étudié la règle de circulation-majorité.</footnote>
**Lemme 8.** Toute configuration qui est archipel est bien classée avec probabilité 1. Pour un réglage $\eta$ de la règle de majorité-circulation, une configuration $x$ qui est $q$-archipel avec $k$ cellules à l'état $q$ a un temps de convergence moyen de $\mathbb{E}\{T(x)\} \le k/\eta$.

Pour une configuration donnée, nous pouvons donc nous assurer de son bon classement sous la condition qu'elle atteigne un archipel de bonne densité, c'est-à-dire un archipel dont la densité est respectivement inférieure ou supérieure à 1/2 selon que la densité de configuration de départ était supérieure ou inférieure à 1/2. C'est l'objet du lemme suivant.

**Lemme 9.** Pour tout $\varepsilon \in [0, 1)$, il existe un réglage $\eta$ de la règle de circulation-majorité $C_{CM}$ tel que toute configuration $x \in \mathcal{E}_n$ atteindra un archipel de bonne densité avec une probabilité supérieure à $1 - \varepsilon$.

On peut facilement s'assurer du résultat par un argument « direct » : on sait que si pendant $n/2$ pas de temps la règle de circulation est appliquée de manière synchrone, toute configuration évolue vers un archipel de bonne densité. Pour $\eta \to 0$, la probabilité de cet événement tend vers 1, ce qui assure la validité du lemme.

Notons cependant que la règle serait de peu d'utilité si la classification était faussée dès que la densité évolue dans le mauvais sens. En pratique, on peut dire que l'irruption de quelques « erreurs », lorsque la majorité s'applique en éloignant la configuration du bon point fixe, ne perturbe pas trop le processus. C'est un problème ouvert que de savoir évaluer l'effet de ces erreurs.

Ces deux lemmes combinés nous permettent dès lors d'énoncer notre théorème :

**Théorème 14.** Pour une probabilité $p \in [0, 1)$ fixée à l'avance et une taille d'anneau $n$ fixée, il existe une valeur de $\eta$ (suffisamment petite) telle que pour la règle de Circulation-Majorité $C_{CM}$, la probabilité de bonne classification de toute configuration soit supérieure à $p : \forall x \in \mathcal{E}_n, B(x) \ge p$.

Ce théorème montre que l'on peut obtenir une qualité aussi haute que l'on souhaite : on a $Q_b(n) \to 1$ pour $\eta \to 0$. Les mesures expérimentales de la qualité et du temps de convergence en fonction du paramètre $\eta$ sont données sur la figure 7.4. Dans la figure 7.5 permet quant à elle de se rendre expérimentalement compte de la différence entre un temps de convergence quadratique pour les règles de Fuk's et de Schüle et une convergence linéaire avec la règle de Circulation-Majorité.

## 7.5 Structures infinies

Dans notre travail réalisé avec Ana Bušić, Irène Marcovici et Jean Mairesse, nous avons étudié le problème de la classification sur différents espaces infinis : lignes, grilles et arbres [35]. En ce qui concerne les grilles finies, nous avons montré qu'il n'existe pas de règle, déterministe ou probabiliste, permettant de classer parfaitement la densité, et ce, quelle que soit la dimension de la grille. Ce résultat généralise le théorème établi par Land et Belew en 1995 [146].

On aboutit ainsi à une situation paradoxale : en une dimension, on sait construire des solutions arbitrairement bonnes pour le cas fini mais on ne sait pas résoudre le cas infini. En deux dimensions le cas infini est simple à résoudre, mais le cas fini est redoutablement difficile [93].

Les questions les plus importantes de ce chapitre émergent assez clairement.

**Question 20.** **Cas unidimensionnel infini.** Existe-t-il un automate cellulaire qui classe la densité sur la ligne bi-infinie $\mathbb{Z}$ lorsque le système est initialisé de façon indépendante uniforme avec probabilité $p$ d'être à l'état 0 et $1 - p$ d'être à l'état 1 ?
<figure><img src="image_43.png" /><figcaption>FIGURE 7.4 – Qualité de classification $Q_b$ et temps de convergence $T_b$ pour une taille d'anneau de $n = 149$. Les moyennes sont obtenues avec 10 000 échantillons. (haut) règle de Fukś; (milieu) règle de Schüle ; (bas) règle de Circulation-Majorité.</figcaption></figure>
<figure><img src="image_44.png" /><figcaption>FIGURE 7.5 – Temps de convergence $T_b$ en fonction de la taille de l’anneau $n$ pour différents réglages des règles $C_S$ and $C_{CM}$. insert: mêmes données, représentées avec une échelle logarithmique</figcaption></figure>

**Question 21.** *Cas bidimensionnel fini.* Existe-t-il un automate cellulaire synchrone ou asynchrone qui approche la solution parfaite d’aussi près que l’on souhaite sur des grilles toriques, c’est-à-dire avec des conditions aux bords périodiques ?

**Question 22.** *Cas bidimensionnel infini bruité.* Sur $\mathbb{Z}$, quelles sont les capacités de correction de la règle circulation-majorité dans le cas où l'évolution est bruitée, c'est-à-dire soumise à un changement d'état aléatoire avec une certaine probabilité ? En particulier, le système est-il ergodique<sup>19</sup> pour un bruit très petit ou permet-il de fournir un contre-exemple à la conjecture des taux positifs [156] ?

<footnote n="19">19. Intuitivement, un système est ergodique s’il a tendance à « oublier » sa condition initiale.</footnote>
# Problème de la synchronisation globale

Nous présentons dans ce chapitre notre travail sur le problème de la synchronisation globale, d'abord présenté en conférence en 2015 [79] puis publié dans une version longue en revue en 2019 [86]. Ceci permettra de présenter un exemple où les effets de l'aléa sont peut-être en-core plus spectaculaires que dans le chapitre précédent. En effet, nous verrons que si d'après le théorème de Richard-Redeker, il n'existe pas de solution déterministe, presque toutes les règles stochastiques sont des solutions. Il n'en demeure pas moins que seules un nombre res-treint de ces solutions est efficace, dans le sens où leur temps de convergence est polynomial. Nous estimons ce temps de convergence à l'aide des techniques analytiques présentées dans les chapitres précédents de ce mémoire et montrons qu'il existe des solutions quadratiques et peut-être pas de solutions linéaires.

La première mise à jour (scientifique) du phénomène de synchronisation mutuelle est attribuée à HUYGHENS (1629-1695). Celui-ci cherchait à construire des horloges qui soient suffisamment précises pour permettre aux marins de mesurer la longitude. Il fallait en particulier que de telles horloges puissent être embarquées à bord des navires et ne pas se dérégler en dépit des secousses qu'elles auraient à subir.

Dans leur monographie sur la synchronisation, Pikovsky et al. racontent que dans une lettre à son père datée de février 1665, Huyghens dit avoir observé que deux horloges à balancier qui étaient suspendues à un mur avaient tendance à osciller en rythme [195]. Il nomme ce phénomène « la sympathie des horloges », en propose une première explication et suggère que l'on pourrait utiliser cette forme de synchronisation pour stabiliser la pulsation des horloges embarquées à bord des navires.

Dans notre contexte, nous définissons le phénomène d'auto-synchronisation comme le développement d'une forme d'oscillation commune entre des parties d'un système qui sont couplées de manière faible. Le terme auto signale que ce phénomène doit survenir sans l'intervention d'un acteur extérieur. Il est à noter qu'il n'est pas toujours facile de distinguer ce qui est auto-synchronisant de ce qui ne l'est pas car on pourra toujours penser qu'il existe un phénomène extérieur qui a déclenché la synchronisation. Les cas emblématiques de synchronisation sont le clignotement synchrone des lucioles<fnref n="20" />, les applaudissements d'une salle en fin de

<footnote n="20">20. Voir : Bénédicte Salthun-Lassalle, « Le clignotement synchrone des lucioles », *Pour la science*, 2010 et Charlotte Mauger, « Le ballet synchronisé des lucioles modélisé », *Pour la science* n° 543, 2022.</footnote>
concert, ou les mouvements de panique d'une foule. En biologie, citons un cas intéressant et inattendu : des chercheurs ont mis en évidence que les deux flagelles qui sont utilisés par certaines cellules pour « nager » dans un milieu liquide ne sont pas directement couplées mais se synchronisent en fonction des mouvements de la cellule [108].

Dans le domaine des automates cellulaires, le mot synchronisation est souvent évoqué, mais avec des acceptations qui varient d'un auteur à l'autre. Ce terme est par exemple employé pour désigner le phénomène de fusion des trajectoires lorsqu'on part de deux configurations différentes et que l'on force certaines cellules à prendre la même valeur avec une probabilité donnée. On se rapportera aux travaux de Bagnoli et Rechtman pour en savoir plus à ce sujet [15].

Rouqier et Morvan ont également étudié le phénomène de coalescence où l'on observe également que deux trajectoires d'un automate cellulaire asynchrone fusionnent mais cette fois-ci le couplage appliqué consiste simplement à mettre à jour les mêmes cellules dans les deux systèmes étudiés [213]. Il est à noter que ce phénomène avait été constaté par hasard lors de nos expériences sur les automates cellulaires élémentaires $\alpha$-asynchrones [96]. La coalescence a également fait l'objet d'une étude approfondie par Jordina Frances de Mas lors d'un stage de Master que nous avons co-encadré avec Irène Marcovici [107].

Le problème dont nous nous préoccupons ici est différent. Le système évolue sans autre influence que sa règle d'évolution locale et nous cherchons à obtenir un état où toutes les cellules s'accordent pour réaliser une forme de clignotement en rythme.

Le problème de la synchronisation globale a été formulé par Das et al. en 1994 [54]. Il a depuis lors reçu une attention plutôt limitée de la part de la communauté des chercheurs. Ce peu d'intérêt vient probablement du fait que le problème est en apparence facile à résoudre : il est possible d'obtenir des solutions qui parviennent quasiment toujours à synchroniser un ensemble de conditions initiales tirées aléatoirement. Das et al. montrent qu'en utilisant des algorithmes génétiques, on peut « inventer » des règles qui ont une performance proche de 100% pour des tailles d'anneau qui vont jusqu'à 999. En vérité, l'intérêt des auteurs n'était pas tant de parvenir à une bonne performance que de montrer qu'il était possible de trouver des règles exhibant une forme d'émergence, au sens où ces règles parvenaient à établir un consensus sur l'état des cellules en annihilant les défauts qui marquent les différences de synchronisation entre régions synchronisées.

Nous demandons maintenant si des solutions *parfaites* peuvent être obtenues, c'est-à-dire que nous exigeons que *toutes* les conditions initiales convergent vers un état synchronisé et non pas seulement un ensemble de conditions initiales tirées aléatoirement.

## 8.1 Formalisation du problème

Nous quittons le cas binaire et considérons l'ensemble des entiers de 0 à $k-1$ muni de l'addition modulo $k$; l'ensemble des états des cellules est noté $Q = \mathbb{Z}/k\mathbb{Z}$. L'ensemble des *configurations* est $\mathcal{E}_n = Q^\mathcal{L}$ avec $\mathcal{L} = \mathbb{Z}/n\mathbb{Z}$ l'anneau de taille $n$.

Notons $v$ la taille du voisinage d'une règle donnée notée $f : Q^v \to Q$. La fonction d'évolution globale sera notée : $F : \mathcal{E}_n \to \mathcal{E}_n$.

Pour un état $q \in Q$, nous notons $\mathbf{q} = q^\mathcal{L}$ la configuration homogène où toutes les cellules sont à l'état $q$ et $\mathcal{H} = \{\mathbf{q}, q \in Q\}$ l'ensemble des $k$ configurations homogènes.

On dira que la fonction *F synchronise* une configuration $x \in \mathcal{E}_n$ si le système qui a $x$ pour condition initiale atteint une configuration homogène puis visite les configurations de $\mathcal{H}$ dans
l'ordre. Formellement :

$$ \exists q \in Q, t \in \mathbb{N}; F^t(x) = q \text{ and } \forall \tau \in \mathbb{N}, F^{t+\tau} = (q + \tau)^{\mathcal{L}}. $$

On dit que $F$ synchronise la taille $n$ si toutes les configurations de $\mathcal{E}_n$ sont synchronisées.

On notera que dans la formulation choisie pour définir le problème, le système ne peut pas être aidé par des états auxiliaires pour parvenir à la synchronisation. On peut envisager une version du problème, plus facile, où des états hors de $Q$ sont pris par certaines cellules sachant que ces états disparaissent à la fin. Nous avons montré que l'ajout d'états auxiliaires permet de résoudre sans difficulté le problème de la synchronisation globale [86]; nous excluons donc cette possibilité dans la suite.

Le problème de la synchronisation globale se formule donc comme :

Trouver une règle locale $f$ telle que pour toute taille d'anneau $n$, la fonction globale $F$ synchronise $\mathcal{E}_n$.

## 8.2 Propriétés élémentaires

On notera que si une règle est une solution au problème de la synchronisation, alors la règle réfléchie et les règles conjuguées par permutation des états (§ 1.2 p. 14) sont également solutions.

On dit que $f$ est isochromatique$^{21}$ si la règle locale est invariante par permutation des couleurs, c'est-à-dire si pour toute permutation $\pi$ de $Q$,

$$ \forall (q_1, \dots, q_s) \in Q^s, f(\pi(q_1), \dots, \pi(q_s)) = \pi(f(q_1, \dots, q_k)). $$

**Proposition 14.** *Une règle synchronisante ne peut être isochromatique.*

Pour s'en convaincre, on prendra simplement la configuration de taille $k$ contenant tous les états disposés en ordre : $x = (i)_{i \in \{0, k-1\}}$. Supposons que $x$ soit synchronisé sur l'état $q$, c'est-à-dire que la première configuration homogène atteinte soit $q$. Considérons le décalé de $x$, alors par invariance selon le décalage $\sigma(x)$ devrait être synchronisé sur $q$. Par ailleurs, considérons $\pi$ la permutation qui a tout état $q$ associe l'état $q + 1$ (modulo $k$) et $\Pi$ l'opérateur sur les configurations qui applique $\pi$ sur chaque cellule. Alors, la règle étant isochromatique, $\Pi(x)$ doit être synchronisé sur $q + 1$ mais on remarque que $\Pi(x) = \sigma(x)$, ce qui indique que $\Pi(x)$ devrait être synchronisé sur $q$, ce qui mène à une contradiction.

Soit $\sigma$ le décalage à gauche (c'est-à-dire la fonction $\sigma : \mathcal{E}_n \to \mathcal{E}_n$ telle que $\forall i \in \mathcal{L}, \sigma(x)_i = x_{i+1}$). On appelle *rotations* de $x$ l'ensemble des configurations obtenues en appliquant $\sigma$ un nombre de fois arbitraires sur $x$; on note cet ensemble : $[x] = \{\sigma^m(x), m \in \mathbb{N}\} = \{\sigma^m(x), m \in \{0, \dots, n-1\}\}$.

On appelle *configuration translatante* toute configuration dont l'image est une rotation d'elle-même. On remarquera que si $F$ synchronise une configuration non-homogène $x \notin \mathcal{H}$, alors $x$ ne peut être translatante, en particulier $x$ ne peut pas être un point fixe. Il est également clair que $F$ synchronise $x$ implique que $F$ synchronise toutes les rotations de $[x]$.

<footnote n="21">21. En anglais, Salo et Torma appellent cette propriété *color-blind*, c'est-à-dire insensible aux couleurs [219]. Cette appellation est cependant ambiguë car, de façon évidente, la règle « voit » bien les différentes couleurs, mais elle réagit de la même façon aux différentes combinaisons de couleurs...</footnote>
<figure><img src="image_45.png" /><figcaption>FIGURE 8.1 – Graphes de de Bruijn permettant la construction de configurations translatantes pour l'ACE 1 (à gauche) et l'ACE 25 (à droite). Ces configurations sont construites d'après les cycles obtenus en suivant les arêtes en gras.</figcaption></figure>

**Lemme 10** ([207]). *Tout automate cellulaire possède une configuration translatante : ∃n ∈ N*, x ∈ E*n*, i ∈ N; F(x) = σ<sup>i</sup>(x).

La démonstration de cette propriété nous a été donnée par Gaëtan Richard à l'issue de notre exposé sur la synchronisation globale au cours du colloque AUTOMATA 2015. De façon surprenante, Markus Redeker nous a également transmis cette même démonstration par courriel un peu plus tard alors qu'il ne connaissait manifestement pas l'argument de Richard.

L'idée de Richard et Redeker est que pour un automate cellulaire avec un voisinage de taille de v, on peut choisir une chaîne q₁, ..., q_v ∈ Q^v librement et itérer le processus qui consiste à ajouter à cette chaîne le résultat de l'application de f aux v derniers caractères de la chaîne. On tombe alors nécessairement sur un comportement périodique du processus et il suffit d'extraire la partie périodique de la chaîne pour avoir une configuration translatante (avec un décalage de v cellules par pas de temps).

On donne ici une autre présentation de cet argument, strictement équivalente, à l'aide de diagrammes de de Bruijn. Sans trop entrer dans les détails, présentons simplement un exemple de la façon de construire une configuration translatante. On construit le graphe suivant : les sommets sont les huit motifs 000, ..., 111 et chaque sommet xyz possède une unique arête sortante qui le relie au motif yzα avec α = f(x, y, z). On peut ajouter à cette arête l'étiquette α pour simplifier les choses. Ce graphe contient nécessairement un cycle et la configuration translatante est obtenue en lisant les étiquettes des arêtes du cycle.

Le corollaire du Lemme 10 est qu'il n'existe pas de solution parfaite au problème de la synchronisation globale.

Intéressons-nous maintenant au cas stochastique : dans quelle mesure l'ajout de bruit dans le fonctionnement de la règle locale de l'automate cellulaire peut-elle aider à la résolution du problème ?

8.3 Cas stochastique binaire

Comme pour le problème de la classification de la densité, nous pouvons nous focaliser sur
le cas des plus proches voisins et commencer par examiner le cas binaire. On prendra donc une
fonction de transition locale $\phi : \{0, 1\}^3 \to [0, 1]$, qui donne la probabilité d'être mis à jour à 1 pour un voisinage donné.

Pour une configuration initiale $x$, l'évolution du système est décrite$^{22}$ par le processus stochastique $(x^t)_{t \in \mathbb{N}}$. La suite de variable aléatoires $(x^t)$ se définit récursivement selon : $x^0 = x$ et

$$ \forall t \in \mathbb{N}, \forall i \in \mathcal{L}, x_i^{t+1} = \mathcal{B}(\phi(x_{i-1}^t, x_i^t, x_{i+1}^t)), \quad (8.1) $$

où $\mathcal{B}(p)$ décrit une loi de Bernoulli de paramètre $p$.

Définissons maintenant le problème dans le cadre probabiliste. La condition de synchronisation se traduit localement par $\phi(0, 0, 0) = 1$ et $\phi(1, 1, 1) = 0$. Pour une règle qui satisfait cette condition, pour une configuration initiale $x \in \mathcal{E}_n$, on définit le temps de synchronisation $T(x)$ comme la variable aléatoire qui compte le nombre d'étapes nécessaires pour atteindre un état homogène : $T(x) = \min\{t, x^t \in \{0, 1\}\}$.

Le temps moyen de synchronisation de $x$ est noté $\mathbb{E}\{T(x)\}$. Pour une taille d'anneau $n$, on définit le *pire temps moyen de synchronisation* (PTMS) selon :

$$ \text{PTMS}(n) = \max_{x \in \mathcal{E}_n} \mathbb{E}\{T(x)\}, $$

On dit qu'un automate cellulaire probabiliste $f$ synchronise la taille $n$ si PTMS($n$) est fini. On dira de même que $f$ est une solution au problème de la synchronisation globale si $f$ synchronise toutes les tailles d'anneau $n \in \mathbb{N}$.

Examinons maintenant comment construire une solution. Nous définissons $\phi$ avec les variables : $p_0 = \phi(0, 0, 0)$, $p_1 = \phi(0, 0, 1)$, ..., $p_7 = \phi(1, 1, 1)$.

**Théorème 15 ([86]).** Soit $\phi$ un ECA stochastique tel que $p_0 = 1$, $p_7 = 0$ et $\forall i \in \{1, \dots, 6\}$, $p_i \in ]0, 1[$, alors $\phi$ est une solution au problème de la synchronisation globale.

La démonstration est assez facile à établir. On remarque que les configurations 0 et 1 sont des états récurrents (§ 2.1 p. 34); ils correspondent à l'état synchronisé du système. Toutes les autres configurations sont des états transients du système : pour un anneau de taille $n$, on peut en effet montrer qu'à partir de chaque état il existe une probabilité non nulle d'atteindre 0 (ou 1) en moins de $n$ pas de temps [86].

Ceci ne règle pas tout pour autant. En effet, on aimerait que le système ne converge pas par pur hasard sur les états synchronisés. On peut formaliser cette exigence en disant que l'on souhaite que la convergence ait lieu en temps polynomial en la taille de l'anneau. Un temps linéaire en $n$ serait bien sûr idéal – on ne peut guère espérer mieux – mais nous allons voir que contrairement au cas de la classification de la densité, cela semble hors d'atteinte...

**Théorème 16.** For $p \in ]0, 1/2[$, soit l'ACE stochastique $\phi$ défini selon :

$$ \phi(x, y, z) = 1 - (p \cdot x + (1 - 2p) \cdot y + p \cdot z). \quad (8.2) $$

$\phi$ est une solution au problème de la synchronisation globale et on a PTMS($n) \in \mathcal{O}(n^2)$.

Pour démontrer que la convergence est quadratique, nous avons montré qu'on pouvait se ramener à l'observation d'un système « stroboscopique » où l'on applique un opérateur d'inversion des configurations un temps sur deux [86]. On observe alors que les frontières des

<footnote n="22">22. On notera que la définition ci-dessus est plus une caractérisation qu'une définition en bonne et due forme. Comme mentionné plus haut, les lecteurs qui souhaitent avoir accès à une définition plus rigoureuse des automates cellulaires probabilistes peuvent se rapporter à un article de Marcovici et Mairesse [162].</footnote>
<figure><img src="image_46.png" /><figcaption>FIGURE 8.2 – (gauche) Diagramme espace-temps de $\phi_k$ pour $k = 3$. (droite) : même évolution mais sans appliquer l'opérateur $\mathbb{S}$ dans la règle de transition : la règle consiste devient une simple copie d'un voisin choisi aléatoirement. Les trois couleurs codent les états 0,1,2. (La règle est isochromatique.)</figcaption></figure>

différentes zones synchronisées suivent une marche aléatoire non biaisée et que ces frontières s'annihilent lorsqu'elles se rencontrent. On a alors exactement le comportement de la règle de Fukś mentionnée ci-dessus (voir le § 7.3), ce qui nous donne un temps de convergence quadratique. Cette opération est illustrée sur la figure 8.2 où l'on représente le déroulement « normal » de la règle à gauche et le déroulement modifié à droite.

## 8.4 Généralisation au cas multicolore

**Théorème 17.** Soit $\phi_k$ la règle locale stochastique définie par :

$$ \forall (x, y, z) \in Q^3, \phi_k(x, y, z) = U(\{x, y, z\}) + 1, $$

où $U(E)$ est la variable aléatoire de choix uniforme dans $E$. Cette règle est une solution au problème de la synchronisation globale et on a : PTMS($n$) $\in \mathcal{O}(n^2)$.

L'obtention du temps quadratique n'est pas aussi simple que dans le cas binaire. On peut bien sûr faire la même opération de suppression du décalage d'état (effet du +1 dans la fonction de transition locale), mais on a alors un processus où chaque zone peut être assignée à une couleur. On peut penser à différentes techniques pour se ramener au cas précédent; notre choix a été d'adapter le lemme de convergence quadratique.

**Lemme 11.** Soient $n$ et $k$ deux entiers strictement positifs et soient $k$ processus stochastiques $(X_1^t), \dots, (X_k^t)$, à valeurs dans $\{0, \dots, n\}$. Soit $F_t$ une filtration adaptée à ces processus$^{23}$. Le temps d'absorption du processus est défini par $T = \min\{t \in \mathbb{N} ; \exists i \in \{1, \dots, k\}, X_i^t = n\}$.

Si les processus sont des martingales, c'est-à-dire que chaque $(X_i^t)$ vérifie :

$$ \forall i \in \{1, \dots, k\}, \forall t \in \mathbb{N}; \mathbb{E}\{X_i^{t+1} | \mathcal{F}_t\} = X_i^t, $$

et s'il existe une constante $\epsilon$ telle que :

$$ \forall t < T, \exists i \in \{1, \dots, k\}; \mathbb{E}\{(X_i^{t+1} - X_i^t)^2 | \mathcal{F}_t\} \ge \epsilon, \text{ alors} $$

$$ \mathbb{E}\{T\} \le n^2/\epsilon. $$

<footnote n="23">23. Informellement, cela signifie que la seule information dont on dispose pour conditionner les variables aléatoires est la connaissance des valeurs de ces processus jusqu'au temps $t$.</footnote>
On reconnaît là une simple adaptation du lemme de convergence en temps quadratique vu plus haut (partie 7, p. 89).

En somme, les solutions fournies plus haut donnent une illustration assez éloquente de l'utilisation de l'aléa pour la résolution de problèmes inverses : alors qu'il n'existe aucune solution déterministe, construire des solutions stochastiques « parfaites » n'est pas si difficile. Les techniques analytiques nous permettent d'estimer le temps de convergence moyen et montrer qu'en une dimension des convergences quadratiques sont obtenues en mélangeant deux ACE simples (c'est une autre règle diploïde).

Nous terminons en demandant :

**Question 23.** Existe-t-il une solution qui converge plus rapidement qu'avec un temps quadratique ?

Nous conjecturons qu'une telle règle n'existe pas, du moins pas dans le cas binaire. En effet, nous pensons que pour faire mieux que le résultat obtenu avec des marches aléatoires non biaisées, il faudrait, justement, biaiser le sens marches aléatoires. Cependant, l'effet du clignotement serait d'annuler le biais introduit au pas suivant car les couleurs sont alors inversées... Formaliser cette intuition et construire une démonstration reste néanmoins difficile à ce stade.
# Modèle bio-inspiré pour le problème du regroupement décentralisé

Ce chapitre présente les travaux qui ont été au centre du projet AMYBIA [71]24, et notamment du post-doc de Nikolaos Vlassopolous [100, 248, 249], dont nous avons été l'encadrant de 2010 à 2012. Bien plus tard, en 2020, le stage de Master 2 d'Amaury Saint-Jore nous a permis de retravailler sur ce modèle en donnant un exemple d'utilisation du modèle bio-inspiré à des fins de classification de données [218].

## 9.1 Présentation du problème et des travaux reliés

Dans ce chapitre, nous examinons quels sont les ingrédients minimaux permettant à un ensemble d'agents évoluant sur une grille de se regrouper de manière décentralisée, c'est-à-dire sans chef et sans distinction de rôle entre ces agents.

Supposons donc que des robots soient initialement jetés au hasard dans un environnement hostile. Ils cherchent à se regrouper et à former un ensemble compact. Pour plus de commodité, on supposera qu'ils évoluent dans un espace discret, un automate cellulaire bidimensionnel, et qu'ils doivent donc s'entendre pour se regrouper dans une zone donnée de cette grille. La difficulté est qu'ils n'ont aucune carte à disposition ni même de boussole pour s'orienter, de plus, ils ne perçoivent que l'état de la cellule de la grille où ils sont et celui des cellules environnantes. La seule bonne nouvelle est qu'ils peuvent changer les états de la cellule où ils se trouvent et comme l'environnement est un automate cellulaire, celui-ci peut relayer l'information de proche en proche. Dans ces conditions, comment faire pour que les robots se regroupent ? Quelles sont les conditions les plus simples qui permettent de réaliser un tel regroupement ?

Un des premiers travaux à s'intéresser au problème de contrôle des robots pour former des ensembles compacts est l'article de Sugihara et Suzuki [236]. Leurs robots n'ont aucune limitation de perception, ce qui leur permet d'utiliser des algorithmes où le groupe vers un « centre

<footnote n="24">24. https://amybia.loria.fr/</footnote>
<figure><img src="image_47.png" /><figcaption>FIGURE 9.1 – Cycle de vie de *Dictyostelium*. Crédits: M.J. Grimson & R.L. Blanton, Biological Sciences Electron Microscopy Laboratory, Texas Tech University. Les images montrent la transformation à partir d'un état de « limace » (*slug*) (en bas à gauche) jusqu'à celui de corps fructifère (en haut à droite).</figcaption></figure>

de gravité » et s'assurer que les liens de visibilité ne sont pas rompus. D'autres travaux ont par la suite considéré des hypothèses plus restrictives, notamment une visibilité limitée [11]. Notons que dans notre travail, la visibilité des agents n'est pas une contrainte puisque les agents communiquent par l'intermédiaire de l'environnement, c'est-à-dire que, pour reprendre le néologisme forgé par Grassé en 1959, les agents se coordonnent par un mécanisme de *stigmergie*<fnref n="25" />.

On trouvera dans les travaux de Flocchini [105, 104] et Prencipe [196] des développements théoriques intéressants sur une version du problème où les agents évoluent sur un plan continu et doivent se retrouver *exactement* sur le même point. La thèse de doctorat de Gauci est également un bon point d'entrée dans la littérature des systèmes de robotique en essaim où, point important, le traitement de l'information est réduit à son strict minimum [121].

Le problème du regroupement décentralisé a une certaine parenté avec le problème de l'élection d'un chef (*leader election problem*) introduit par Smith en 1971 [231]. Dans ce problème, toutes les cellules d'un automate cellulaire sont dans un même état et l'objectif est d'atteindre un état où une cellule unique est dans un état distingué. On notera que nous pourrions résoudre le problème du regroupement décentralisé en résolvant d'abord le problème de l'élection d'un chef, puis faire en sorte que tous les « subordonnés » rejoignent le chef. Cependant, le problème d'élection de chef n'a pas de solution avec un petit nombre d'états dans le monde des automates cellulaires et il est surtout étudié dans un contexte d'informatique distribuée, dans lequel chaque agent a un identifiant unique et peut ainsi être facilement distingué des autres.

Le modèle que nous présentons ici s'inspire de la biologie, et plus particulièrement du phénomène appelé *chimiotaxie*. Il désigne la capacité de certaines cellules vivantes à s'orienter dans un milieu en fonction de la présence d'une substance chimique. L'étude de ce phénomène à l'aide de modèles informatiques a été initiée dans les années 1970 et s'est poursuivie depuis sans discontinuer [140, 131]. L'utilisation de modèles où l'espace est continu et où les cellules sont modélisées par un simple point pose des problèmes, par exemple lorsque toutes les cellules ont tendance à se concentrer dans une zone de plus en plus resserrée (les équations font

<footnote n="25">25. Du Grec στίγμα, piqûre, signe, dérivé du verbe στίζω, et de ἔργον (le travail).</footnote>
apparaître une singularité) [188, 180]. Ici, nous n'aurons pas ce type d'obstacle puisque nous travaillerons sur une grille discrète, et il y sera plus simple d'y imposer des contraintes d'occupations de l'espace (une ou plusieurs amibes par cellule de la grille). Ceci explique peut-être que l'on plusieurs modèles biologiques où la préférence est donnée à un espace discret plutôt que continu [230, 59].

## 9.2 Description du modèle

Nous décrivons le modèle en trois étapes : (a) l'environnement, (b) les amibes, (c) les interactions entre environnement et amibes.

<figure><img src="image_48.png" /><figcaption>FIGURE 9.2 – Règle de transition du modèle de la couche d'environnement (modèle de Greenberg-Hastings).</figcaption></figure>

L'ensemble des états des cellules est $\{0, ..., M\}$ : l'état 0 est l'état neutre, l'état M est l'état excité, les états de 1 à M − 1 sont des états réfractaires. L'évolution d'une cellule est représentée sur la Fig. 9.2 et se décrit comme suit :

* Une cellule neutre qui a au moins une cellule excitée autour d'elle devient excitée avec probabilité $p_T$, sinon elle reste neutre.

* Une cellule excitée devient réfractaire de niveau M − 1.

* Une cellule réfractaire décrémente son état jusqu'à devenir neutre (0).

Décrivons maintenant les mouvements des amibes. On dira qu'une cellule est *vide* si elle ne contient pas d'amibe et *non saturée* si elle est vide ou contient une unique amibe. Les règles de déplacement des amibes s'énoncent alors comme suit :

* Avec probabilité $p_A$, se déplacer sur une cellule voisine non saturée.

* S'il y a une ou plusieurs cellules excitées non saturées parmi les voisines, se déplacer sur l'une des cellules, en la choisissant de manière aléatoire uniforme.

* Sinon, rester sur la même cellule.

La probabilité $p_A$ a donc pour but de créer un bruit sur le mouvement des amibes, on l'appellera taux d'agitation.

Notons qu'à chaque pas de temps, une seule amibe est autorisée à se déplacer à partir d'une cellule source donnée. D'autre part, une cellule qui contient deux amibes ou plus est saturée et ne peut recevoir d'autre amibe$^{26}$ Ces règles, qui sont assez arbitraires, visent simplement à limiter de trop grandes concentrations d'amibes dans une même région sans pour autant trop

<footnote n="26">26. Comme les déplacements sont synchrones, une cellule peut donc contenir plus de deux amibes, dans le cas où, au même pas temps, elle reçoit une amibe de la part de plus de deux cellules voisines.</footnote>
gêner le mouvement des amibes. Notons que nous aurions pu mettre en place un mécanisme de résolution de conflit plus complexe, comme dans le cas des turmites (cf. chap. 6, mais nous pensons cela aurait compliqué la description du modèle sans nécessairement le changer de manière significative.

Passons à la formalisation de ce modèle dans le langage des systèmes dynamiques discrets.

La grille sera finie $\mathcal{L} = \{1, \dots, m\} \times \{1, \dots, n\}$ ou torique $\mathcal{L} = (\mathbb{Z}/m\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z})$. Notons $A_c^t$ le nombre d'amibes contenues dans une cellule $c \in \mathcal{L}$ au temps $t$.

Pour une cellule $c$ de voisinage $\mathcal{N}_c$, notons $E_c^t$ l'ensemble des cellules excitées au temps $t$: $E_c^t = \{c' \in \mathcal{N}_c | \sigma_{c'}^t = M\}$.

On rappelle que l'on note $\mathcal{B}(\alpha)$ une variable aléatoire de Bernoulli de paramètre $\alpha$. Pour exprimer l'évolution de la couche automate cellulaire, nous écrivons :

$$ \sigma_c^{t+1} = \begin{cases} M & \text{si } \sigma_c^t = 0 \\ \sigma_c^t - 1 & \text{et } [|E_c^t| > 0 \text{ ou } (A_c^t > 0 \text{ et } \mathcal{B}(\lambda) = 1)] \\ 0 & \text{sinon.} \end{cases} \quad (R1) $$

$$ (R1) $$

$$ (R2) $$

$$ (R3) $$

On reconnaît là une modification de modèle de Greenberg-Hastings [125]. Cette règle (R1) dit qu'une cellule devient excitée si elle reçoit une excitation, qui peut provenir soit d'une cellule voisine soit, avec probabilité $\lambda$, d'une amibe qu'elle contient.

Pour modéliser les mouvements des amibes, posons $\tilde{N}_c^t$ et $\tilde{E}_c^t$ comme étant respectivement l'ensemble des cellules non-saturées et l'ensemble des cellules excitées non-saturées dans le voisinage d'une cellule $c$ au temps $t$. Le déplacement d'une amibe $c$ dans une cellule cible $\Delta_c^t$ s'écrit :

$$ \text{si } \mathcal{B}(p_A) = 1 \quad \text{alors } \Delta_c^t = \mathcal{U}[\tilde{N}_c^t] \quad (R4) $$

$$ \text{sinon si } \sigma_c^t = 0 \text{ et } |\tilde{E}_c^t| > 0 \quad \text{alors } \Delta_c^t = \mathcal{U}[\tilde{E}_c^t] \quad (R5) $$

$$ \text{sinon } \Delta_c^t = \emptyset, \quad (R6) $$

où $\mathcal{U}(E)$ représente la variable aléatoire qui choisit de manière uniforme un élément dans un ensemble $E$ et où $\Delta_c^t = \emptyset$ signifie qu'il n'y a pas de mouvement.

Le nombre d'amibes contenues dans une cellule $c$ est donc mis à jour selon :

$$ A_c^{t+1} = A_c^t + |\{c' \in \mathcal{L} : \Delta_{c'}^t = c\}| - |\{\Delta_c^t\}|. $$

On ne manquera pas de remarquer qu'une conséquence de ces règles est qu'une amibe n'est pas attirée par les ondes de réaction-diffusion qu'elle émet.

## 9.3 Observation du phénomène d'agrégation

Pour découvrir la dynamique de ce modèle, on commencera par considérer le cas où l'agitation des amibes est nulle $p_A = 0$: ceci signifie que l'aléa n'intervient que dans les moments où les amibes émettent une onde.

### 9.3.1 Formation de foyers et effet de pacemaker

Examinons ce qui se produit pour un taux d'émission fixé arbitrairement à $\lambda = 0.01$. Nous fixons la densité initiale à $d_{\text{ini}} = 10\%$, c'est-à-dire que chaque cellule a initialement une probabilité de 0.1 de contenir une (et unique) amibe. Ces conditions sont en accord avec celles choisies
<figure><img src="image_49.png" /><figcaption>FIGURE 9.3 – Trois pas de temps montrant une évolution avec deux amibes (cercles). Les états excité, réfractaire et neutre sont respectivement représentés en gris, en hachuré et en blanc. L'amibe de gauche se déplace aléatoirement sur la figure de gauche et elle suit un front d'excitation sur le diagramme du milieu.</figcaption></figure>

<figure><img src="image_50.png" /><figcaption>FIGURE 9.4 – Formation d'un pacemaker.</figcaption></figure>
<figure><img src="image_51.png" /><figcaption>FIGURE 9.5 – Temps d'agrégation en fonction du taux d'émission λ. Échelle logarithmique pour l'axe des abscisses. La taille de la grille est de 150 × 100. Reproduit de la ref. [71]. Les boites indiquent les premier et troisième quartiles ; les traits indiquent les valeurs minimales et maximums observées pour un échatillon de taille 50.</figcaption></figure>

par d'autres auteurs [6]. Dans la suite, on travaille avec une grille finie et des conditions aux
bords non périodiques; ceci dit, les observations sont également valides sur une grille torique.

La figure 9.4 montre l'évolution du système : un foyer compact se forme en quelques centaines de pas, puis se met à émettre des ondes avec une bonne régularité. Le regroupement est obtenu de façon rapide.

La figure 9.5 présente une évaluation de la vitesse de regroupement en fonction du taux d'émission λ. Pour quantifier le phénomène de regroupement, nous mesurons le temps que met le processus pour être contenu dans une boîte dont la surface correspond à 1/4 de la surface totale de la grille. En effet, pour de telle valeur du ratio, nous ne sommes plus très loin de former un groupe compact et connexe. Les simulations montrent l'existence d'une valeur optimale du taux d'émission λ*. On remarque que les valeurs du temps d'agrégation restent proches de la valeur minimale sur une large plage de valeurs, ce qui montre que le réglage de λ peut se faire de manière approximative sans que la dynamique ne soit trop ralentie.

On peut facilement comprendre l'existence d'un temps d'agrégation optimal par le raison-
nement pur. En effet, dans le cas limite où l'on fixe λ = 1, les amibes tentent d'émettre une onde
à chaque pas de temps et se trouvent face à un modèle quasiment déterministe. Cependant,
les amibes sont statiques car les ondes qu'elles émettent ne peuvent atteindre d'autres amibes
puisque les ondes de réaction-diffusion se propagent et s'annulent lorsqu'elles se rencontrent
frontalement, c'est-à-dire avec des sens de propagation opposés. De même, pour l'autre cas
limite, quand λ tend vers 0, le phénomène d'agrégation se voit d'autant plus ralenti que λ est
petit car les ondes sont de moins en moins émises. En supposant que le temps d'agrégation
<figure><img src="image_52.png" /><figcaption>FIGURE 9.6 – Regroupement avec $p_A = 0.1$ et $\lambda = 0.01$.</figcaption></figure>

moyen est une fonction continue de $\lambda$, on voit donc qu'il existe un $\lambda$ optimal qui minimise le temps d'agrégation.

## 9.3.2 Explications de la dynamique du modèle

Expérimentalement, on observe que pour des valeurs de $\lambda$ plus petites que $\lambda^*$, le processus de convergence est assez « fluide » : les amibes s'attirent en formant un groupe relativement homogène, et celui-ci devient de plus en plus compact à mesure que le temps passe. En revanche, pour un taux d'émission $\lambda$ plus grand que $\lambda^*$, un phénomène nouveau apparaît : des groupes stables apparaissent et ces groupes se « combattent » jusqu'à ce qu'un groupe « absorbe » un autre groupe. Ce phénomène d'absorption résulte lui-même d'un autre processus émergent : les groupes formés ont tendance à émettre des ondes de manière régulière, la probabilité d'émission d'une onde par un groupe augmentant avec le nombre d'amibes qu'il contient.

Pour comprendre ce phénomène de lutte entre groupes, observons en pensée ce qu'il se produit avec deux groupes seulement, A et B, en supposant que la taille de A est légèrement supérieure à celle de B. Lorsque les ondes émises par ces deux groupes se rencontrent, elles s'annulent et ne se traversent pas. Il en résulte la formation d'un *front d'excitation* qui délimite les *zones d'influence* de chaque groupe. Ce front avance ou recule selon les aléas des temps d'émission des amibes mais on peut remarquer que comme A est plus grand, il émet des ondes de manière plus régulière et il a donc tendance à faire déplacer le front dans la direction de B et donc à étendre sa *zone d'influence*. Lorsque sa zone d'influence touche le groupe B, les amibes de ce groupe ont tendance à « migrer » vers A jusqu'à atteindre les amibes de A et fusionner avec elles. Nous avons donc là un exemple manifeste de phénomène d'émergence : il est difficile de prédire la dynamique du système à la seule vue des règles locales, les groupes, fronts d'excitation et zones d'influence sont des objets d'ordre supérieur qui permettent de mieux comprendre l'évolution du système et, dans une certaine mesure, de faire des prédictions sur la façon dont le regroupement décentralisé se produit.

## 9.3.3 Robustesse du modèle

On peut dans un second temps ajouter du bruit sur le mouvement des amibes et prendre une valeur de $p_A$ strictement positive.

On constate alors que pour des valeurs de $p_A$ « raisonnables », c'est-à-dire inférieures à 0.25, le processus de regroupement n'est pas affecté par l'introduction de bruit sur le mouvement des amibes (voir fig. 9.6). On constate même que dans certains cas la présence de bruit peut rendre
<figure><img src="image_53.png" /><figcaption>FIGURE 9.7 – Regroupement avec $p_A = 0.1$ et $\lambda = 0.01$ et avec présence d'obstacles. On notera que l'on a utilisé un voisinage de von Neumann.</figcaption></figure>

les mouvements collectifs des amibes plus fluides. La forme du groupe final est également modifiée, devenant plus circulaire. Pour de plus hautes valeurs de $p_A$, on observe également un processus de regroupement, mais celui-ci peut devenir plus lent et le groupe final est bien sûr de moins en moins compact à mesure que $p_A$ augmente. La question de savoir de façon plus précise dans quelle mesure le bruit modifie le processus de regroupement est un problème à étudier.

On peut également observer ce qui se produit lorsqu'on introduit des obstacles sur la grille. La figure 9.7 présente une simulation du système pour une grille de taille 64 × 64, pour $p_A = 0.10$. Les obstacles sont matérialisés en bleu : ce sont des cellules qui sont imperméables aux ondes de réaction-diffusion et qui ne laissent pas passer les amibes. On remarquera que l'on a également choisi un voisinage de von Neumann de façon à travailler dans les conditions les plus difficiles qui soient. L'observation des simulations montre que le comportement du système est robuste : l'ajout d'obstacles ne constitue pas un frein au regroupement car les ondes de réaction-diffusion, de par leur dynamique, contournent les obstacles et peuvent se ré-amplifier après avoir franchi des ouvertures étroites.

## 9.4 Développements du modèle

### 9.4.1 Problème de l'infotaxie collective

Nous allons maintenant voir comment cette « mécanique » de coordination des amibes peut être mise à profit pour coordonner une équipe d'agents dont le but est de localiser de manière non conventionnelle une source diffusant des ondes chimiques. De nouveau, nous travaillons dans un cadre très contraint : outre les restrictions précédentes nous supposerons que les localisations de la source ne peuvent se faire que de façon sporadique et que les évènements de localisation de la source sont de type binaire : *ils disent qu'une source a été détectée mais ne donnent*
<figure><img src="image_54.png" /><figcaption>FIGURE 9.8 – Évolution du système pour $N = 5$ amibes pour une grille de taille $20 \times 20$, $p_A = 0.2$, et $p_R = 0.9$. La source est représentée en bleu (forme de « carreau »); les amibes sont les cercles noirs (état rec) ou en violet (état emi). Les cellules sont en rouge, orange et blanc ce qui correspond respectivement aux états E, R et N.</figcaption></figure>

aucune information sur sa direction, ni la distance où celle-ci se trouve.

De telles situations sont observées dans la nature, par exemple dans le cas où la femelle d'un papillon de nuit émet des phéromones pour attirer les mâles. La phéromone se diffuse par paquets de forte concentration (des « patchs ») qui se déplacent de manière plus ou moins aléatoire dans l'espace en raison des tourbillons et courants qui se forment naturellement dans les mouvements d'air. Lorsqu'un mâle rencontre un de ces paquets, il sait seulement qu'une femelle est proche mais il ne sait pas exactement où elle se trouve. Les insectes savent cependant utiliser à leur avantage l'information du sens de déplacement du vent : ils cherchent tout d'abord un endroit où les détections sont fréquentes puis remontent en sens opposé de direction du vent. Ce problème a été nommé *infotaxie* par Vergassola et al. [246] : le mot est composé de *info-* qui est l'apocope d'*information* et du grec τάξις (*taxis*) qui signifie : *mise ordre, arrangement, disposition* (Bailly).

Notre article de 2016 expose ce modèle d'infotaxie collective et les observations par simulation numérique [81]. Nous en rappelons ici les principales caractéristiques.

La première chose à décrire est la probabilité de faire une détection. On note $\sigma \in \mathcal{L}$ la position de la source. La probabilité $\rho$ de détection de la source dans une cellule $c \in \mathcal{L}$ quelconque s'exprime alors comme : $\rho(\sigma) = 1$ et

$$ \forall c \neq \sigma, \rho(c) = \frac{K}{d(c, \sigma)^2}, $$

où $d(c, \sigma)$ est la distance de Manhattan entre $c$ et $\sigma$, et où $K$ est une constante, arbitrairement fixée à $K = 0.5^{27}$.

<footnote n="27">27. D'autres auteurs ont préféré prendre une fonction qui décroît de manière exponentielle avec la distance. Le choix d'une fonction qui décroît avec le carré de la distance facilite les choses et permet aux amibes de faire des détections sans avoir à être nécessairement très près de la source.</footnote>
Lorsqu'une détection se produit, une amibe passe de l'état receveur (rec) à l'état émetteur emi. Ceci l'amène à déclencher une onde de réaction-diffusion, à la condition que la cellule sur laquelle elle se trouve soit à l'état neutre (N). D'autre part, pour accélérer la convergence vers la source, nous ajoutons la possibilité qu'une amibe émette plusieurs ondes lorsqu'elle fait une détection. Ceci est modélisé par le fait qu'une amibe reste dans l'émetteur avec probabilité pR et passe dans l'état receveur (rec) avec probabilité $1-pR$. Le temps passé dans l'état émetteur suit donc une loi géométrique de paramètre pR ; la valeur de ce paramètre est fixée empiriquement à pR = 0.9.

La figure 9.8 montre l'évolution du système pour un jeu de paramètres donné$^{28}$. Cette figure illustre le comportement le plus courant du système et ses différentes phases :

(a) **régime de dispersion** : Les amibes se déplacent aléatoirement et font quelques rares détections.

(b) **régime de concentration** : Lorsqu'une amibe, par le jeu du hasard, se retrouve proche de la source, elle émet de façon plus fréquente et attire à elle les autres amibes.

(c) **phase finale** : Les amibes sont regroupées autour de la source, elles émettent beaucoup d'ondes, qui se contrarient l'une l'autre. Une amibe finit par trouver la source grâce à la combinaison des mouvements aléatoires et des ondes émises.

L'étude détaillée des différentes phases a fait l'objet du stage de Quentin Ladeveze, étudiant de Licence 3 en informatique à l'université de Lorraine, réalisé en 2016. Ce stage a permis de déterminer les différentes plages de paramètres pour lesquelles le processus d'infotaxie se déroulait le plus rapidement. Parmi les observations les plus remarquables, notons que « plus n'est pas mieux » : de façon paradoxale, il existe une valeur optimale du nombre d'amibes. En effet, si les amibes sont trop nombreuses, la phase (c) devient trop longue car les ondes se détruisent les unes les autres et les amibes deviennent incapables de converger de façon cohérente vers la source.

La figure 9.9 montre comment varie le temps de détection en fonction de la probabilité d'agitation pour 20 amibes sur une grille de taille 80×80. On remarquera que le gain par rapport à une pure marche aléatoire est appréciable pour des valeurs de $p_A$ assez grandes ($p_A < 0.4$ environ). D'autre part, on constate une fois de plus que la présence d'un peu d'agitation est bénéfique : la valeur minimale du temps de détection est en effet obtenue pour $p_A = 0.2$!

## 9.4.2 Des amibes & des robots

Nous avons cherché à savoir si ces propriétés, observées uniquement par le truchement de la simulation numérique, pouvaient être également « transférées » sur un système réel. Nous nous sommes donc intéressés à réaliser un système de regroupement décentralisé à l'aide de robots [100].

Nous avons pour cela bénéficié de l'aide du professeur Guy Theraulaz, de l'université de Toulouse, qui a mis à notre disposition les robots Alice qui avaient été utilisés pour étudier la dynamique des fourmis à l'aide de robots [120]. Nous avons également procédé à des expériences sur des robots Khepera III, sur une table spéciale où les robots pouvaient réagir à des ondes lumineuses projetées par le bas.

Il est à noter que la transposition du modèle cellulaire au cas de robots réels n'est pas une tâche anodine. Notamment dans le cas des robots Alice, qui, dans la configuration que nous avions, ne disposaient que de deux capteurs de lumière. Les résultats que nous avons obtenus

<footnote n="28">28. Voir aussi les suppléments visuels sur : https://hal.inria.fr/hal-01327983</footnote>
<figure><img src="image_55.png" /></figure>

FIGURE 9.9 – Temps de détection moyen en fonction de la probabilité d'agitation $p_A$. Le jeu de paramètres est: $N = 20$ amibes, $L = 80$, $K = 0.5$, $p_A = 0.1$, et $p_R = 0.9$ (en bleu). La courbe en violet montre une évolution purement aléatoire (sans ondes de réaction-diffusion). Repris de la ref. [81].

<figure><img src="image_56.png" /></figure>

FIGURE 9.10 – Image montrant le dispositif expérimental avec les robots Alice (à gauche) et avec les robots Khepera (à droite). Repris de la ref. [100].
<figure><img src="image_57.png" /><figcaption>FIGURE 9.11 – Mouvements des robots Alice. Repris de la ref. [100].</figcaption></figure>

étaient néanmoins encourageants et nous ont permis de démontrer la faisabilité d'une application des méthodes de regroupement des amibes dans des cas « physiques ». Un obstacle majeur reste cependant présent : pour les robots Alice comme pour les robots Khepera III, nos expériences ont simulé la propagation des ondes de réaction-diffusion. Implémenter la diffusion de ces informations dans un milieu réel, par exemple à laide d'un réseau de capteurs, reste le défi principal pour la poursuite de ces recherches.

### 9.4.3 Des amibes pour classer des données

Après avoir observé les propriétés remarquables des deux modèles d'amibes précédents, nous nous sommes demandés si la formation des groupes ne pourrait pas se faire en fonction de données contenues par les amibes, autrement dit s'il était possible de faire réaliser une tâche de partitionnement de données (*data clustering* en anglais) [218].

Des modèles bio-inspirés ont déjà été utilisés pour ce type de tâche [130, 177, 170].

La mise en œuvre du modèle d'agrégation des amibes pour le partitionnement de données repose sur les principes suivants :

1. Chaque amibe porte une donnée du jeu de données.

2. Les amibes émettent des excitations dans la cellule où elles se trouvent avec une certaine probabilité.

3. Ces excitations se transmettent avec le mécanisme de réaction-diffusion (automate cellulaire de Greenberg-Hastings) en portant la donnée dans le front d'excitations.

4. Les amibes réagissent aux excitations reçues en fonction d'une comparaison avec leur propre donnée : si la différence est faible, l'excitation est perçue comme étant attractive et l'amibe remonte le front, si la différence est élevée, l'excitation est perçue comme répulsive et l'amibe se déplace en s'écartant du front.

Les caractéristiques exprimées ci-dessus sont assez simples à saisir mais leur mise en œuvre concrète pose une multitude de problèmes. Il faut évidemment traiter du cas où plusieurs
amibes sont superposées, régler convenablement la différence entre attraction et répulsion, choisir un taux d'émission pour les amibes, etc. Ce travail a fait l'objet du stage de Master 2 d'Amaury Saint-Jore, avec lequel, en collaboration avec Emmanuel Jeandel, nous avons pu montrer que sous certaines conditions, ce modèle pouvait séparer des données générées selon plusieurs lois gaussiennes. Par ailleurs, des résultats encourageants ont été obtenus avec le jeu de données « classique » des Iris de Fischer [218]. Cette piste de recherche doit néanmoins être consolidée si l'on souhaite promouvoir ce système comme un mode de tri de données bio-inspiré robuste et adaptatif.

Nous pouvons clore ce dernier chapitre sur deux questions.

**Question 24.** Quels résultats analytiques peuvent être obtenus avec ce modèle ? Faut-il le simplifier pour le rendre abordable par l'analyse, par exemple en proposant une version unidimensionnelle ? Doit-on recourir à des approximations de champ moyen ? Comment décrire le phénomène d'agrégation de façon précise et prédicible en moyenne ?

**Question 25.** Dans quelles autres situations pourrait-on coupler la réaction-diffusion et le déplacement de robots ou d'agents ? La piste du tri de données doit-elle être approfondie ou doit-on chercher d'autres problèmes pour lesquels il serait pertinent d'appliquer ce modèle bio-inspiré ?
# Ouvertures et pistes de recherche

Que retenir au terme de notre parcours en neuf stations ? En recherche, il est toujours délicat de tirer des conclusions fermes à partir de travaux qui sont par nature toujours en chantier. Tâchons cependant sélectionner quelques éléments, « sé-lect-tionner », c'est-à-dire de « cueillir » (c'est un des sens du mot logos) quelques fleurs parmi celles qui s'offrent à notre vue.

## Sur les liens entre analyse mathématique et simulation numérique

La première partie de ce mémoire s'est concentrée sur l'étude de l'asynchronisme des automates cellulaires à l'aide de méthodes analytiques. Nous avons posé la question de la robustesse des automates cellulaires, et l'asynchronisme nous a paru la façon la plus directe d'aborder cette question.

Les résultats obtenus montrent que même pour des systèmes dont l'évolution est probabliste, il est possible de prédire le comportement qualitatif de ce système et d'estimer la valeur des temps de convergence avec une assez bonne précision. Ceci nous a permis de présenter une classification des automates cellulaires et d'étudier leurs propriétés de récurrence. Du même coup, les limites de l'approche analytique se sont rapidement fait sentir : il reste en effet un certain nombre d'automates cellulaires simples dont on ne sait pas calculer le temps de convergence vers un point fixe. Nous n'avons pas non plus essayé de nous attaquer à des questions plus difficiles, comme l'évaluation du comportement des systèmes avec un synchronisme partiel. Ceci justifie le recours à la simulation numérique pour aller observer différentes propriétés et, dans un second temps, chercher à établir des démonstrations en partant des observations.

Sur le volet analytique, nous constatons que, s'agissant de nos travaux tout autant de ceux de nos collègues, les systèmes à états binaires ont tenu jusqu'à présent une place centrale dans la littérature du domaine. Ceci est tout à fait dans l'ordre des choses puisque la méthode scientifique, d'origine cartésienne, recommande de ne pas s'occuper des problèmes les plus difficiles tant qu'on n'a pas une vue claire des problèmes plus simples. Néanmoins, il nous paraît aujourd'hui nécessaire de se risquer davantage en territoire inconnu en explorant des automates cellulaires avec plusieurs états. On pourra par exemple s'atteler à l'étude des règles ternaires, qui commencent actuellement à peine à être défrichées [112, 253, 65].

Du côté des techniques d'analyse de la dynamique des systèmes probabilistes, nous avons vu que les chaînes de Markov et les martingales tiennent un rôle prépondérant. Pourtant, dès que l'on s'attaque à des systèmes où les interactions sont légèrement plus complexes que celles des automates cellulaires élémentaires, on se heurte à l'impossibilité d'appliquer directement ces outils (partie 2 du mémoire). Il faut alors recourir à des approximations avec des hypothèses fortes, comme nous l'avons vu avec l'hypothèse du champ moyen dans le cas de l'automate de Greenberg-Hastings. Le problème est que le cadre analytique projette alors le comportement du système en le simplifiant et élague ainsi la grande richesse de comportement qu'un modèle
peut receler, comme dans le cas du modèle de formation d'essais.

En somme, entre analyse et simulation, nous ne choisissons pas notre camp. Il existe de nombreux problèmes où la complémentarité de ces deux approches doit être cultivée et notre souhait est de continuer à travailler à la jonction des deux.

## À propos des moyens de calcul

Dans ce mémoire, nous avons évoqué l'aspect matériel du calcul mais sans entrer dans les détails. Rappelons qu'avec Nikolaos Vlassopoulos, Hugues Berry, et Bernard Girau, nous avons implémenté un calcul d'automate cellulaire parallèle à l'aide de systèmes de type FPGA (field-programme gate arrays) [249]. Cette piste de travail pourrait être reprise car si au moment où nous avons exploré comment simuler des automates cellulaires à l'aide de FPGA, il n'existait pas de solution « clé en main », la prise en main de tels outils de calcul semble avoir été simplifiée depuis.

La piste des simulations parallèles sur cartes graphiques (GPU) constitue une autre voie possible et, à ce titre, nous pensons qu'il serait intéressant de voir quelles seraient les spécifications engendrées par la simulation de systèmes asynchrones ou probabilistes par rapport aux systèmes déterministes classiques [39]. Au-delà des FPGA et des GPU, qui sont les systèmes auxquels on pense « naturellement » lorsqu'il s'agit de calculer en parallèle, nous sommes persuadés que de nombreux autres systèmes de calcul parallèles et asynchrones seront développés dans les prochaines années. Nous avons évoqué les modèles de calcul « browniens » conçus par Ferdinand Peper, Jia Lee et leurs collaborateurs [101] mais d'autres systèmes sont également en cours de développement, notamment sous la poussée forte du développement de la recherche en intelligence artificielle (puces neuromorphiques, caméras asynchrones, etc.)

Signalons également que nous avons développé notre propre outil de simulation des automates cellulaires : *FiatLux*<fnref n="29" />, logiciel écrit en java et qui compte maintenant plusieurs centaines de classes. En vingt ans de recherche, ce logiciel s'est considérablement développé mais nous n'avons jamais pris le temps de remettre son architecture à plat et d'écrire une documentation du code et une documentation utilisateur. Même si le développement logiciel ne tient pas une place centrale dans nos activités, nous souhaitons consacrer plus de temps à ce volet dans les années à venir, ne serait-ce que pour laisser une trace à ceux qui souhaiteront continuer ce travail ou le reprendre en repartant du début.

## À propos de la robustesse du calcul

Nous avons posé en introduction la question de la réalisation de calculs à l'aide de méthodes robustes, c'est-à-dire qui résistent à différentes perturbations structurelles du modèle. Nous avons constaté sur les exemples donnés que des modèles où le caractère discret est marqué et où les règles semblent assez *ad hoc*, comme dans le cas des turmites, étaient assez peu robustes. La plupart du temps un changement mineur dans la définition du modèle peut conduire à des comportements qualitativement différents. En revanche, pour des modèles inspirés de la biologie et où l'aléa joue un rôle central, comme dans le cas des amibes par exemple, nous avons vu que le modèle était nettement plus robuste. Ceci n'est pas surprenant : si un système parvient à son but par des mécanismes d'auto-organisation en tirant parti de l'aléa, il y a de

<footnote n="29">29. https://project.inria.fr/fiatlux/</footnote>
fortes chances que les « obstacles » ne viendront pas perturber ses trajectoires de manière trop importante.

Tout cela est évidemment de l'ordre de l'intuition et, pour donner un contenu plus solide à ces idées, l'étude de problèmes inverses nous paraît fondamental. Nous avons présenté dans ce mémoire le problème de la classification de la densité, le problème la synchronisation globale, le problème du regroupement décentralisé. Nous avons également évoqué des problèmes « proches », tels que le problème de l'infotaxie collective ou celui de la classification de données à l'aide des amibes virtuelles. Les lignes ci-dessous présentent quelques autres exemples possibles.

## Ouvertures

Pour finir, donnons ici quelques problèmes sur lesquels nous souhaiterions travailler dans un futur proche.

### Exploration de l'espace des AC probabilistes

Une exploration complète de l'espace des ACE probabilistes reste à faire : il s'agit de « cartographier » cet espace, paramétré par huit probabilités et donc analogue à $[0, 1]⁸$. On pourrait commencer par mesurer par exemple la densité asymptotique moyenne obtenue pour les différents points de cet espace, puis d'autres paramètres comme la densité asymptotique des motifs de plus grandes longueur, voire des quantités comme l'entropie ou le spectre des densités [67]. Où sont les discontinuités, les transitions de phase du premier et second ordre, quels sont les motifs qui apparaissent, etc. ? Un tel travail rendrait honneur au projet de Turing de comprendre les mécanismes de naissance des formes à partir de lois locales simples [244].

### Problème du diagnostic décentralisé

Nous sommes actuellement engagés dans une collaboration avec Irène Marcovici et Régine Marchand sur le problème du diagnostic décentralisé [122]. Plus généralement, les recherches sur les problèmes de consensus distribué nous paraissent fondamentaux. Les automates cellulaires, par leur côté uniforme et simple, sont un terrain de choix pour poser les questions les plus claires mais il ne faudrait pas se limiter strictement à ce cadre : nous souhaitons donc passer de la structure en grille à l'étude des systèmes dynamiques sur des graphes. Un stage de Master 2 vient d'être initié sur ce thème avec Kévin Engrand, étudiant du Master AVR (apprentissage, vision, robotique) de l'université de Lorraine.

### Problème de la classification de la parité

Dans le prolongement de nos réflexions sur le problème de la classification de la densité, nous avons traité le problème de la classification de la parité par des systèmes de particules asynchrones. Dans ce problème, un consensus doit également être établi entre les cellules : le système doit converger vers tout-zéro ou tout-un si la configuration initiale contient respectivement un nombre pair ou impair de 1. Nous avons construit une première solution qui consiste à mettre à jour le système par paires, et à changer simultanément l'état des deux cellules mises à jour en fonction de leur voisinage [89]. La parité est donc conservée au fil du temps et la convergence vers tout-zéro ou tout-un se fait à l'aide de mécanismes similaires à ceux observés pour les automates cellulaires quadratiques.
Nous avons démontré que la convergence était quadratique pour les cas les plus simples mais nous n’avons pas su trouver un argument dans le cas général. Ceci montre, une fois de plus, et s’il en était besoin, que des modifications du modèle qui peuvent sembler anodines rendent les choses plus difficiles au niveau de l’analyse. Les simulations confirment en revanche que la convergence est quadratique en moyenne et que le modèle fournit une solution que l’on peut utiliser sur des anneaux de petite taille. Pour des systèmes plus grands, le problème reste ouvert et on pourrait imaginer un système de systèmes où la parité serait calculée par niveaux hiérarchiques. Plus généralement, ce modèle ne vise pas tant à fournir une nouvelle méthode plus efficace que les solutions déterministes [215] mais à dégager de nouvelles façons d’aborder le calcul, en faisant jouer à l’aléa un rôle constructif (voir le travail de Hongu et Hagiya pour un exemple récent [134]).

## Problème de l’auto-correction

Dans ce problème, on part d’un pavage du plan obéissant à des contraintes, par exemple un *k*-coloriage, c’est-à-dire un état de la grille où chaque cellule possède une couleur parmi *k* et où deux cellules adjacentes ne peuvent avoir la même couleur. On perturbe cet état « admissible » en introduisant des erreurs et on souhaite que les cellules reviennent à un état admissible uniquement à l’aide d’interactions locales. Avec Irène Marcovici et Siamak Taati, nous avons étudié ce problème pour différentes valeurs du nombre de couleurs *k* et nous avons montré que dans certains cas, les règles stochastiques pouvaient être à la fois plus simples, plus « isotropes » et plus efficaces que les règles déterministes [94, 95].

Pour en savoir plus sur ce sujet, nous invitons les lecteurs à se reporter au paragraphe 2.2 de la thèse d’habilitation à diriger les recherches d’Irène Marcovici [168].

## Ouverture vers l’économie et la modélisation des échanges inter-entreprises

Ce mémoire présenté des modèles liés à la physique (transitions de phase), à la chimie (réaction-diffusion) et à la biologie (*Dictyostelium discoideum*). Afin d’élargir davantage notre champ de recherches, nous avons franchi le pas en allant du côté de l’économie et avons entamé un travail sur le problème de la mutualisation des dettes entre entreprises [9]. En effet, cette question est un enjeu économique majeur, tout particulièrement en période de crise, où les liquidités peuvent manquer et conduire à des faillites d’entreprises pourtant viables.

Nous nous intéressons aux réseaux de paiement entre entreprises afin de réduire la dette qu’ils contiennent. Comme les factures sont généralement payées avec un certain délai (deux mois en zone euro), les dettes qu’elles représentent s’accumulent et peuvent être réduites par mutualisation. En effet, si plusieurs entreprises se doivent mutuellement des sommes, on peut annuler une partie de ces sommes et financer les restes dus (cf. exemple sur la figure 12).

L’ensemble des dettes existant à un moment donné est modélisé par un multigraphe dont les sommets sont les entreprises et les arcs représentent des factures émises pendant un laps de temps donné (par exemple un mois). Nos premiers travaux ont porté sur le cas de la réduction intégrale de dettes, c’est-à-dire que chaque facture est ou bien laissée en l’état ou bien supprimée. Ce problème étant NP-complet, il nécessite des méthodes heuristiques pour trouver comment optimiser la quantité de dettes annulée en fonction des entreprises que l’on peut financer. Nous avons proposé plusieurs heuristiques et commencé à analyser la structure des graphes d’échange, notamment lors du stage de Marie Vela-Mena, étudiante de L3 à l’université de Marseille, et celui d’Arthur Rousseau, étudiant de L3 à l’ENS Paris.
<figure><img src="image_58.png" /><figcaption>(a) Situation initiale</figcaption></figure>

<figure><img src="image_59.png" /><figcaption>(b1) avec une réduction partielle</figcaption></figure>

<figure><img src="image_60.png" /><figcaption>(b2) avec une réduction intégrale</figcaption></figure>

FIGURE 12 – (a) Situation initiale ; les positions nettes sont indiquées entre parenthèses (b1) avec une réduction partielle du cycle A-B-C : on paye et supprime une facture et on en réduit deux autres ; (b2) avec une réduction intégrale avec un financement par EXT de 3 unités sur le sommet A : on paye et supprime quatre factures (en pointillés). Les changements de solde induits par ces paiements sont indiqués entre crochets. Deux dettes subsistent : A vers EXT (montant 3) et C vers D (montant 10).

À terme, le but visé est de transformer les paiements entre une communauté d'acteurs, en tenant compte de leur position nette, c'est-à-dire la somme des crédits diminué de la somme des dettes. Ce système pourrait avoir des effets bénéfiques en favorisant les échanges à l'intérieur d'un groupe d'acteurs économiques fortement reliés. Un financement de bourse thèse a été obtenu par le programme d'actions exploratoires de l'Inria 30, ce qui nous a permis de lancer le doctorat de Joannès Guichon, avec un encadrement en tandem avec Sylvain Contassot-Vivier. Notre souhait serait de pouvoir d'appliquer les techniques vues sur les systèmes complexes à topologie régulière sur ce cas plus proche du terrain, où les liens entre composants sont bien sûr différemment structurés : ces systèmes économiques sont à première vue plus embrouillés, plus intriqués, plus difficiles à analyser, mais, nous l'espérons, aussi propices à étudier que ceux que nous avons vu dans ce mémoire.

## Un pas de côté

Enfin, nous souhaitons mentionner que les automates cellulaires et les systèmes complexes sont également des objets qui peuvent donner lieu à de nombreuses réflexions qui dépassent le strict cadre scientifique [92]. Nous avons pu ainsi au cours des dernières années développer quelques éléments sur l'œuvre de Turing [74, 82], sur les mathématiques [84], sur la question de l'intelligence artificielle [88] ou même proposer une vue esthétique de nos diagrammes espace-temps probabilistes [80]. Il va sans dire que ce travail devra être poursuivi, et même accentué, car c'est au fond tout l'à côté des sciences qui donne son sens à l'activité scientifique.

<footnote n="30">30. https://www.inria.fr/fr/murene</footnote>
Bibliographie

[1] Nazim FATÈS. "Robustesse de la dynamique des systèmes discrets : le cas de l'asynchrонisme dans les automates cellulaires". Thèse de doct. École normale supérieure de Lyon, 2004.

[2] Guillermo ABRAMSON et Damián H. ZANETTE. "Globally coupled maps with asynchronous updating". In: *Physical Review E* 58 (4 1998), p. 4454-4460. DOI: 10.1103/PhysRevE.58.4454.

[3] Susumu ADACHI, Ferdinand PEPER et Jia LEE. "Computation by asynchronously updating cellular automata". In: *Journal of Statistical Physics* 114.1-2 (2004), p. 261-289.

[4] Susumu ADACHI, Ferdinand PEPER et Jia LEE. "Universality of Hexagonal Asynchronous Totalistic Cellular Automata". In: *Proceedings of ACRI'04*. Sous la dir. de Peter SLOOT, Bastien CHOPARD et Alfons HOEKSTRA. T. 3305. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2004, p. 91-100. DOI: 10.1007/978-3-540-30479-1_10.

[5] Alexandru AGAPIE, Robins HÖNS et Heinz MÜHLENBEIN. "Markov Chain Analysis for One-Dimensional Asynchronous Cellular Automata (Kluwer Academic Publishers)". In: *Methodology And Computing In Applied Probability* 6.21 (2004), p. 181-201. DOI: 10.1023/B:MCAP.0000017712.55431.96.

[6] Pankaj AGARWAL. "Simulation of aggregation in *Dictyostelium* using the Cell programming language". In: *Computer Applications in the Biosciences* 10.6 (1994), p. 647-655.

[7] Jean-Paul ALLOUCHE et Christine REDER. "Oscillations spatio-temporelles engendrées par un automate cellulaire". In: *Discrete Applied Mathematics* 8.3 (1984), p. 215-254. DOI: 10.1016/0166-218X(84)90122-7.

[8] Ramón ALONSO-SANZ et Larry BULL. "A very effective density classifier two-dimensional cellular automaton with memory". In: *Journal of Physics A* 42 (2009), p. 485101.

[9] Massimo AMATO, Nazim FATÈS et Lucio GOBBI. *The economics and algorithmics of an integral settlement procedure on B2B network*. Prerprint SSRN. 2021. DOI: 10.2139/ssrn.3915380.

[10] S. AMOROSO et Y. N. PATT. "Decision procedures for surjectivity and injectivity of parallel maps for tesselation structures". In: *Journal of Computer and System Sciences* 6 (1972), p. 448-464.

[11] H. ANDO, Y. OASA, I. SUZUKI et M. YAMASHITA. "Distributed memoryless point convergence algorithm for mobile robots with limited visibility". In: *IEEE Transactions on Robotics and Automation* 15.5 (1999), p. 818-828. DOI: 10.1109/70.795787.
[12] Julio ARACENA, Eric GOLES, Andrés MOREIRA et Lilian SALINAS. "On the robustness of update schedules in Boolean networks". In: *Biosystems* 97.1 (2009), p. 1-8. DOI: 10.1016/j.biosystems.2009.03.006.

[13] Pablo ARRIGHI, Nicolas SCHABANEL et Guillaume THEYSSIER. "Stochastic Cellular Automata: Correlations, Decidability and Simulations". In: *Fundamenta Informaticae* 126.2-3 (2013), p. 121-156. DOI: 10.3233/FI-2013-875.

[14] Jan M. BAETENS, Pieter VAN DER WEEËN et Bernard DE BAETS. "Effect of asynchronous updating on the stability of cellular automata". In: *Chaos, Solitons & Fractals* 45.4 (2012), p. 383-394. DOI: 10.1016/j.chaos.2012.01.002.

[15] Franco BAGNOLI et Raúl RECHTMAN. "Synchronization and maximum Lyapunov exponents of cellular automata". In: *Physical Review E* 59.2 (1999), R1307.

[16] Stefania BANDINI, Andrea BONOMI et Giuseppe VIZZARI. "An analysis of different types and effects of asynchronicity in cellular automata update schemes". In: *Natural Computing* 11.2 (2012), p. 277-287. DOI: 10.1007/s11047-012-9310-4.

[17] Anouk BARBEROUSSE et Cyrille IMBERT. "New Mathematics for Old Physics : The Case of Lattice Fluids". In: *Studies in History and Philosophy of Science Part B : Studies in History and Philosophy of Modern Physics* 44.3 (2013), p. 231-241. DOI: 10.1016/j.shpsb.2013.03.003.

[18] Hamid BEIGY et M.R. MEYBODI. "Asynchronous cellular learning automata". In: *Automatica* 44.5 (2008), p. 1350-1357. DOI: 10.1016/j.automatica.2007.09.018.

[19] Selma BELGACEM et Nazim FATÈS. "Robustness of multi-agent models : the example of collaboration between turmites with synchronous and asynchronous updating". In : *Complex Systems* 21.3 (2012), p. 165-182. URL: http://www.complex-systems.com/abstracts/v21_i03_a01.html.

[20] Florence BÉNÉZIT. "Distributed average consensus for wireless sensor networks". Thèse de doct. Lausanne : EPFL, 2009. DOI: 10.5075/epfl-thesis-4509.

[21] Hugues BERRY et Nazim FATÈS. "Robustness of the Critical Behaviour in the Stochastic Greenberg-Hastings Cellular Automaton Model". In: *International Journal of Unconventional Computing* 7.1-2 (2011), p. 65-85. URL: http://www.oldcitypublishing.com/IJUC/IJUCabstracts/IJUC7.1-2abstracts/IJUCv7n1-2p65-85Berry.html.

[22] Hugues BERSINI et Vincent DETOURS. "Asynchrony Induces Stability in Cellular Automata Based Models". In: *Proceedings of the 4th International Workshop on the Synthesis and Simulation of Living Systems ArtificialLifeIV*. Sous la dir. de Rodney A. BROOKS et Pattie MAES. MIT Press, 1994, p. 382-387.

[23] Olivier BEURET et Marco TOMASSINI. "Behaviour of multiple generalized Langton's ants". In: *Proceeding of the Artificial Life V Conference*. Sous la dir. de C. LANGTON et K. SHIMOHARA. Nava, Japan : MIT Press, 1998, p. 45-50.

[24] Hendrik J. BLOK et Birger BERGERSEN. "Synchronous versus Asynchronous Updating in the "game of Life"". In: *Physical Review E* 59 (1999), p. 3876-9.

[25] Jean-Pierre BOON. "How Fast Does Langton's Ant Move?" In: *Journal of Statistical Physics* 102 (2001), p. 355-360.
[26] Olivier BOURÉ. "« Le simple est-il robuste ? » : une étude de la robustesse des systèmes complexes par les automates cellulaires". Thèse de doct. Université de Lorraine, 2013.
URL: http://tel.archives-ouvertes.fr/tel-00918545.

[27] Olivier BOURÉ, Nazim FATÈS et Vincent CHEVRIER. "Robustness of Cellular Automata in the Light of Asynchronous Information Transmission". In: *Proceedings of Unconventional Computation 2011*. Sous la dir. de Cristian CALUDE, Jarkko KARI, Ion PETRE et Grzegorz ROZENBERG. T. 6714. Lecture Notes in Computer Science. Springer, 2011, p. 52-63.
DOI: 10.1007/978-3-642-21341-0.

[28] Olivier BOURÉ, Nazim FATÈS et Vincent CHEVRIER. "Probing robustness of cellular automata through variations of asynchronous updating". In: *Natural Computing* 11 (2012), p. 553-564.
DOI: 10.1007/s11047-012-9340-y.

[29] Olivier BOURÉ, Nazim FATÈS et Vincent CHEVRIER. "A Robustness Approach to Study Metastable Behaviours in a Lattice-Gas Model of Swarming". In: *Proceedings of Automata'13*. Sous la dir. de Jarkko KARI, Martin KUTRIB et Andreas MALCHER. T. 8155. Lecture Notes in Computer Science. Springer, 2013, p. 84-97.
DOI: 10.1007/978-3-642-40867-0_6.

[30] Olivier BOURÉ, Nazim FATÈS et Vincent CHEVRIER. "First steps on asynchronous lattice-gas models with an application to a swarming rule". In: *Natural Computing* 12.4 (2013), p. 551-560.
DOI: 10.1007/s11047-013-9389-2.

[31] Raimundo BRICEÑO, Pablo MOISSET DE ESPANÉS, Axel OSSES et Ivan RAPAPORT. "Solving the density classification problem with a large diffusion and small amplification cellular automaton". In: *Physica D: Nonlinear Phenomena* 261 (2013), p. 70-80.
DOI: 10.1016/j.physd.2013.07.002.

[32] Simon Ralph BROADBENT et John Michael HAMMERSLEY. "Percolation Processes I. Crystals and Mazes". In: *Proceedings of the Cambridge Philosophical Society* 53.3 (1957), p. 629-641.

[33] Leonid A. BUNIMOVICH et Serge E. TROUBETZKOY. "Recurrence properties of Lorentz lattice gas cellular automata". In: *Journal of Statistical Physics* 67 (1992), p. 289-302.
DOI: 10.1007/BF01049035.

[34] Ana BUŠIĆ, Nazim FATÈS, Jean MAIRESSE et Irène MARCOVICI. "Density Classification on Infinite Lattices and Trees". In: *Proceedings of LATIN 2012: Theoretical Informatics*. Sous la dir. de David FERNÁNDEZ-BACA. T. 7256. Lecture Notes in Computer Science. Springer, 2012, p. 109-120.
DOI: 10.1007/978-3-642-29344-3_10.

[35] Ana BUŠIĆ, Nazim FATÈS, Jean MAIRESSE et Irène MARCOVICI. "Density classification on infinite lattices and trees". In: *Electronic Journal of Probability* 18.51 (2013), p. 1-22.
DOI: 10.1214/EJP.v18-2325.

[36] Harmen J. BUSSEMAKER, Andreas DEUTSCH et Edith GEIGANT. "Mean-Field Analysis of a Dynamical Phase Transition in a Cellular Automaton Model for Collective Motion". In: *Physical Review Letters* 78.26 (1997), p. 5018-5021.
DOI: 10.1103/PhysRevLett.78.5018.

[37] BUVEL, R.L. et INGERSON, T.E. "Structure in Asynchronous Cellular Automata". In: *Physica D* 1 (1984), p. 59-68.

[38] Stephen WOLFRAM. "Universality and Complexity in Cellular Automata". In: *Physica D* 10 (1984), p. 1-35.
[39] Daniel CAGIGAS-MUÑIZ, Fernando DIAZ-DEL-RIO, Jose Luis SEVILLANO-RAMOS et
Jose-Luis GUISADO-LIZAR. "Efficient simulation execution of cellular automata on GPU".
In : *Simulation Modelling Practice and Theory* (2022), p. 102519. DOI : 10.1016/j.simpat.2022.102519.

[40] Mathieu CAPCARRERE. "Evolution of Asynchronous Cellular Automata". In : *Proceedings of Parallel Problem Solving from Nature — PPSN VII*. Sous la dir. de Juan Julián Merelo GUERVÓS, Panagiotis ADAMIDIS, Hans-Georg BEYER, Hans-Paul SCHWEFEL et José-Luis FERNÁNDEZ-VILLACAÑAS. T. 2439. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2002, p. 903-912. DOI: 10.1007/3-540-45712-7_87.

[41] Mathieu S. CAPCARRERE, Moshe SIPPER et Marco TOMASSINI. "Two-state, *r* = 1 Cellular Automaton that Classifies Density". In : *Phys. Rev. Lett.* 77.24 (1996), p. 4969-4971.

[42] Geoffrey CARON-LORMIER, Roger W. HUMPHRY, David A. BOHAN, Cathy HAWES et Pernille THORBEK. "Asynchronous and synchronous updating in individual-based models". In : *Ecological Modelling* 212.3-4 (2008), p. 522-527. DOI: 10.1016/j.ecolmodel.2007.10.049.

[43] Bernadette CHARRON-BOST et Patrick LAMBEIN-MONETTE. "Randomization and quantization for average consensus". In : *Proceedings of the IEEE Conference on Decision and Control (CDC)*. IEEE. 2018, p. 3716-3721.

[44] Philippe CHASSAING et Lucas GERIN. "Asynchronous cellular automata and brownian motion". In : *DMTCS Proceedings of AofA'07*. T. AH. 2007, p. 385-402. URL : http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/viewArticle/dMAH0129.

[45] Vincent CHEVRIER et Nazim FATÈS. *Multi-agent Systems as Discrete Dynamical Systems : Influences and Reactions as a Modelling Principle*. Rapp. tech. http://hal.inria.fr/inria-00345954. INRIA - LORIA, 2009.

[46] Vincent CHEVRIER et Nazim FATÈS. "How important are updating schemes in multi-agent systems? An illustration on a multi-turmite model". In : *Proceedings of AAMAS '10*. Richland, SC : International Foundation for Autonomous Agents et Multiagent Systems, 2010, p. 533-540. DOI : 10.1145/1838206.1838282.

[47] Bastien CHOPARD et Michel DROZ. *Cellular Automata Modeling of Physical Systems*. Cambridge University Press, 1998.

[48] Emilio N. M. CIRILLO, Francesca R. NARDI et Cristian SPITONI. "Basic Ideas to Approach Metastability in Probabilistic Cellular Automata". In : *Probabilistic Cellular Automata : Theory, Applications and Future Perspectives*. Sous la dir. de Pierre-Yves LOUIS et Francesca R. NARDI. Springer, 2018, p. 37-51. DOI : 10.1007/978-3-319-65558-1_3.

[49] Kenneth W. COMER. "Who Goes First? An Examination of the Impact of Activation on Outcome Behavior in Agent-based Models". Thèse de doct. George Mason University, Fairfax, Virginia, USA, 2014.

[50] Mauro COPELLI et Paulo R. A. CAMPOS. "Excitable scale free networks". In : *European Physics Journal B* 56.3 (2007), p. 271-278. DOI: 10.1140/epjb/e2007-00114-7.

[51] Robert CORI, Yves MÉTIVIER et Wieslaw ZIELONKA. "Asynchronous Mappings and Asynchronous Cellular Automata". In : *Information and Computation* 106.2 (1993), p. 159-202. DOI : 10.1006/inco.1993.1052.
[52] David CORNFORTH, David G. GREEN et David NEWTH. "Ordered asynchronous processes in multi-agent systems". In : *Physica D* 204.1-2 (2005), p. 70-82. DOI : 10.1016/j.physd.2005.04.005.

[53] Christian DARABOS, Mario GIACOBINI et Marco TOMASSINI. "Scale-Free Automata Networks Are Not Robust in a Collective Computational Task". In : *Cellular Automata*. Sous la dir. de Samira EL YACOUBI, Bastien CHOPARD et Stefania BANDINI. T. 4173. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 2006, p. 512-521.

[54] Rajarshi DAS, James P. CRUTCHFIELD, Melanie MITCHELL et James E. HANSON. "Evolving Globally Synchronized Cellular Automata". In : *Proceedings of 6th ICGA*. San Francisco, USA : Morgan Kaufmann, 1995, p. 336-343.

[55] Jacques DEMONGEOT, Eric GOLES, Michel MORVAN, Mathilde NOUAL et Sylvain SENÉ. "Attraction Basins as Gauges of Robustness against Boundary Conditions in Biological Complex Systems". In : *PLoS One* 5.8 (2010), e11793. DOI : 10.1371/journal.pone.0011793.

[56] Alberto DENNUNZIO, Enrico FORMENTI et Luca MANZONI. "Computing Issues of Asynchronous CA". In : *Fundamenta Informaticae* 120.2 (2012), p. 165-180. DOI : 10.3233/FI-2012-755.

[57] Alberto DENNUNZIO, Enrico FORMENTI, Luca MANZONI et Giancarlo MAURI. "m-Asynchronous cellular automata : from fairness to quasi-fairness". In : *Natural Computing* 12.4 (2013), p. 561-572. DOI : 10.1007/s11047-013-9386-5.

[58] Andreas DEUTSCH. "Orientation-induced pattern formation : swarm dynamics in a lattice-gas automaton model". In : *International Journal of Bifurcation and Chaos* 06.09 (1996), p. 1735-1752. DOI : 10.1142/S0218127496001077.

[59] Andreas DEUTSCH et Sabine DORMANN. *Cellular Automaton Modeling of Biological Pattern Formation Characterization, Applications, and Analysis*. Modeling and Simulation in Science, Engineering and Technology. Second edition. Birkhäuser Basel, 2017. DOI : 10.1007/978-1-4899-7980-3.

[60] Alexander K. DEWDNEY. "Two-dimensional Turing machines and turmites make tracks on a plane, Computer Recreations". In : *Scientific American* (sept. 1989), p. 180-182.

[61] Nobutaka DOBA. "The Time Evolution of a Greenberg-Hastings Cellular Automaton on a Finite Graph". In : *Complex Systems* 27 (juin 2018), p. 101-126. DOI : 10.25088/ComplexSystems.27.2.101.

[62] Eytan DOMANY et Wolfgang KINZEL. "Equivalence of cellular automata to Ising models and directed Percolation". In : *Physical Review Letters* 53 (1984), p. 311-314.

[63] Manfred DROSTE et Paul GASTIN. "Asynchronous cellular automata for pomsets without auto-concurrency". In : *Proceedings of CONCUR'96*. Sous la dir. d'Ugo MONTANARI et Vladimiro SASSONE. T. 1119. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 1996, p. 627-638. DOI : 10.1007/3-540-61604-7_80.

[64] Manfred DROSTE, Paul GASTIN et Dietrich KUSKE. "Asynchronous cellular automata for pomsets". In : *Theoretical Computer Science* 247.1-2 (2000), p. 1-38. DOI : 10.1016/S0304-3975(00)00166-3.
[65] Adam DZEDZEJ, Barbara WOLNIK, Anna NENCA, Jan M. BAETENS et Bernard DE BAETS. "Efficient enumeration of three-state two-dimensional number-conserving cellular automata". In: *Information and Computation* 274 (2020), p. 104534. DOI: 10.1016/j.ic.2020.104534.

[66] L. O. FADIEIEVA, I. Ye. MAKARENKO et P. V. MERZLYKIN. "The turmite-based cryptographic algorithm". In: *Journal of Physics: Conference Series* 1840.1 (2021), p. 012019. DOI: 10.1088/1742-6596/1840/1/012019.

[67] Nazim FATÈS. "Experimental study of elementary cellular automata dynamics using the density parameter". In : *Discrete models for complex systems, DMCS '03 (Lyon)*. Proceedings of Discrete Mathematics Theoretical Computer Science AB. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2003, p. 155-165.

[68] Nazim FATÈS. "Asynchronism Induces Second Order Phase Transitions in Elementary Cellular Automata". In : *Journal of Cellular Automata* 4.1 (2009), p. 21-38. URL : http://hal.inria.fr/inria-00138051.

[69] Nazim FATÈS. "Critical phenomena in cellular automata : perturbing the update, the transitions, the topology". In : *Acta Physica Polonica B - Proceedings Supplement* 3.2 (2010), p. 315-325. URL : http://www.actaphys.uj.edu.pl/sup3/abs/s3p0315.htm.

[70] Nazim FATÈS. "Does *Life* Resist Asynchrony?" In : *Game of Life Cellular Automata*. Sous la dir. d'Andrew ADAMATZKY. Springer London, 2010, p. 257-274. DOI: 10.1007/978-1-84996-217-9_14.

[71] Nazim FATÈS. "Solving the decentralised gathering problem with a reaction-diffusion-chemotaxis scheme — Social amoebae as a source of inspiration". In : *Swarm Intelligence* 4.2 (2010), p. 91-115. DOI: 10.1007/s11721-010-0038-4.

[72] Nazim FATÈS. "Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision". In : *28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)*. Sous la dir. de Thomas SCHWENTICK et Christoph DÜRR. T. 9. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany : Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2011, p. 284-295.

[73] Nazim FATÈS. "A note on the Density Classification Problem in Two Dimensions". In : *Exploratory papers presented at Automata* 2012. La Marana, Corse, France, 2012. URL : http://hal.inria.fr/hal-00727558.

[74] Nazim FATÈS. "Turing et la dimension ontologique du jeu". In : *Philosophia Scientiæ* 16-3 (2012), p. 7-16. DOI: 10.4000/philosophiascientiae.763.

[75] Nazim FATÈS. "A Note on the Classification of the Most Simple Asynchronous Cellular Automata". In : *Proceedings of Automata'13*. Sous la dir. de Jarkko KARI, Martin KUTRIB et Andreas MALCHER. T. 8155. Lecture Notes in Computer Science. Springer, 2013, p. 31-45. DOI: 10.1007/978-3-642-40867-0_3.

[76] Nazim FATÈS. "Stochastic Cellular Automata Solutions to the Density Classification Problem - When Randomness Helps Computing". In : *Theory of Computing Systems* 53.2 (2013), p. 223-242. DOI: 10.1007/s00224-012-9386-3.

[77] Nazim FATÈS. "A guided tour of asynchronous cellular automata". In : *Journal of Cellular Automata* 9.5-6 (2014), p. 387-416.
[78] Nazim FATÈS. "Quick Convergence to a Fixed Point: A Note on Asynchronous Elementary Cellular Automata". In: *Proceedings of ACRI'14*. Sous la dir. de Jarosław WAS, Georgios Ch. SIRAKOULIS et Stefania BANDINI. T. 8751. Lecture Notes in Computer Science. Springer, 2014, p. 586-595. DOI: 10.1007/978-3-319-11520-7_62.

[79] Nazim FATÈS. "Remarks on the Cellular Automaton Global Synchronisation Problem". In: *Proceedings of AUTOMATA 2015*. Sous la dir. de Jarkko KARI. T. 9099. Lecture Notes in Computer Science. extended version available on https://members.loria.fr/nazim.fates/dwnld/submitted-GlobalSynchProblem-Fates17.pdf. Springer, 2015, p. 113-126. DOI: 10.1007/978-3-662-47221-7_9.

[80] Nazim FATÈS. "Aesthetics and Randomness in Cellular Automata". In: *Designing Beauty: The Art of Cellular Automata*. Sous la dir. d'Andrew ADAMATZKY et Genaro MARTÍNEZ. Springer, 2016, p. 137-139. DOI: 10.1007/978-3-319-27270-2_23.

[81] Nazim FATÈS. "Collective Infotaxis with Reactive Amoebae: A Note on a Simple Bioinspired Mechanism". In: *Proceedings of ACRI 2016 – 12th International Conference on Cellular Automata for Research and Industry*. Sous la dir. de Samira EL YACOUBI, Jarosław WAS et Stefania BANDINI. Springer International Publishing, 2016, p. 157-165.

[82] Nazim FATÈS. « Théoréô, je vois! »– Lettres à Turing. Jean-Marc Lévy-Leblond (dir.) Ed. Thierry Marchaisse, 2016.

[83] Nazim FATÈS. "Diploid Cellular Automata: First Experiments on the Random Mixtures of Two Elementary Rules". In: *Proceedings of AUTOMATA 2017 – Cellular Automata and Discrete Complex Systems - 23rd IFIP WG 1.5 International Workshop*. Sous la dir. d'Alberto Dennunzio et AL. T. 10248. Lecture Notes in Computer Science. Springer, 2017, p. 97-108. DOI: 10.1007/978-3-319-58631-1_8.

[84] Nazim FATÈS. "Le dire mathématique". In: *Images des mathématiques* (2017). Publ. en ligne: https://images.math.cnrs.fr/Le-dire-mathematique.html.

[85] Nazim FATÈS. "Asynchronous Cellular Automata". In: *Encyclopedia of Complexity and Systems Science*. Berlin, Heidelberg: Springer Berlin Heidelberg, 2018, p. 1-21. DOI: 10.1007/978-3-642-27737-5_671-2.

[86] Nazim FATÈS. "Remarks on the cellular automaton global synchronisation problem: deterministic versus stochastic models". In: *Natural Computing* 18.3 (2019), p. 429-444.

[87] Nazim FATÈS. "A tutorial on elementary cellular automata with fully asynchronous updating". In: *Natural Computing* 19 (2020), p. 179-197. DOI: 10.1007/s11047-020-09782-7.

[88] Nazim FATÈS. "Le temps passe-t-il pour l'intelligence artificielle?" In: *The conversation* (2021). Publ. en ligne: https://theconversation.com/le-temps-passe-t-il-pour-lintelligence-artificielle-162291.

[89] Nazim FATÈS. *An asynchronous cellular system that solves the parity problem*. Rapp. tech. Inria Nancy Grand-Est, 2022. URL: https://hal.inria.fr/hal-03894581.

[90] Nazim FATÈS, Vincent CHEVRIER et Olivier BOURÉ. "A Trade-Off Between Simplicity and Robustness? Illustration on a Lattice-Gas Model of Swarming". In: *Probabilistic Cellular Automata: Theory, Applications and Future Perspectives*. Sous la dir. de Pierre-Yves LOUIS et Francesca R. NARDI. Springer, 2018, p. 239-259. DOI: 10.1007/978-3-319-65558-1_16.
[91] Nazim FATÈS et Lucas GERIN. "Examples of Fast and Slow Convergence of 2D Asynchronous Cellular Systems". In: *Journal of Cellular Automata* 4.4 (2009), p. 323-337.

[92] Nazim FATÈS et Irène MARCOVICI. "Automates cellulaires : la complexité dans les règles de l'art". In: *La Recherche* (juil. 2018). Réédition après changements mineurs dans le numéro spécial 31 en 2019., p. 67-71. URL: https://www.larecherche.fr/automates-cellulaires-la-complexit%C3%A9-dans-les-r%C3%A8gles-de-lart.

[93] Nazim FATÈS, Irène MARCOVICI et Siamak TAATI. "Two-Dimensional Traffic Rules and the Density Classification Problem". In: *Proceedings fo AUTOMATA 2016 – 22nd IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems*. Sous la dir. de Matthew COOK et Turlough NEARY. T. 9664. Lecture Notes in Computer Science. Springer, 2016, p. 135-148. DOI: 10.1007/978-3-319-39300-1_11.

[94] Nazim FATÈS, Irène MARCOVICI et Siamak TAATI. "Cellular Automata for the Self-stabilisation of Colourings and Tilings". In: *Proceedings of Reachability Problems – 13th International Conference, RP 2019*. Sous la dir. d'Emmanuel FILIOT, Raphaël M. JUNGERS et Igor POTAPOV. T. 11674. Lecture Notes in Computer Science. Springer, 2019, p. 121-136. DOI: 10.1007/978-3-030-30806-3_10.

[95] Nazim FATÈS, Irène MARCOVICI et Siamak TAATI. "Self-stabilisation of cellular automata on tilings". In: *Fundamenta Informaticae* 185-1 (2022). URL: https://fi.episciences.org/9184.

[96] Nazim FATÈS et Michel MORVAN. "An Experimental Study of Robustness to Asynchronism for Elementary Cellular Automata". In: *Complex Systems* 16 (2005), p. 1-27.

[97] Nazim FATÈS, Michel MORVAN, Nicolas SCHABANEL et Eric THIERRY. "Fully asynchronous behavior of double-quiescent elementary cellular automata". In: *Theoretical Computer Science* 362 (2006), p. 1-16. DOI: 10.1016/j.tcs.2006.05.036.

[98] Nazim FATÈS, Damien REGNAULT, Nicolas SCHABANEL et Eric THIERRY. "Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata." In: *Proceedings of LATIN 2006*. Sous la dir. de José R. CORREA, Alejandro HEVIA et Marcos A. KIWI. T. 3887. Lecture Notes in Computer Science. Springer, 2006, p. 455-466. DOI: 10.1007/11682462_43.

[99] Nazim FATÈS, Biswanath SETHI et Sukanta DAS. "On the Reversibility of ECAs with Fully Asynchronous Updating : The Recurrence Point of View". In: *Reversibility and Universality, Essays Presented to Kenichi Morita on the Occasion of his 70th Birthday*. Sous la dir. d'Andrew ADAMATZKY. T. 30. Emergence, Complexity and Computation. Springer, 2018, p. 313-332. DOI: 10.1007/978-3-319-73216-9.

[100] Nazim FATÈS et Nikolaos Vlassopoulos. "A Robust Scheme for Aggregating Quasi-Blind Robots in an Active Environment". In: *International Journal of Swarm Intelligence Research* 3.3 (2012), p. 66-80. DOI: 10.4018/jsir.2012070105.

[101] Li-Juan FEI, Jia LEE, Xin HUANG et Ferdinand PEPER. "Effect of random fluctuations on minimizing the complexity of universal asynchronous cellular automata". In: *Physica D: Nonlinear Phenomena* 428 (2021), p. 133052. DOI: 10.1016/j.physd.2021.133052.

[102] Jacques FERBER et Jean-Pierre MÜLLER. "Influences and Reaction : a Model of Situated Multiagent Systems". In: *Proceedings of the 2nd International Conference on Multi-agent Systems*. 1996, p. 72-79.
[103] Robert FISCH, Janko GRAVNER et David GRIFFEATH. "Metastability in the Greenberg-Hastings model". In: *The Annals of Applied Probability* 3.4 (1993), p. 935-967.

[104] Paola FLOCCHINI, Giuseppe PRENCIPE et Nicola SANTORO. *Distributed Computing by Oblivious Mobile Robots*. 1st. Morgan & Claypool Publishers, 2012.

[105] Paola FLOCCHINI, Giuseppe PRENCIPE, Nicola SANTORO et Peter WIDMAYER. "Gathering of asynchronous robots with limited visibility". In: *Theoretical Computer Science* 337.1-3 (2005), p. 147-168. DOI: 10.1016/j.tcs.2005.01.001.

[106] Enrico FORMENTI. "A Survey on m-Asynchronous Cellular Automata". In: *Proceedings of Automata'13*. Sous la dir. de Jarkko KARI, Martin KUTRIB et Andreas MALCHER. T. 8155. Lecture Notes in Computer Science. Springer, 2013, p. 46-66. DOI: 10.1007/978-3-642-40867-0.

[107] Jordina FRANCÈS DE MAS. "Coalescence in fully asynchronous elementary cellular automata". HAL 01627454. Mém. de mast. Université de Lorraine (Nancy), 2017. URL : https://hal.inria.fr/hal-01627454.

[108] Benjamin FRIEDRICH. "Hydrodynamic synchronization of flagellar oscillators". In: *The European Physical Journal Special Topics* 225.11 (2016), p. 2353-2368. DOI: 10.1140/epjst/e2016-60056-4.

[109] Henryk FUKŚ. "Solution of the density classification problem with two cellular automata rules". In: *Physical Review E* 55.3 (mar. 1997), R2081-R2084. DOI: 10.1103/PhysRevE.55.R2081.

[110] Henryk FUKŚ. "Nondeterministic density classification with diffusive probabilistic cellular automata". In: *Physical Review E* 66.6 (2002), p. 066106. DOI: 10.1103/PhysRevE.66.066106.

[111] Henryk FUKŚ et Nazim FATÈS. "Bifurcations of local structure maps as predictors of phase transitions in asynchronous cellular automata". In: *Proceedings of ACRI'14*. Sous la dir. de Jarosław WAS, Georgios Ch. SIRAKOULIS et Stefania BANDINI. T. 8751. Lecture Notes in Computer Science. Springer, 2014, p. 556-560. DOI: 10.1007/978-3-319-11520-7_58.

[112] Henryk FUKŚ et Roman PROCYK. "Explorations of ternary cellular automata and ternary density classification problems". In: *Acta Physica Polonica B – Proceedings Supplement* 12.1 (2019). arXiv:2002.08924, p. 75-89.

[113] Henryk FUKŚ et Andrew SKELTON. "Orbits of the Bernoulli measure in single-transition asynchronous cellular automata". In: *Proceedings of Automata'11*. Sous la dir. de Nazim FATÈS, Eric GOLES, Alejandro MAASS et Ivan RAPAPORT. Discrete Mathematics and Theoretical Computer Science Proceedings. DMTCS, 2011, p. 95-112. URL: http://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAP0107.

[114] Péter GÁCS. "Deterministic computations whose history is independent of the order of asynchronous updating". In: *Arxiv CoRR* cs.DC/0101026 (2001). URL: http://arxiv.org/abs/cs.DC/0101026.

[115] Peter GÁCS, Georgii L. KURDIUMOV et Leonid A. LEVIN. "One-Dimensional Homogeneous Media Dissolving Finite Islands". In: *Problemy Peredachi Informatsii* 14 (1987), p. 92-98.
[116] Anahí GAJARDO et Eric GOLES. "Dynamics of a class of ants on a one-dimensional lattice". In: *Theoretical Computer Science* 322.2 (2004), p. 267-283. DOI: 10.1016/j.tcs.2004.03.012.

[117] Anahí GAJARDO, Eric GOLES et Andrés MOREIRA. "Generalized Langton's Ant: Dynamical Behavior and Complexity". In: *Proceedings of STACS 2001*. Sous la dir. d'Afonso FERREIRA et Horst REICHEL. T. 2010. Lecture Notes in Computer Science. Springer, 2001, p. 259-270.

[118] Anahí GAJARDO, Eric GOLES et Andrés MOREIRA. "Complexity of Langton's ant". In: *Discrete Applied Mathematics* 117.1-3 (2002), p. 41-50.

[119] David GALE, Jim PROPP, Scott SUTHERLAND et Serge TROUBETZKOY. "Further Travels with My Ant". In: *Mathematical Entertainments column, Mathematical Intelligencer* 17 (1995), p. 48-56.

[120] Simon GARNIER, Maud COMBE, Christian JOST et Guy THERAULAZ. "Do Ants Need to Estimate the Geometrical Properties of Trail Bifurcations to Find an Efficient Route? A Swarm Robotics Test Bed". In: *PLOS Computational Biology* 9.3 (mar. 2013), p. 1-12. DOI: 10.1371/journal.pcbi.1002903.

[121] Melvin GAUCI. "Swarm Robotic Systems with Minimal Information Processing". Thèse de doct. UK: The University of Sheffield, 2014. URL: http://etheses.whiterose.ac.uk/7569/.

[122] Nicolas GAUVILLE, Nazim FATÈS et Irène MARCOVICI. "Diagnostic décentralisé à l'aide d'automates cellulaires". In: *Actes des JFSMA 2019 - 27èmes Journées Francophones sur les Systèmes Multi-Agents*. ISBN 9782364937192. Toulouse, France : Cépaduès, 2019, p. 96-105. URL: https://hal.inria.fr/hal-02195799.

[123] Reza GHARAVI et Venkat ANANTHARAM. "Effect of Noise on Long-term Memory in Cellular Automata with Asynchronous Delays between the Processors". In: *Complex Systems* 6.3 (1992), p. 287-300. URL: http://www.complex-systems.com/abstracts/v06_i03_a05.html.

[124] Ulrich GOLZE. "(A-)synchronous (non-)deterministic cell spaces simulating each other". In: *Journal of Computer and System Sciences* 17.2 (1978), p. 176-193.

[125] J. M. GREENBERG, B. D. HASSARD et S. P. HASTINGS. "Pattern formation and periodic structures in systems modeled by reaction-diffusion equations". In: *Bulletin of the American Mathematical Society* 84.6 (1978), p. 1296-1327.

[126] Carlos GRILO et Luís CORREIA. "Effects of asynchronism on evolutionary games". In: *Journal of Theoretical Biology* 269.1 (2011), p. 109-122. DOI: 10.1016/j.jtbi.2010.10.022.

[127] Yukio GUNJI. "Pigment color patterns of molluscs as an autonomous process generated by asynchronous automata". In: *Biosystems* 23.4 (1990), p. 317-334. DOI: 10.1016/0303-2647(90)90014-R.

[128] Howard A GUTOWITZ, Jonathan D VICTOR et Bruce W KNIGHT. "Local structure theory for cellular automata". In: *Physica D: Nonlinear Phenomena* 28.1-2 (1987), p. 18-48.
[129] Masami HAGIYA, Koichi TAKAHASHI, Mitsuharu YAMAMOTO et Takahiro SATO. "Analysis of Synchronous and Asynchronous Cellular Automata Using Abstraction by Temporal Logic". In: *Proceedings of FLOPS'04: Functional and Logic Programming*. Sous la dir. d'Yukiyoshi KAMEYAMA et Peter STUCKEY. T. 2998. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2004, p. 7-21. DOI: 10.1007/978-3-540-24754-8_2.

[130] Julia HANDL et Bernd MEYER. "Ant-based and swarm-based clustering". In : *Swarm Intelligence* 1.2 (2007), p. 95-113.

[131] Thomas HILLEN et Kevin J. PAINTER. "A user's guide to PDE models for chemotaxis". In : *Journal of Mathematical Biology* 58 (2009), p. 183-217.

[132] Haye HINRICHSEN. "Nonequilibrium Critical Phenomena and Phase Transitions into Absorbing States". In : *Advances in Physics* 49 (2000), p. 815-958.

[133] Jörg HOFFMANN, Nazim FATÈS et Héctor PALACIOS. "Brothers in Arms? On AI Planning and Cellular Automata". In: *Proceedings of ECAI 2010*. Sous la dir. d'Helder COELHO, Rudi STUDER et Michael WOOLDRIDGE. T. 215. Frontiers in Artificial Intelligence and Applications. IOS Press, 2010, p. 223-228. URL: http://www.booksonline.iospress.nl/Content/View.aspx?pid=17702.

[134] Taiga HONGU et Masami HAGIYA. "Self-stabilizing distributed algorithms by cellular automata". In: *Proceedings of AUTOMATA 2020*. Sous la dir. d'Hector ZENIL. Springer. 2020, p. 86-98.

[135] Xin HUANG, Jia LEE, Tian-Hao SUN et Ferdinand PEPER. "Self-adaptive self-reproductions in cellular automata". In: *Physica D* 263 (2013), p. 11-20. DOI: 10.1016/j.physd.2013.07.012.

[136] Bernardo A. HUBERMAN et Natalie GLANCE. "Evolutionary games and computer simulations". In: *Proceedings of the National Academy of Sciences, USA* 90 (1993), p. 7716-7718.

[137] Gabriel ISTRATE. "Stochastic Stability in Schelling's Segregation Model with Markovian Asynchronous Update". In: *Proceedings of ACRI 2018*. Sous la dir. de Giancarlo MAURI, Samira EL YACOUBI, Alberto DENNUNZIO, Katsuhiro NISHINARI et Luca MANZONI. T. 11115. Lecture Notes in Computer Science. Springer, 2018, p. 416-427. DOI: 10.1007/978-3-319-99813-8_38.

[138] Yasusi KANADA. "The Effects of Randomness in Asynchronous 1D Cellular Automata (Poster)". In: *Artificial Life IV* (1994). URL: http://www.kanadas.com/CA/AsyncCA/AsyncCAext.pdf.

[139] Jarkko KARI. "Theory of cellular automata : A survey". In: *Theoretical Computer Science* 334.1-3 (2005), p. 3-33. DOI: 10.1016/j.tcs.2004.11.021.

[140] Evelyn F. KELLER et Lee A. SEGEL. "Travelling Bands of Chemotactic Bacteria : A Theoretical Analysis". In : *Journal of Theoretical Biology* 30.2 (1971), p. 235-248.

[141] Wolfgang KINZEL. "Directed Percolation". In: *Percolation Structures and Processes*. Sous la dir. de R. Zallen G. DEUTSCHER et J. ADLER. Bristol : Adam Hilger Pub. Co., 1983, p. 425.

[142] Petr KŮRKA. "Languages, equicontinuity and attractors in cellular automata". In: *Ergodic Theory and Dynamical Systems* 17.2 (1997), p. 417-433. DOI: 10.1017/S014338579706985X.

[143] Ingo KUSCH et Mario MARKUS. "Mollusc Shell Pigmentation : Cellular Automaton Simulations and Evidence for Undecidability". In : *Journal of Theoretical Biology* 178.3 (1996), p. 333-340. DOI: 10.1006/jtbi.1996.0029.
[144] Dietrich KUSKE. "Emptiness Is Decidable for Asynchronous Cellular Machines". In: *Proceedings of CONCUR 2000 — Concurrency Theory*. Sous la dir. de Catuscia PALAMIDESSI. T. 1877. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2000, p. 536-551. DOI: 10.1007/3-540-44618-4_38.

[145] Dietrich KUSKE. "Weighted asynchronous cellular automata". In: *Theoretical Computer Science* 374.1-3 (2007), p. 127-148. DOI: 10.1016/j.tcs.2006.11.031.

[146] Mark LAND et Richard K. BELEW. "No Perfect Two-State Cellular Automata for Density Classification Exists". In: *Physical Review Letters* 74.25 (1995), p. 5148-5150. DOI: 10.1103/PhysRevLett.74.5148.

[147] Christopher G. LANGTON. "Studying Artificial Life with Cellular Automata". In: *Physica D* 22 (1981), p. 120-149.

[148] Gérard LE CAËR. "Comparison between simultaneous and sequential updating in $2^{n+1}$—1 cellular automata". In: *Physica A* 157.2 (1989), p. 669-687. DOI: 10.1016/0378-4371(89)90061-7.

[149] Jia LEE. "A Simple Model of Asynchronous Cellular Automata Exploiting Fluctuation". In: *Journal of Cellular Automata* 6.4-5 (2011), p. 341-352. URL: http://www.oldcitypublishing.com/JCA/JCAabstracts/JCA6.4-5abstracts/JCAv6n4-5p341-352Lee.html.

[150] Jia LEE, Susumu ADACHI et Ferdinand PEPER. "Reliable Self-Replicating Machines in Asynchronous Cellular Automata". In: *Artificial Life* 13.4 (2007), p. 397-413. DOI: 10.1162/artl.2007.13.4.397.

[151] Jia LEE, Susumu ADACHI, Ferdinand PEPER et Shinro MASHIKO. "Delay-insensitive computation in asynchronous cellular automata". In: *Journal of Computer and System Sciences* 70.2 (2005), p. 201-220. DOI: 10.1016/j.jcss.2004.10.009.

[152] Jia LEE, Susumu ADACHI, Ferdinand PEPER et Kenichi MORITA. "Asynchronous game of life". In: *Physica D* 194.3-4 (2004), p. 369-384. DOI: 10.1016/j.physd.2004.03.007.

[153] Jia LEE, Katsunobu IMAI et Qing-sheng ZHU. "Fluctuation-driven computing on number-conserving cellular automata". In: *Information Sciences* 187 (2012), p. 266-276. DOI: 10.1016/j.ins.2011.10.017.

[154] Jia LEE et Qing-Sheng ZHU. "A Direct Proof of Turing Universality of Delay-Insensitive Circuits". In: *International Journal of Unconventional Computing* 8.2 (2012), p. 107-118. URL: http://www.oldcitypublishing.com/IJUC/IJUCabstracts/IJUC8.2abstracts/IJUCv8n2p107-118Lee.html.

[155] Qin LEI, Tao LI, Jia LEE, Wen-Li XU et Ferdinand PEPER. "Asynchronous communicating cellular automata: Formalization, robustness and equivalence". In: *Information Sciences* 587 (2022), p. 335-353. DOI: 10.1016/j.ins.2021.12.036.

[156] Thomas Milton LIGGETT. *Interacting particle systems*. T. 2. Springer, 1985.

[157] R.J. LIPTON, R.E. MILLER et L. SNYDER. "Synchronization and computing capabilities of linear asynchronous structures". In: *Journal of Computer and System Sciences* 14.1 (1977), p. 49-72. DOI: 10.1016/S0022-0000(77)80040-8.

[158] Erik D. LUMER et Grégoire NICOLIS. "Synchronous versus asynchronous dynamics in spatially distributed systems". In: *Physica D: Nonlinear Phenomena* 71.4 (1994), p. 440-452. DOI: 10.1016/0167-2789(94)90010-8.
[159] Matthew MACAULEY, Jon MCCAMMOND et Henning MORTVEIT. "Dynamics groups of asynchronous cellular automata". In : *Journal of Algebraic Combinatorics* 33.1 (2011), p. 11-35. DOI: 10.1007/s10801-010-0231-y.

[160] Matthew MACAULEY, Jon MCCAMMOND et Henning S. MORTVEIT. "Order Independence in Asynchronous Cellular Automata". In : *Journal of Cellular Automata* 3.1 (2008), p. 37-56. URL : http://www.oldcitypublishing.com/JCA/JCAabstracts/JCA3.1abstracts/JCAv3n1p37-56Macauley.html.

[161] Matthew MACAULEY et Henning S. MORTVEIT. "Coxeter Groups and Asynchronous Cellular Automata". In : *Proceedings of ACRI'10*. Sous la dir. de Stefania BANDINI, Sara MANZONI, Hiroshi UMEO et Giuseppe VIZZARI. T. 6350. Lecture Notes in Computer Science. Springer, 2010, p. 409-418. DOI: 10.1007/978-3-642-15979-4_43.

[162] Jean MAIRESSE et Irène MARCOVICI. "Around probabilistic cellular automata". In : *Theoretical Computer Science* 559.0 (2014), p. 42-72. DOI: 10.1016/j.tcs.2014.09.009.

[163] Danuta MAKOWIEC. "Cellular automata model of cardiac pacemaker". In : *Acta Physica Polonica B* 39.5 (2008), p. 1067-1085.

[164] Diego MALDONADO, Anahí GAJARDO, Benjamin HELLOUIN DE MENIBUS et Andrés MOREIRA. "Nontrivial Turmites are Turing-universal". In : *Journal of Cellular Automata* 13.5-6 (2018), p. 373-392. URL : http://www.oldcitypublishing.com/journals/jca-home/jca-issue-contents/jca-volume-13-number-5-6-2018/jca-13-5-6-p-373-392/.

[165] Marco MAMEI, Andrea ROLI et Franco ZAMBONELLI. "Emergence and control of macrospatial structures in perturbed cellular automata, and implications for pervasive computing systems." In : *IEEE Transactions on Systems, Man, and Cybernetics, Part A* 35.3 (2005), p. 337-348. DOI: 10.1109/TSMCA.2005.846379.

[166] Luca MANZONI. "Asynchronous cellular automata and dynamical properties". In : *Natural Computing* 11.2 (2012), p. 269-276. DOI: 10.1007/s11047-012-9308-y.

[167] Irène MARCOVICI. "Automates cellulaires probabilistes et mesures spécifiques sur des espaces symbolique". texte en anglais. Thèse de doct. Université Paris 7, 2013.

[168] Irène MARCOVICI. "Entre aléa et déterminisme : lumière sur quelques structures discrètes". Habilitation à diriger des recherches. Université de Lorraine (Nancy), 2021. URL : https://hal.science/tel-03480298.

[169] Genaro MARTÍNEZ. "A Note on Elementary Cellular Automata Classification". In : *Journal of Cellular Automata* 8.34 (2013). preprint on arXiv 1306.5577, p. 233-259.

[170] Nesrine MASMOUDI. "Modèle bio-inspiré pour le clustering de graphes : application à la fouille de données et à la distribution de simulations". Thèse de doctorat. Normandie Université ; Université de Sfax (Tunisie), 2017. URL : https://tel.archives-ouvertes.fr/tel-01745613.

[171] Susanna M. MESSINGER, Keith A. MOTT et David PEAK. "Task-performing dynamics in irregular, biomimetic networks : Research Articles". In : *Complexity* 12.6 (2007), p. 14-21. DOI: 10.1002/cplx.v12:6.

[172] Cristopher MOORE et Stephan MERTENS. *The Nature of Computation*. Oxford University Press, 2011.
[173] Kenichi MORITA. "Reversible computing and cellular automata — A survey". In: *Theoretical Computer Science* 395.1 (2008), p. 101-131. DOI: 10.1016/j.tcs.2008.01.041.

[174] Anca MUSCHOLL. "On the complementation of Büchi asynchronous cellular automata". In: *Automata, Languages and Programming*. Sous la dir. de Serge ABITEBOUL et Eli SHAMIR. T. 820. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 1994, p. 142-153. DOI: 10.1007/3-540-58201-0_64.

[175] Katsuhiko NAKAMURA. "Synchronous to asynchronous transformation of polyautomata". In: *Journal of Computer and System Sciences* 23.1 (1981), p. 22-37. DOI: 10.1016/0022-0000(81)90003-9.

[176] Katsuo NAKAMURA. "Asynchronous Cellular Automata and Their Computational Ability". In: *Systems, Computers, Controls* 5.5 (1974), p. 58-66.

[177] Satyasai Jagannath NANDA et Ganapati PANDA. "A survey on nature inspired meta-heuristic algorithms for partitional clustering". In: *Swarm and Evolutionary Computation* 16 (2014), p. 1-18. DOI: 10.1016/j.swevo.2013.11.003.

[178] Chrystopher L. NEHANIV. "Evolution in asynchronous cellular automata". In: *Proceedings of the eighth international conference on Artificial life*. MIT Press, 2003, p. 65-73.

[179] Chrystopher L. NEHANIV. "Asynchronous Automata Networks Can Emulate any Synchronous Automata Network". In: *International Journal of Algebra and Computation* 14.5-6 (2004), p. 719-739. DOI: 10.1142/S0218196704002043.

[180] T. J. NEWMAN et R. GRIMA. "Many-body theory of chemotactic cell-cell interactions". In: *Physical Review E* 70.5 (2004), p. 051916.

[181] David NEWTH et David CORNFORTH. "Asynchronous spatial evolutionary games". In: *Biosystems* 95.2 (2009), p. 120-129. DOI: 10.1016/j.biosystems.2008.09.003.

[182] Mathilde NOUAL. "Synchronism vs Asynchronism in Boolean networks". In: *CoRR* abs/1104.4039 (2011). URL: http://arxiv.org/abs/1104.4039.

[183] Mathilde NOUAL. "Mise à jour de réseaux d'automates". Thèse de doct. Ecole normale supérieure de Lyon - ENS LYON, 2012. URL: https://tel.archives-ouvertes.fr/tel-00726560.

[184] Géza ÓDOR. "Universality Classes in nonequilibrium systems". In: *Reviews of modern physics* 76 (2004).

[185] Pedro P. B. de OLIVEIRA. "On Density Determination With Cellular Automata: Results, Constructions and Directions." In: *Journal of Cellular Automata* 9.5-6 (2014), p. 357-385.

[186] Pedro Paulo Balbi de OLIVEIRA, Enrico FORMENTI, Kévin PERROT, Sara RIVA et Eurico L. P. RUIVO. "Non-maximal Sensitivity to Synchronism in Periodic Elementary Cellular Automata: Exact Asymptotic Measures". In: *Proceedings of AUTOMATA 2020*. Sous la dir. d'Hector ZENIL. T. 12286. Lecture Notes in Computer Science. Version longue en ligne sur Arxiv https://arxiv.org/abs/2004.07128. Springer, 2020, p. 14-28. DOI: 10.1007/978-3-030-61588-8_2.

[187] Nicolas OLLINGER et Gaétan RICHARD. "Four states are enough!" In: *Theoretical Computer Science* 412.1-2 (2011), p. 22-32.

[188] Hans G. OTHMER et Angela STEVENS. "Aggregation, Blowup, and Collapse: The ABC's of Taxis in Reinforced Random Walks". In: *SIAM Journal of Applied Mathematics* 57.4 (1997), p. 1044-1081.
[189] Norman H. PACKARD. "Dynamic Patterns in Complex Systems". In: Singapore: World Scientific, 1988. Chap. Adaptation toward the edge of chaos, p. 293-301.

[190] Ferdinand PEPER, Susumu ADACHI et Jia LEE. "Variations on the Game of Life". In: *Game of Life Cellular Automata*. Sous la dir. d'Andrew ADAMATZKY. Springer London, 2010, p. 235-255. DOI: 10.1007/978-1-84996-217-9_13.

[191] Ferdinand PEPER, Teijiro ISOKAWA, Noriaki KOUDA et Nobuyuki MATSUI. "Self-Timed Cellular Automata and their computational ability". In: *Future Generation Computer Systems* 18.7 (2002), p. 893-904. DOI: 10.1016/S0167-739X(02)00069-9.

[192] Ferdinand PEPER, Jia LEE et Teijiro ISOKAWA. "Brownian Cellular Automata". In: *Journal of Cellular Automata* 5.3 (2010), p. 185-206.

[193] Kévin PERROT, Marco MONTALVA-MEDEL, Pedro PB DE OLIVEIRA et Eurico LP RUIVO. "Maximum sensitivity to update schedules of elementary cellular automata over periodic configurations". In: *Natural Computing* 19.1 (2020), p. 51-90.

[194] Giovanni PIGHIZZINI. "Asynchronous Automata Versus Asynchronous Cellular Automata". In: *Theoretical Computer Science* 132.2 (1994), p. 179-207. DOI: 10.1016/0304-3975(94)90232-1.

[195] Arkady PIKOVSKY, Michael ROSENBLUM et Jürgen KURTHS. *Synchronization: a universal concept in nonlinear sciences*. T. 12. Cambridge university press, 2003.

[196] Giuseppe PRENCIPE. "Impossibility of gathering by a set of autonomous mobile robots". In: *Theoretical Computer Science* 384.2-3 (2007), p. 222-231. DOI: 10.1016/j.tcs.2007.04.023.

[197] Lutz PRIESE. "A note on asynchronous cellular automata". In: *Journal of Computer and System Sciences* 17.2 (1978), p. 237-252. DOI: 10.1016/0022-0000(78)90007-7.

[198] Filippo RADICCHI, Daniele VILONE et Hildegard MEYER-ORTMANNS. "Phase Transition between Synchronous and Asynchronous Updating Algorithms". In: *Journal of Statistical Physics* 129.3 (2007), p. 593-603. DOI: 10.1007/s10955-007-9416-8.

[199] N. RAJEWSKY, L. SANTEN, A. SCHADSCHNEIDER et M. SCHRECKENBERG. "The Asymmetric Exclusion Process: Comparison of Update Procedures". In: *Journal of Statistical Physics* 92.1-2 (1998), p. 151-194. DOI: 10.1023/A:1023047703307.

[200] Nikolaus RAJEWSKY et Michael SCHRECKENBERG. "Exact results for one-dimensional cellular automata with different types of updates". In: *Physica A* 245.1-2 (1997), p. 139-144. DOI: 10.1016/S0378-4371(97)00010-1.

[201] Damien REGNAULT. "Directed Percolation Arising in Stochastic Cellular Automata Analysis". In: *Mathematical Foundations of Computer Science 2008*. Sous la dir. d'Edward OCHMAŃSKI et Jerzy TYSZKIEWICZ. Springer Berlin Heidelberg, 2008, p. 563-574.

[202] Damien REGNAULT. "Sur les automates cellulaires probabilistes: comportements asynchrones". 07ENSL0 494. Thèse de doct. École normale supérieure deyon, 2008.

[203] Damien REGNAULT. "Proof of a Phase Transition in Probabilistic Cellular Automata". In: *Proceedings of Developments in Language Theory*. Sous la dir. de Marie-Pierre BÉAL et Olivier CARTON. T. 7907. Lecture Notes in Computer Science. Springer, 2013, p. 433-444. DOI: 10.1007/978-3-642-38771-5.

[204] Damien REGNAULT, Nicolas SCHABANEL et Eric THIERRY. "Progresses in the analysis of stochastic 2D cellular automata: A study of asynchronous 2D minority". In: *Theoretical Computer Science* 410.47-49 (2009), p. 4844-4855. DOI: 10.1016/j.tcs.2009.06.024.
[205] Leonardo REYES et David LAROZE. "Cellular Automata for excitable media on a Complex Network: The effect of network disorder in the collective dynamics". In: *Physica A: Statistical Mechanics and its Applications* 588 (2022), p. 126552. DOI: 10.1016/j.physa.2021.126552.

[206] Leonardo I. REYES. "Greenberg-Hastings dynamics on a small-world network: the collective extinct-active transition". arXiv 1505.00182. 2017.

[207] Gaétan RICHARD. "On the Synchronisation Problem over Cellular Automata". In: *Proceedings of STACS 2017*. Sous la dir. d'Heribert VÖLLMER et Brigitte VALLÉE. T. 66. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017, 54:1-54:13.

[208] D. RICHARDSON. "Tessellations with local transformations". In: *Journal of Computer Systems and Sciences* 6 (1972), p. 373-388.

[209] Pejman ROHANI, Timothy J. LEWIS, Daniel GRÜNBAUM et Graeme D. RUXTON. "Spatial self-organisation in ecology : pretty patterns or robust reality?" In : *Trends in Ecology & Evolution* 12.2 (1997), p. 70-74.

[210] Juri ROLF, Tomas BOHR et Mogens H. JENSEN. "Directed percolation universality in asynchronous evolution of spatiotemporal intermittency". In : *Physical Review E*. 57.3 (1998), R2503-R2506.

[211] Jean-Baptiste ROUQUIER. "Robustesse et émergence dans les systèmes complexes : le modèle des automates cellulaires". Thèse de doct. École Normale Supérieure de Lyon, 2008. URL: http://tel.archives-ouvertes.fr/tel-00354042.

[212] Jean-Baptiste ROUQUIER. "An exhaustive experimental study of synchronization by forcing on elementary cellular automata". In: *Proceedings of the First Symposium on Cellular Automata "Journées Automates Cellulaires" (JAC 2008)*. MCCME Publishing House, Moscow, 2009, p. 250-261.

[213] Jean-Baptiste ROUQUIER et Michel MORVAN. "Coalescing Cellular Automata : Synchronization by Common Random Source for Asynchronous Updating". In: *Journal of Cellular Automata* 4.1 (2009), p. 55-78. URL: http://www.oldcitypublishing.com/JCA/JCAabstracts/JCA4.1abSTRACTS/JCAv4n1p55-77Rouquier.html.

[214] Jean-Baptiste ROUQUIER, Damien REGNAULT et Éric THIERRY. "Stochastic minority on graphs". In: *Theoretical Computer Science* 412.30 (2011), p. 3947-3963. DOI: 10.1016/j.tcs.2011.02.028.

[215] Eurico L.P. RUIVO et Pedro P.B. de OLIVEIRA. "A perfect solution to the parity problem with elementary cellular automaton 150 under asynchronous update". In: *Information Sciences* 493 (2019), p. 138-151. DOI: 10.1016/j.ins.2019.04.045.

[216] Graeme RUXTON et Leonardo SARAVIA. "The need for biological realism in the updating of cellular automata models". In: *Ecological Modelling* 107.2 (1998), p. 105-112.

[217] M. Ali SAIF et Prashant M. GADE. "The prisoner's dilemma with semi-synchronous updates : evidence for a first-order phase transition". In: *Journal of Statistical Mechanics : Theory and Experiment* 2009.7 (2009), P07023. DOI: 10.1088/1742-5468/2009/07/P07023.

[218] Amaury SAINT-JORE, Nazim FATÈS et Emmanuel JEANDEL. "Amoebae for clustering : a bio-inspired cellular automata method for data classification". preprint. 2020. URL : https://hal.inria.fr/hal-02973830.
[219] Ville SALO et Ilkka TÖRMÄ. "Color Blind Cellular Automata". In: *Journal of Cellular Automata* 9.5-6 (2014), p. 477-509.

[220] Andaç T ŞAMILOĞLU, Veysel GAZI et A Buğra KOKU. "Effects of Asynchronism and Neighborhood Size on Clustering in Self-propelled Particle Systems". In: *Proceedings of ISCIS 2006*. Sous la dir. d'Albert LEVI, Erkay SAVAŞ, Hüsnü YENIGÜN, Selim BALCISOY et Yücel SAYGIN. T. 4263. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2006, p. 665-676. DOI: 10.1007/11902140_70.

[221] J. R. SÁNCHEZ et R. LÓPEZ-RUIZ. "Self-synchronization of Cellular Automata: An Attempt to Control Patterns". In: *Proceedings of the 6th International Conference on Computational Science - Part III*. Sous la dir. de Vassil N. ALEXANDROV, G. Dick van ALBADA, Peter M. A. SLOOT et Jack DONGARRA. T. 3993. Lecture Notes in Computer Science. Springer, 2006, p. 353-359. DOI: 10.1007/11758532_48.

[222] Bruno SCHERRER. "Asynchronous neurocomputing for optimal control and reinforcement learning with large state spaces". In: *Neurocomputing* 63 (2005), p. 229-251. DOI: 10.1016/j.neucom.2004.01.192.

[223] Oliver SCHNEIDER et Thomas WORSCH. "A 3-State Asynchronous CA for the Simulation of Delay-Insensitive Circuits". In: *Proceedings of ACRI'12*. Sous la dir. de Georgios Ch. SIRAKOULIS et Stefania BANDINI. T. 7495. Lecture Notes in Computer Science. Springer, 2012, p. 565-574. DOI: 10.1007/978-3-642-33350-7_58.

[224] Birgitt SCHÖNFISCH et André de ROOS. "Synchronous and asynchronous updating in cellular automata". In: *BioSystems* 51 (1999), p. 123-143.

[225] Martin SCHÜLE. "Natural computation". Thèse de doct. Eidgenössische Technische Hochschule (ETH) Zürich, 2012. DOI: 10.3929/ethz-a-009787778.

[226] Martin SCHÜLE, Thomas OTT et Ruedi STOOP. "Computing with Probabilistic Cellular Automata". In: *ICANN '09: Proceedings of the 19th International Conference on Artificial Neural Networks*. Limassol, Cyprus: Springer-Verlag, 2009, p. 525-533.

[227] Martin SCHÜLE et Ruedi STOOP. "A full computation-relevant topological dynamics classification of elementary cellular automata". In: *Chaos* 22.4, 043143 (2012), p. 043143. DOI: 10.1063/1.4771662.

[228] Biswanath SETHI, Nazim FATÈS et Sukanta DAS. "Reversibility of Elementary Cellular Automata under Fully Asynchronous Update". In: *Proceedings of TAMC'14*. Sous la dir. de T.V. GOPAL, Manindra AGRAWAL, Angsheng LI et Barry COOPER. T. 8402. Lecture Notes in Computer Science. Springer, 2014, p. 39-49. DOI: 10.1007/978-3-319-06089-7_4.

[229] Fernando SILVA et Luís CORREIA. "An experimental study of noise and asynchrony in elementary cellular automata with sampling compensation". In: *Natural Computing* 12.4 (2013), p. 573-588. DOI: 10.1007/s11047-013-9387-4.

[230] Matthew J. SIMPSON, Alistair MERRIFIELD, Kerry A. LANDMAN et Barry D. HUGHES. "Simulating invasion with cellular automata: Connecting cell-scale and population-scale properties". In: *Physical Review E* 76.2, 021918 (2007), p. 021918.

[231] Alvy Ray SMITH III. "Two-Dimensional Formal Languages and Pattern Recognition by Cellular Automata". In: *FOCS*. 1971, p. 144-152.
[232] Daniel SOTO FORERO et Yony CEBALLOS. "Behavior of stochastic reaction-diffusion process in a random network with dynamic links". In: *IAENG International Journal of Computer Science* 3.48 (2021), p. 1-7.

[233] Antoine SPICHER, Nazim FATÈS et Olivier SIMONIN. "Translating Discrete Multi-Agents Systems into Cellular Automata: Application to Diffusion-Limited Aggregation". In: *Agents and Artificial Intelligence*. Sous la dir. de Joaquim FILIPE, Ana FRED et Bernadette SHARP. T. 67. Communications in Computer and Information Science. Springer Berlin Heidelberg, 2010, p. 270-282. DOI: 10.1007/978-3-642-11819-7_21.

[234] W. Richard STARK. "Amorphous computing : examples, mathematics and theory". In : *Natural Computing* 12.3 (2013), p. 377-392. DOI: 10.1007/s11047-013-9370-0.

[235] W. Richard STARK et William H. HUGHES. "Asynchronous, irregular automata nets : the path not taken". In : *BioSystems* 55 (2000), p. 107-117.

[236] Kazuo SUGIHARA et Ichiro SUZUKI. "Distributed motion coordination of multiple mobile robots". In : *Proceedings of 5th IEEE International Symposium on Intelligent Control*. 1990, p. 138-143.

[237] Tomoaki SUZUDO. "Searching for Pattern-Forming Asynchronous Cellular Automata - An Evolutionary Approach". In : *Proceedings of ACRI'04*. Sous la dir. de Peter M. A. SLOOT, Bastien CHOPARD et Alfons G. HOEKSTRA. T. 3305. Lecture Notes in Computer Science. Springer, 2004, p. 151-160. DOI: 10.1007/978-3-540-30479-1_16.

[238] Tomoaki SUZUDO. "Spatial pattern formation in asynchronous cellular automata with mass conservation". In : *Physica A : Statistical Mechanics and its Applications* 343 (2004), p. 185-200. DOI: 10.1016/j.physa.2004.06.067.

[239] Wahiba TAOUALI, Thierry VIÉVILLE, Nicolas P. ROUGIER et Frédéric ALEXANDRE. "No clock to rule them all". In : *Journal of Physiology - Paris* 105.1-3 (2011), p. 83-90. DOI : 10.1016/j.jphysparis.2011.08.005.

[240] Tommaso TOFFOLI. "Computation and construction universality of reversible cellular automata". In : *Journal of Computer Systems and Sciences* 15 (1977), p. 213-231.

[241] Tommaso TOFFOLI. "Integration of the Phase-Difference Relations in Asynchronous Sequential Networks". In : *Proceedings of the Fifth Colloquium on Automata, Languages and Programming*. Sous la dir. de Giorgio AUSIELLO et Corrado BÖHM. T. 62. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 1978, p. 457-463. DOI: 10.1007/3-540-08860-1_34.

[242] Marco TOMASSINI et Mattias VENZI. "Artificially Evolved Asynchronous Cellular Automata for the Density Task". In : *Proceedings of ACRI 2002*. Sous la dir. de Stefania BANDINI, Bastien CHOPARD et Marco TOMASSINI. T. 2493. Lecture Notes in Computer Science. Springer, 2002, p. 44-55. DOI: 10.1007/3-540-45830-1_5.

[243] Predrag T. TOŠIĆ. "On Modeling Large-Scale Multi-Agent Systems with Parallel, Sequential and Genuinely Asynchronous Cellular Automata". In : *Acta Physica Polonica B - Proceedings Supplement* 4.2 (2011), p. 217-235. DOI: 10.5506/APhysPolBSupp.4.217.

[244] Alan M. TURING. "The chemical basis of morphogenesis". In : *Philosophical Transactions of the Royal Society (London)* 237 (1952), p. 5-72.

[245] Leonardo VANNESCHI et Giancarlo MAURI. "A study on learning robustness using asynchronous 1D cellular automata rules". In : *Natural Computing* 11.2 (2012), p. 289-302. DOI: 10.1007/s11047-012-9311-3.
[246] Massimo VERGASSOLA, Emmanuel VILLERMAUX et Boris I. SHRAIMAN. "'Infotaxis' as a strategy for searching without gradients". In: *Nature* 445.7126 (2007), p. 406-409. DOI: 10.1038/nature05464.

[247] Michael VIELHABER. "Computation of functions on n bits by asynchronous clocking of cellular automata". In : *Natural Computing* 12.3 (2013), p. 307-322. DOI : 10.1007/s11047-013-9376-7.

[248] Nikolaos VLASSOPOULOS, Nazim FATÈS, Hugues BERRY et Bernard GIRAU. "An FPGA Design for the stochastic Greenberg-Hastings Cellular Automata". In : *International Conference on High Performance Computing and Simulation*. Sous la dir. de Waleed SMARI. New Jersey, USA : IEEE, 2010, p. 565-574.

[249] Nikolaos VLASSOPOULOS, Nazim FATÈS, Hugues BERRY et Bernard GIRAU. "Large-scale Simulations on FPGAs : Finding the Asymptotic Critical Threshold of the Greenberg-Hastings Cellular Automata". In : *Journal of Cellular Automata* 7.1 (2012), p. 5-29.

[250] John VON NEUMANN. *Theory of self-reproducing automata*. A. Burks (editor). University of Illinois press Urbana, 1966.

[251] Weiguo WANG. "An asynchronous two-dimensional self-correcting cellular automaton". In : *Proceedings of FOCS'91 (Foundations of Computer Science)*. IEEE Computer Society, 1991, p. 278-285. DOI: 10.1109/SFCS.1991.185379.

[252] Xingyuan WANG et Dahai XU. "A novel image encryption scheme using chaos and Langton's Ant cellular automaton". In : *Nonlinear Dynamics* 79.4 (2014), p. 2449-2456. DOI: 10.1007/s11071-014-1824-0.

[253] Barbara WOLNIK et Bernard DE BAETS. "Ternary reversible number-conserving cellular automata are trivial". In : *Information Sciences* 513 (2020), p. 180-189. DOI: 10.1016/j.ins.2019.10.068.

[254] Thomas WORSCH. "Towards intrinsically universal asynchronous CA". In : *Natural Computing* 12.4 (2013), p. 539-550. DOI: 10.1007/s11047-013-9388-3.
Résumé

Ce mémoire présente une sélection de travaux sur les automates cellulaires et les systèmes complexes discrets. Nous nous intéressons au thème de la robustesse de ces systèmes, à travers l'utilisation de règles asynchrones ou probabilistes. Nous partons du problème de l'analyse et de la classification des automates cellulaires élémentaires asynchrones. Différentes techniques issues de la théorie des probabilités, chaînes de Markov et martingales, sont mises en œuvre pour expliquer les propriétés de convergence de ces systèmes. Dans la deuxième partie, nous présentons des modèles plus complexes, pour lesquels l'estimation de la robustesse se fait principalement à l'aide de simulations numériques. Les expériences montrent des phénomènes collectifs variés et des réponses aux changements difficiles à prédire par l'analyse des règles locales. Dans la troisième partie, l'exploration se poursuit en présentant trois problèmes inverses, problèmes où l'on cherche à trouver des règles qui réalisent un « calcul » sous forme d'un consensus entre cellules ou entre agents. L'ensemble des travaux présentés permet de parcourir différents modèles discrets avec des approches complémentaires. Nous creusons ainsi la question posée par Turing en 1952 où celui-ci évoquait un rôle constructif de l'aléa dans son article sur la morphogenèse.

**Mots-clés:** automates cellulaires, systèmes complexes discrets, robustesse des systèmes dynamiques

Abstract

This thesis presents a selection of research works on the theme of cellular automata and discrete complex systems. We are interested in the robustness of these systems, mainly through the use of asynchronous or probabilistic rules. We start from the problem of analysing and classifying the dynamics of asynchronous elementary cellular automata. We use techniques from probability theory such as Markov chains and martingales in order to understand the convergence properties of such systems. In the second part, we present models which are more complex locally and we estimate their robustness properties mainly with numerical simulations. Experiments show that the various collective phenomena we observe have responses to perturbations which are difficult to predict from the analysis of their local rule. The third parts consists of the presentation of three inverse problems, where one seeks to find the rules that produce a given behaviour, here a consensus on the state of the cells or the agents. The overall variety of models that are discussed in the thesis allow us to study a variety of models with complementary techniques, thus following the path opened by Alan Turing in his 1952 article on morphogenesis.

**Keywords:** cellular automata, discrete complex systems, robustness of dynamical systems