Automate cheminant

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.

• Automate à jetons, une extension des automates cheminant.

• 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.

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

• Portail de l'informatique théorique