Automate d'arbres

Un alphabet gradué (ranked alphabet en anglais) est un alphabet ${\displaystyle F}$ muni d'une fonction ${\displaystyle \operatorname {ar} }$ qui, à chaque symbole ${\displaystyle f}$ de ${\displaystyle F}$, associe un entier naturel ${\displaystyle \operatorname {ar} (f)}$ qui est son arité (le nombre d'arguments qu'elle requiert).

On considère les constantes comme des opérateurs nullaires (i.e. d'arité 0). Parfois, l'ensemble des symboles d'arité 0 est partagé en deux sous-ensembles, les constantes et les variables.

Un alphabet gradué est donc une signature (ensemble de symboles de constante, de fonction et de relation), considérée comme indépendante de l'algèbre sur laquelle elle agit éventuellement.

• Étant donné un alphabet gradué ${\displaystyle F}$, les termes (de base) ou arbres sur ${\displaystyle F}$ sont définis comme suit :

1. Un symbole de ${\displaystyle F}$ d'arité 0 est un terme ;
2. Si ${\displaystyle f}$ est un symbole d'arité ${\displaystyle n}$, et si ${\displaystyle t_{1},t_{2},\ldots ,t_{n}}$ sont des termes, alors la suite ${\displaystyle (f,t_{1},t_{2},\ldots ,t_{n})}$ est un terme ; ce terme est généralement noté ${\displaystyle f(t_{1},t_{2},\ldots ,t_{n})}$ ;
3. Tout terme s'obtient, à partir des symboles d'arité 0, par un nombre fini d'applications de la règle précédente.

On peut voir un terme ${\displaystyle (f,t_{1},t_{2},\ldots ,t_{n})}$ comme un arbre. La racine de l'arbre a pour étiquette le symbole ${\displaystyle f}$, et les enfants de la racine sont les termes ${\displaystyle t_{1},t_{2},\ldots ,t_{n}}$.

• Un terme clos est un terme sans variable.
• Un terme linéaire est un terme où chaque variable apparaît au plus une fois.
• Un contexte est un terme linéaire.
• On définit la hauteur d'un terme ${\displaystyle t}$ par :

${\displaystyle h(t)=\left\{{\begin{array}{c @{=} c}0&{\text{si }}t{\text{ est d'arité }}0\\\max(h(t_{1}),...,h(t_{n}))+1&{\text{si }}t=f(t_{1},...t_{n})\\\end{array}}\right.}$

Un automate d'arbres fini ascendant (bottom-up finite tree automaton en anglais) sur ${\displaystyle F}$ est défini par les objets :

${\displaystyle (Q,F,Q_{f},\Delta )}$

Ici ${\displaystyle Q}$ est un ensemble fini d'états, ${\displaystyle F}$ est un alphabet gradué, ${\displaystyle Q_{f}\subseteq Q}$ est un ensemble d'états finaux, et ${\displaystyle \Delta }$ est un ensemble de règles de transition, c'est-à-dire de règles de réécritures qui transforment les nœuds dont les racines des fils sont des états en nœuds dont les racines sont des états. ${\displaystyle \Delta }$ est constitué d'éléments de la forme ${\displaystyle (f(q_{1},...,q_{n})\rightarrow q)}$, où ${\displaystyle q_{1},...,q_{n},q}$ sont des états de ${\displaystyle Q}$, et ${\displaystyle f\in F}$ est un symbole d'arité ${\displaystyle n}$. Par conséquent l'état d'un nœud est déduit des états de ses fils.

Il n'y a pas d'état initial en tant que tel, mais les règles de transition pour les symboles constants peuvent être considérées comme des états initiaux. L'arbre est accepté si l'état de la racine est un état acceptant.

Un automate d'arbres ascendant reconnaissant les expressions booléennes valant vrai sur l'alphabet ${\displaystyle \{et:2\ ,\ ou:2\ ,\ non:1\ ,\ vrai:0\ ,\ faux:0\}}$ est ${\displaystyle A=(Q,F,Q_{f},\Delta )}$ avec:

${\displaystyle Q=\{q_{0},\ q_{1}\}}$

${\displaystyle F=\{et,\ ou,\ non,\ faux,\ vrai\}}$

${\displaystyle Q_{f}=\{q_{1}\}}$

${\displaystyle \Delta =\left\{{\begin{array}{c c c}faux&\rightarrow &q_{0}\\vrai&\rightarrow &q_{1}\\et(q_{a},q_{b})&\rightarrow &q_{min(a,b)}\\ou(q_{a},q_{b})&\rightarrow &q_{max(a,b)}\\non(q_{a})&\rightarrow &q_{1-a}\end{array}}\right.}$

Un automate d'arbres fini descendant sur ${\displaystyle F}$ est défini par :

${\displaystyle (Q,F,I,\Delta )}$

${\displaystyle Q}$ est un ensemble fini d'états, ${\displaystyle F}$ est un alphabet gradué, ${\displaystyle I\subseteq Q}$ est l'ensemble des états initiaux, et ${\displaystyle \Delta }$ l'ensemble des règles de transition, constitué d'éléments de la forme ${\displaystyle ((q,f)\rightarrow (q_{1},...,q_{n}))}$, où ${\displaystyle q_{1},...,q_{n},q}$ sont des états de ${\displaystyle Q}$, et ${\displaystyle f\in F}$ est un symbole d'arité ${\displaystyle n}$.

Il y a deux différences avec les automates d'arbres ascendants : d'abord, ${\displaystyle I\subseteq Q}$, l'ensemble de ses états initiaux, remplace ${\displaystyle Q_{F}}$ ; ensuite, ses règles de transition sont l'inverse, c'est-à-dire des règles de réécriture qui transforment les nœuds dont les racines sont des états en nœuds dont les racines des fils sont des états. L'arbre est accepté si toutes les branches sont complètement traversées jusqu'au bout.

Un automate d'arbres est déterministe s'il ne possède aucune paire de règles de transition ayant le même côté gauche. Cette définition correspond à l'idée intuitive que pour qu'un automate soit déterministe, une transition et une seule doit être possible pour un nœud donné. De plus, pour un arbre descendant ${\displaystyle (Q,F,I,\Delta )}$, on a ${\displaystyle |I|=1}$.

Pour les automates d'arbres non déterministes, on peut remarquer qu'il suffit d'inverser les règles de transition pour transformer un automate ascendant en un automate descendant et inversement; les états finaux deviennent les états initiaux. Ainsi, les automates d'arbres descendants non déterministes sont équipotents à leurs homologues ascendants.

Dans le cas déterministe, les arbres ascendants sont strictement plus puissants que les automates d'arbres descendants. En effet, pour les premiers, l'état d'un nœud est déterminé par l'étiquette de ses ${\displaystyle n}$ fils, alors que pour les seconds, les états des ${\displaystyle n}$ fils sont déterminés seulement par l'étiquette de leur père.

Pour un automate ascendant, un terme de base ${\displaystyle t}$ (c'est-à-dire un arbre) est accepté s'il existe une réduction qui part de ${\displaystyle t}$ et aboutit à ${\displaystyle q(t)}$, où ${\displaystyle q}$ est un état final. Pour un automate descendant, un terme de base ${\displaystyle t}$ est accepté s'il existe une réduction qui part de ${\displaystyle q(t)}$ et aboutit à ${\displaystyle t}$, où ${\displaystyle q(t)}$ est un état initial.

Le langage d'arbres ${\displaystyle L(A)}$ reconnu par un automate d'arbres ${\displaystyle A}$ est l'ensemble de tous les termes de base acceptés par ${\displaystyle A}$. Un ensemble de termes de base est reconnaissable s'il existe un automate qui le reconnaît. Les langages d'arbres réguliers sont les langages d'arbres reconnu par les automates d'arbres non-déterministes et les automates d'arbres déterministes ascendants.

Une propriété importante est que les homomorphismes linéaires (c'est-à-dire qui préservent l'arité) préservent la reconnaissabilité.

Un langage d'arbres finis binaires est définissable en logique monadique du second ordre (ou de manière équivalente en WMSO, pour logique monadique du second ordre faible, ou la quantification porte sur des sous-ensembles finis) si, et seulement si ${\displaystyle L}$ est reconnaissable par un automate ascendant[1] - [2] - [3].

Un automate d'arbres fini non déterministe est complet s'il y a au moins une règle de transition disponible pour chaque combinaison possible symbole-état. Un état ${\displaystyle q}$ est accessible s'il existe un terme de base ${\displaystyle t}$ tel qu'il existe une réduction de ${\displaystyle t}$ à ${\displaystyle q(t)}$. Un FTA est réduit si tous ses états sont accessibles.

Soit ${\displaystyle L}$ un ensemble reconnaissable de termes de base. Alors, il existe une constante ${\displaystyle k>0}$ telle que : pour chaque terme de base ${\displaystyle t}$ dans ${\displaystyle L}$ tel que ${\displaystyle h(t)>k}$, il existe un contexte ${\displaystyle C\in C(F)}$, un contexte non trivial ${\displaystyle C'\in C(F)}$ et un terme de base ${\displaystyle u}$ tels que ${\displaystyle t=C[C'[u]]}$ et pour tout ${\displaystyle n\geq 0}$ ${\displaystyle C[C'^{n}[u]]\in L}$.

La classe des langages d'arbres reconnaissables est fermée pour l'union, la complémentation et l'intersection :

• Une congruence sur des langages d'arbres est une relation ${\displaystyle \equiv }$ telle que : ${\displaystyle u_{i}\equiv v_{i}1\leq i\leq n\Rightarrow f(u_{1},\ldots ,u_{n})\equiv f(v_{1},\ldots ,v_{n})}$ ;
• Elle est à index fini si son nombre de classes d'équivalence est fini ;
• Pour un langage d'arbres ${\displaystyle L}$ donné, ${\displaystyle u\equiv _{L}v}$ si pour tout contexte ${\displaystyle C\in C(F)}$, ${\displaystyle C[u]\in L}$ si et seulement si ${\displaystyle C[v]\in L}$.

Les trois affirmations suivantes sont équivalentes :

1. L est un langage d'arbres reconnaissable ;
2. L est l'union de classes d'équivalence d'une congruence à index fini ;
3. La relation ${\displaystyle \equiv _{L}}$ est une congruence à index fini.

• Automate cheminant
• Théorème de Courcelle, un théorème dont la preuve s'appuie sur la notion d'automate d'arbre.
• Automate d'arbres infinis