Automate cheminant

Un automate cheminant dans les arbres, appelé en abrégé automate cheminant (en anglais tree walking automaton (TWA)) est une variante des automates finis qui opère sur des arbres plutôt que sur des mots. Le concept a déjà été défini par Aho et Ullman en 1971^[1].

Le présent article traite des automates cheminant. Les automates d'arbres (ascendants ou descendants) sont une autre catégorie d'automates, et reconnaissent les langages réguliers d'arbres.

Description informelle

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.

Définition

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.

Exemple

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

Propriétés

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.

Annexes

Article lié

Automate à jetons, une extension des automates cheminant.

Bibliographie

Alfred V. Aho et Jeffrey D. Ullman, « Translations on a context free grammar », Information and Control, vol. 19, n^o 5,‎ 1971, p. 439–475 (DOI 10.1016/S0019-9958(71)90706-6, lire en ligne)
Mikołaj Bojańczyk et Thomas Colcombet, « Tree-walking automata cannot be determinized », Theoretical Computer Science, vol. 350, n^os 2-3,‎ 2006, p. 164–173 (DOI 10.1016/j.tcs.2005.10.031, lire en ligne)
Mikołaj Bojańczyk et Thomas Colcombet, « Tree-walking automata do not recognize all regular languages », SIAM Journal on Computing, vol. 38, n^o 2,‎ 2008, p. 658–701 (DOI 10.1137/050645427, lire en ligne)
Mikołaj Bojańczyk, « Tree-walking automata », dans C. Martin-Vide, F. Otto et H. Fernau (éditeurs), Language and Automata Theory and Applications, LATA 2008, Tarragona, Springer, 2008 (ISBN 9783540882817), p. 1-2.
Anca Muscholl, Mathias Samuelides et Luc Segoufin, « Complementing deterministic tree-walking automata », Information Processing Letters, vol. 99, n^o 1,‎ 2006, p. 33-39.

Lien externe

Mikołaj Bojańczyk, « Tree-walking automata ».

Portail de l'informatique théorique

[1] , Aho et Ullman 1971.

[2] Bojańczyk et Colcombet 2006

[3] Bojańczyk, p. 6.

[4] Bojańczyk et Colcombet 2008

[1]

[2]

[3]

[4]