Structure automatique

En informatique théorique, une structure automatique[1] est une structure définie à partir d'automates finis. L'intérêt principal de ces structures est de représenter de manière finie des objets infinis, ce qui offre un cadre « naturel » à la décidabilité de problèmes.

En particulier, la vérification de modèles de formules de la logique du premier ordre est décidable sur les structures automatiques.

Introduction

Structures

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

  • A {\displaystyle A} est un ensemble (dénombrable) ;
  • R 1 … R p {\displaystyle R_{1}\dots R_{p}} sont des prédicats sur A {\displaystyle A} d'arités r 1 … r p {\displaystyle r_{1}\dots r_{p}}  ;
  • f 1 … f q {\displaystyle f_{1}\dots f_{q}} sont des fonctions (partielles) sur A {\displaystyle A} d'arités r 1 ′ … r q ′ {\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.

Structures récursives

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 A {\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.

Définition formelle

Structures automatiques

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

  • L δ {\displaystyle L_{\delta }} , le domaine de ν {\displaystyle \nu } , est un langage régulier de Σ ∗ {\displaystyle \Sigma ^{*}} ;
  • L ε := { ( w , w ′ )   |   ν ( w ) = ν ( w ′ ) } {\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 R i {\displaystyle R_{i}} d'arité r i {\displaystyle r_{i}} , le langage L i := { ( w 1 … w r i )   |   R 1 ( ν ( w 1 ) … ν ( w r i ) ) } {\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.

Représentations automatiques

Toute structure automatique U = ⟨ A , R 1 … R p ⟩ {\displaystyle {\mathcal {U}}=\langle A,R_{1}\dots R_{p}\rangle } possède une représentation automatique sous la forme ⟨ ν , M δ , T ε , T 1 … T p ⟩ {\displaystyle \langle \nu ,M_{\delta },T_{\varepsilon },T_{1}\dots T_{p}\rangle } où :

  • M δ {\displaystyle M_{\delta }} est un automate fini sur Σ {\displaystyle \Sigma } qui reconnaît L δ {\displaystyle L_{\delta }}  ;
  • T ε {\displaystyle T_{\varepsilon }} est un transducteur synchrone qui reconnaît L ε {\displaystyle L_{\varepsilon }}  ;
  • Chaque T i {\displaystyle T_{i}} est un transducteur synchrone qui reconnaît L i {\displaystyle L_{i}} .

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

Exemples

  1. Les structures finies sont automatiques.
  2. L'ensemble des entiers naturels muni de l'addition ⟨ N , + ⟩ {\displaystyle \langle \mathbb {N} ,+\rangle } est automatique. On code les entiers en base 2 avec le bit de poids fort à droite et l'addition est représentée avec un transducteur synchrone.
  3. On peut étendre la structure précédente avec une relation de divisibilité restreinte : x | p y {\displaystyle x|_{p}y} si x {\displaystyle x} est une puissance de p {\displaystyle p} qui divise y {\displaystyle y} . Pour tout p ≥ 2 {\displaystyle p\geq 2} , la structure N p = ⟨ N , + , | p ⟩ {\displaystyle {\mathfrak {N}}_{p}=\langle \mathbb {N} ,+,|_{p}\rangle } est automatique.
  4. Les groupes automatiques sont des cas particuliers de structures automatiques qui sont des groupes.

Représentation automatique de N p = ⟨ N , + , | p ⟩ {\displaystyle {\mathfrak {N}}_{p}=\langle \mathbb {N} ,+,|_{p}\rangle }

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

Le langage L δ {\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.

Décidabilité de la vérification de modèles

Étant donné une représentation d'une structure automatique, la vérification de modèles d'une formule logique du premier ordre sur le langage des prédicats de la structure est décidable.

En particulier, étant donné une formule φ ( x ¯ ) {\displaystyle \varphi ({\overline {x}})} de variables libres x ¯ = ( x 1 … x n ) {\displaystyle {\overline {x}}=(x_{1}\dots x_{n})} sur ce langage, il est possible de construire un transducteur synchrone reconnaissant l'ensemble des codages d'éléments vérifiant la formule : { ( w 1 … w n   |   U , [ x 1 ↦ ν ( w 1 ) … x n ↦ ν ( w n ) ] ⊨ φ ( x ¯ ) } {\displaystyle \{(w_{1}\dots w_{n}~|~{\mathcal {U}},[x_{1}\mapsto \nu (w_{1})\dots x_{n}\mapsto \nu (w_{n})]\models \varphi ({\overline {x}})\}} .

Il est possible d'étendre la logique du premier ordre avec un quantificateur ∃ ω {\displaystyle \exists ^{\omega }} dont la sémantique est définie comme « il existe une infinité ». Grâce au lemme de l'étoile, on peut montrer que la vérification de modèles de cette logique étendue reste décidable sur les structures automatiques.

Propriétés remarquables

Injectivité de la représentation

À 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 L ε = { ( w , w )   |   w ∈ L δ } {\displaystyle L_{\varepsilon }=\{(w,w)~|~w\in L_{\delta }\}} .

Clôture

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.

Extensions

Par définition, les structures automatiques sont finies ou dénombrables. Il est possible d'étendre la définition à des ensembles ayant la puissance du continu via un encodage par des mots infinis, on parle alors de structure ω {\displaystyle \omega } -automatique.

Notes et références

  1. ↑ Achim Blumensath et Erich Grädel, « Automatic Structures », Proceedings of the 15th Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society, lICS '00,‎ , p. 51– (ISBN 0769507255, lire en ligne, consulté le ).
  2. ↑ a et b (en) T. Hirst and D. Harel., « More about recursive structures: Descriptive complexity and zero-one laws », Proc. 11th IEEE Symp. on Logic in Computer Science,‎ , p. 334-348 (lire en ligne).
  • icône décorative Portail de l'informatique théorique