Structure automatique

On considère des structures de la forme ${\displaystyle \langle A,R_{1}\dots R_{p},f_{1}\dots f_{q}\rangle }$où :

• ${\displaystyle A}$ est un ensemble (dénombrable) ;
• ${\displaystyle R_{1}\dots R_{p}}$ sont des prédicats sur ${\displaystyle A}$ d'arités ${\displaystyle r_{1}\dots r_{p}}$ ;
• ${\displaystyle f_{1}\dots f_{q}}$ sont des fonctions (partielles) sur ${\displaystyle A}$ d'arités ${\displaystyle r'_{1}\dots r'_{q}}$.

Quitte à remplacer les fonctions des prédicats caractérisant leurs graphes, on peut supposer que les structures sont purement relationnelles.

Il semble naturel qu'afin de décider des propriétés logiques sur une structure, celle-ci doive posséder une représentation finie.

C'est l'idée que généralisent les structures récursives[2] : l'ensemble de leurs éléments ${\displaystyle A}$ est récursif, et les ensembles de r-uplets définis par les relations le sont également. On peut donc représenter de telles structures par une collection finie de machines de Turing.

Néanmoins les nombreux résultats d'indécidabilité[2] sur ces structures très générales montrent qu'il est nécessaire de se restreindre à certaines sous-classes, comme les structures automatiques.

Une structure relationnelle ${\displaystyle {\mathcal {U}}=\langle A,R_{1}\dots R_{p}\rangle }$est dite automatique s'il existe un alphabet fini ${\displaystyle \Sigma }$, un langage ${\displaystyle L_{\delta }}$ et une fonction de décodage surjective ${\displaystyle \nu :L_{\delta }\mapsto A}$ tels que :

• ${\displaystyle L_{\delta }}$, le domaine de ${\displaystyle \nu }$, est un langage régulier de ${\displaystyle \Sigma ^{*}}$;
• ${\displaystyle L_{\varepsilon }:=\{(w,w')~|~\nu (w)=\nu (w')\}}$(qui caractérise les défauts d'injectivité) est reconnu par un transducteur synchrone (sans ${\displaystyle \varepsilon }$-règles) ;
• Pour tout prédicat ${\displaystyle R_{i}}$ d'arité ${\displaystyle r_{i}}$, le langage ${\displaystyle L_{i}:=\{(w_{1}\dots w_{r_{i}})~|~R_{1}(\nu (w_{1})\dots \nu (w_{r_{i}}))\}}$est reconnu par un transducteur synchrone.

Toute structure automatique ${\displaystyle {\mathcal {U}}=\langle A,R_{1}\dots R_{p}\rangle }$ possède une représentation automatique sous la forme ${\displaystyle \langle \nu ,M_{\delta },T_{\varepsilon },T_{1}\dots T_{p}\rangle }$où :

• ${\displaystyle M_{\delta }}$ est un automate fini sur ${\displaystyle \Sigma }$ qui reconnaît ${\displaystyle L_{\delta }}$ ;
• ${\displaystyle T_{\varepsilon }}$ est un transducteur synchrone qui reconnaît ${\displaystyle L_{\varepsilon }}$ ;
• Chaque ${\displaystyle T_{i}}$ est un transducteur synchrone qui reconnaît ${\displaystyle L_{i}}$.

C'est à partir de cette représentation que l'on va décider certaines propriétés de la structure.

Automate qui vérifie l'addition. Il accepte un mot ${\displaystyle (x_{n}y_{n}z_{n})\dots (x_{0}y_{0}z_{0})}$ si le nombre ${\displaystyle z_{0}\dots z_{n}}$ est égal à la somme de ${\displaystyle x_{0}\dots x_{n}}$et ${\displaystyle y_{0}\dots y_{n}}$.

Le langage ${\displaystyle L_{\delta }}$ est l'ensemble des mots finis sur l'alphabet {0, 1}. La fonction de décodage associe à tout mot fini m l'entier dont la représentation binaire avec le bit de poids fort à droite est m. Par exemple, le mot 00101 se décode en 4+16 = 20. L'addition est représentée par l'automate à deux états donnée dans la figure de droite.

À partir d'une représentation automatique d'une structure, il est possible d'en construire une représentation injective.

Une telle représentation vérifie que la fonction de décodage ${\displaystyle \nu }$ est injective, ou de manière équivalente, que ${\displaystyle L_{\varepsilon }=\{(w,w)~|~w\in L_{\delta }\}}$.

La classe des structures automatiques est closes par :

• mise à une puissance finie ;
• quotient par une relation définissable au premier ordre ;
• ajout d'un prédicat définissable au premier ordre ;
• restriction à une sous-structure dont le domaine est définissable au premier ordre.