Automate à jetons

Un automate à jetons est un automate cheminant doté d'un ensemble fini supplémentaire de « jetons », identifiés avec les entiers 1, 2, ... , n. En plus de ses actions usuelles, un automate peut déposer un jeton sur le nœud qu'il est en train de visiter, enlever un jeton de ce nœud, et poser une question du type « est-ce que le i-ième jeton est présent sur le nœud courant » ? L'empilement des jetons est assujetti à des restrictions importantes concernant l'ordre dans lequel les jetons peuvent être déposés ou enlevés : le jeton de numéro i ne peut être posé que si les jetons des numéros de 1 à i-1 sont déjà dans l’arbre; symétriquement, le i-ième jeton ne peut être enlevé que si les jetons de numéro i+1 à n ne figurent pas dans l'arbre. En d'autres termes, le jeton enlevé doit être celui de plus grand numéro présent, le jeton déposé celui de plus petit numéro disponible. Sans ces restrictions, l'automate perd un certain nombre de ses propriétés qui deviennent indécidables, et les langages reconnus excèdent les langages réguliers d'arbres.

La classe de langages reconnus par des automates à n jetons déterministes (resp. non déterministes) est notée ${\displaystyle {\textit {DPA}}_{n}}$ (resp. ${\displaystyle {\textit {PA}}_{n}}$). On pose

${\displaystyle {\textit {DPA}}=\bigcup _{n}{\textit {DPA}}_{n}}$ et ${\displaystyle {\textit {PA}}=\bigcup _{n}{\textit {PA}}_{n}}$.

On note enfin TWA la classe des langages reconnus par les automates cheminant ordinaires.

• En ce qui concerne la relation entre automates cheminant et automates à jetons, on sait qu'il existe un langage reconnu par un automate déterministe à 1 jeton qui n'est pas reconnu par un automate cheminant ; ceci implique soit que ${\displaystyle {\textit {TWA}}\subsetneq {\textit {DPA}}}$ ou alors que ces deux classes sont incomparables, ce qui constitue un problème ouvert.
• Les automates à jetons sont strictement moins puissants que les automates d'arbres : ${\displaystyle {\textit {PA}}\subsetneq {\textit {REG}}}$. Il existe une variante, les automates à jetons invisibles, qui ont la même puissance d'expression que les automates d'arbres[2].
• La hiérarchie des automates à jetons est stricte : pour tout n, on a ${\displaystyle {\textit {PA}}_{n}\subsetneq {\textit {PA}}_{n+1}}$ et ${\displaystyle {\textit {DPA}}_{n}\subsetneq {\textit {DPA}}_{n+1}}$.

Plusieurs problèmes sont ouverts[2] :

• on ne sait pas s'il est possible de déterminiser un automate à jetons, donc si ${\displaystyle {\textit {DPA}}={\textit {PA}}}$ ;
• on ne sait pas non plus si les langages à jetons sont fermés par complémentation. Pour les langages reconnus par automates à jetons déterministes, la réponse est positive[3].

Il existe une extension des expressions régulières, appelées des expressions chenilles (en anglais « caterpillars »), introduite pour la description des syntaxes d'arbres par Anne Brüggemann-Klein et Derick Wood[4]. Les expressions chenilles décrivent exactement les langages reconnus par automates cheminant, et les langages reconnus par automates à jetons sont décrits par des expressions chenilles augmentées d'une opération de coupure[2].

Les automates à jetons possèdent un caractérisation intéressante en termes de logique. On note ${\displaystyle FO+TC}$ l'ensemble des propriétés des arbres décrites par la logique du premier ordre avec fermeture transitive, et ${\displaystyle FO+{\text{pos}}\,TC}$ les mêmes propriétés pour la fermeture transitive positive. On peut montrer que ${\displaystyle PA\subseteq FO+TC}$ et que ${\displaystyle PA=FO+{\text{pos}}\,TC}$, en d'autres termes, les langages reconnus par automates à jetons sont exactement ceux que l'on peut exprimer dans la logique du premier ordre avec fermeture transitive positive[5].

• 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)
• Joost Engelfriet et Hendrik Jan Hoogeboom, « Tree-Walking Pebble Automata », dans J. Karhumäki, H. Maurer, G. Păun et G. Rozenberg (éditeurs), Jewels are Forever, Springer Science, 1999 (DOI 10.1007/978-3-642-60207-8_7, lire en ligne), p. 72-83
• Anne Brüggemann-Klein et Derick Wood, « Caterpillars, context, tree automata and tree pattern matching », dans G. Rozenberg et W. Thomas (éditeurs), Developments in Language Theory 1999, World Scientific, 2000, p. 270-285,
• Anne Brüggemann-Klein et Derick Wood, « Caterpillars. A context specification technique », Markup Languages, vol. 2, n^o 1,‎ 2000, p. 81-106
• Mikołaj Bojańczyk, Mathias Samuelides, Thomas Schwentick et Luc Segoufin, « Expressive Power of Pebble Automata », dans M. Bugliesi, B. Preneel, V. Sassone, I. Wegener (éditeurs), Proceedings ICALP 2006, Venise, Springer, coll. « Lecture Notes in Computer Science, Volume 4051 », 2006 (DOI 10.1007/11786986_15, lire en ligne), p. 157-168
• Anca Muscholl, Mathias Samuelides et Luc Segoufin, « Complementing deterministic tree-walking automata », Information Processing Letters, vol. 99, n^o 1,‎ 2006, p. 33-39.
• Mathias Samuelides et Luc Segoufin, « Complexity of Pebble Tree-Walking Automata », dans E. Csuhaj-Varjú et Z. Ésik (éditeurs), Proceedings FCT 2007, Springer, coll. « Lecture Notes in Computer Science, Volume 4639 », 2007 (DOI 10.1007/978-3-540-74240-1_40, lire en ligne), p. 458-469
• Mikołaj Bojańczyk, « Tree-walking automata ».

• Automate cheminant
• Automate d'arbres
• Fermeture transitive