Automate cheminant

Les arbres considérés ici sont supposés binaires et étiquetés avec des symboles d'un alphabet fixé Σ.

Un automate cheminant A est un automate fini qui parcourt un arbre de manière séquentielle. Il commence à la racine et finit à la racine. À un instant donné, l'automate A « visite » un nœud v et se trouve dans un certain état. En fonction de l’état, de l’étiquette du nœud v et du type du nœud (est-il la racine, un enfant gauche ou droit ou est-il une feuille ?), l'automate A change d'état et de déplace vers le parent de v ou vers un de ses enfants. L'automate accepte un arbre donné s'il termine dans un état final à la racine. Comme pour les automates de mots, un automate cheminant peut être déterministe ou non.

Un automate cheminant (non déterministe) A = (Q, Σ, I, F, R, δ) est composé des données suivantes :

• Q est un ensemble fini d'état,
• Σ est un alphabet,
• I, F, et R sont des sous-ensembles d'états, respectivement les états initiaux, d'acceptation et de et rejet
• T est l'ensemble des « types » possibles : {nœud interne, feuille} × {racine, enfant gauche, enfant droit}
• δ ⊆ Q × T × Σ × {up, left, right } × Q est la relation de transition.

La relation de transition opère donc en fonction de l'état, du type du nœud ainsi que du symbole lu sur la nœud, décide du mouvement et change d'état.

Un configuration de l'automate est un couple formé (q,v) d'un état et d'un nœud. L'automate commence dans une configuration initiale formée d'un état initial et de la racine. Il termine, s'il accepte l'arbre, dans une configuration terminale formée d'un état terminal et de la racine.

Voici l'exemple d'un automate cheminant qui réalise l'algorithme de parcours en profondeur (DFS) sur un arbre donné. L'automate ${\displaystyle A}$ a 3 states, ${\displaystyle Q=\{q_{0},q_{\ell },q_{r}\}}$. L'automate commence à la racine dans l'état ${\displaystyle q_{0}}$ et descend vers le sous-arbre gauche. Puis il continue récursivement : quand ${\displaystyle A}$ entre dans un nœud ${\displaystyle v}$ en étant dans l'état ${\displaystyle q_{\ell }}$, cela signifie qu'il vient de traiter le sous-arbre gauche de ${\displaystyle v}$, et il procède au traitement du sous-arbre droit de ${\displaystyle v}$. Si ${\displaystyle A}$ entre dans un nœud ${\displaystyle v}$ en étant dans l'état ${\displaystyle q_{r}}$, cela signifie que tout le sous-arbre de racine ${\displaystyle v}$ a été visité, et ${\displaystyle A}$ se déplace vers le parent de ${\displaystyle v}$ en changeant son état en ${\displaystyle q_{\ell }}$ ou ${\displaystyle q_{r}}$, selon que ${\displaystyle v}$ est un enfant gauche ou droit.

Voici d'autres exemples : On peut montrer que l'ensemble des arbres dont toutes les feuilles portent le même symbole fixe a est reconnaissable par un automate cheminant. Plus généralement, l'ensemble des arbres dont la suite les feuilles porte un mot d'un langage régulier fixé est reconnaissable par un automate cheminant.

Certaines propriétés élémentaires sont faciles :

• Les langages d'arbres reconnus par les automates cheminant sont fermés par union et par intersection.
• Un langage d'arbres reconnu par automate cheminant est aussi reconnu par automate d'arbres (mais l'inclusion est stricte, voir ci-dessous).

Contrairement aux automates d'arbres, les automates cheminant sont difficiles à analyser. Voici quelques propriétés difficiles à prouver :

• Les automates cheminant déterministes sont moins puissants que les automates cheminant non déterministes[2].
• Les langages d'arbres reconnus par les automates cheminant déterministes sont fermés par complémentation (pour les automates non déterministes, le problème est ouvert[3]).
• L'ensemble des langages reconnus par automates cheminant est strictement inclus dans la famille des langages reconnus par automate d'arbres[4].
• Tester si le langage reconnu par automates cheminant est vide est EXPTIME-complet.