\( \newcommand{\llbracket}{[\![} \newcommand{\rrbracket}{]\!]} \renewcommand{\epsilon}{\varepsilon} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\NN}{\mathbb{N}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\RR}{\mathbb{R}} \newcommand{\ACA}{\mathcal{A}} \newcommand{\ACC}{\mathcal{C}} \newcommand{\ACV}{\mathcal{V}} \newcommand{\ACQ}{\mathcal{Q}} \)

Automates cellulaires :
Décidabilité en 1D

Cours M2 - MIT
Victor Poupet

Graphes de de Bruijn

En dimension 1, on peut utiliser les graphes de de Bruijn pour représenter la dynamique des automates cellulaires.

Définition
Le graphe de de Bruijn d’ordre \(n\) sur l’alphabet \(\Sigma\) est le graphe orienté \((V, E)\) où
  • \(V = \Sigma^n\)
  • \(E = \{(au,ub),\ a,b ∈ \Sigma, u ∈ \Sigma^{n−1}\}\)

Surjectivité

preuve de K. Sutner (1991)

Étant donné un AC $$\ACA = (1,\ACQ,\ACV,δ)$$

Soit \(n\) le diamètre de \(V\), on considère le graphe de de Bruijn d’ordre \((n − 1)\) sur l’alphabet \(\ACQ\)


  • on étiquette l’arête \((au, ub)\) par \(δ(aub)\)
  • on obtient un automate fini
  • on considère tous les états comme étant initiaux et finals

✎ Le mot \(w ∈ \ACQ^*\) est reconnu par l’automate ssi il existe une configuration dont l’image contient \(w\)

✎ L’automate fini reconnaît tout \(\ACQ^*\) ssi l’AC est surjectif

Th. (Amoroso & Patt, 1972)
La surjectivité d’un automate cellulaire en dimension 1 est décidable.

Injectivité

preuve de K. Sutner (1991)

Soient \(\ACC_1, \ACC_2 ∈ \ACQ^\ZZ\), avec $$\ACA(\ACC_1) = \ACA(\ACC_2)$$

Deux cas possibles :

  • \(\ACC_1\) et \(\ACC_2\) diffèrent en un nombre fini de cellules
  • \(\ACC_1\) et \(\ACC_2\) diffèrent inifiniment souvent

Graphe \((V, E)\)

  • \(V =\{(u, v) ∈ \Sigma^n × \Sigma^n\}\)
  • on connecte les paires
    \(\left(\begin{array}{cc} au\\a'u'\end{array}\right)\) et \(\left(\begin{array}{cc} ub\\u'b'\end{array}\right)\)
    si \(δ(aub) = δ(a'u'b')\)

✎ Un AC est injectif sur les configurations périodiques ssi le graphe n’a pas de cycle contenant un sommet \((u, v)\) avec \(u \neq v\)

Th. (Amoroso & Patt, 1972)
L’injectivité d’un automate cellulaire en dimension 1 est décidable
Prop. (Culik, 1987)
Un automate cellulaire est injectif ssi il est injectif sur les configurations périodiques

Généralisation

Les preuves de Sutner se généralisent à toute propriété du premier ordre sur l’espace des configurations

Théorème (K. Sutner, 2009)
La logique du premier ordre sur les configurations d’automates cellulaires en dimension 1, munie de la relation de successeur et de l’égalité est décidable

Par exemple, on peut décider si un AC a


Mais on ne peut pas exprimer au premier ordre l’accessibilité (\(\ACC \rightarrow^* \ACC'\))

(la nilpotence est indécidable même en dimension 1)