Automate à jetons

En informatique théorique, et notamment en théorie des automates, un automate à jetons (en anglais « pebble automaton ») est un type d'automate d'arbres. Les automates à jetons constituent généralisation des automates cheminant dans les arbres ; l'automate est autorisé à employer un nombre fini de « jetons » qui sont utilisés pour marquer son passage dans un nœud. Ce modèle d'automate est plus puissant que les automates cheminant ordinaires, mais toujours encore moins puissant que les automates d'arbres. Les automates à jetons, introduits par Engelfriet et Hoogeboom, sont censés pallier un défaut d'automate cheminant, qui « se perd facilement dans un arbre » (« easily gets lost in a tree ») parce que « dans un arbre binaire, quand tous les nœuds ont la même étiquette, tous les nœuds se ressemblent » (« in a binary tree of which all internal nodes have the same label, all nodes look pretty much the same »)^[1].

Description

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.

Classes de langages

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

{\textit {DPA}}=\bigcup _{n}{\textit {DPA}}_{n}

et

{\textit {PA}}=\bigcup _{n}{\textit {PA}}_{n}

.

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

Propriétés

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 ${\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 : ${\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 ${\textit {PA}}_{n}\subsetneq {\textit {PA}}_{n+1}$ et ${\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 ${\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].

Automates et logique

Les automates à jetons possèdent un caractérisation intéressante en termes de logique. On note $FO+TC$ l'ensemble des propriétés des arbres décrites par la logique du premier ordre avec fermeture transitive, et $FO+{\text{pos}}\,TC$ les mêmes propriétés pour la fermeture transitive positive. On peut montrer que $PA\subseteq FO+TC$ et que $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].

Notes et références

↑ Engelfriet et Hoogeboom, 1999.
↑ ^{a b et c} Mikołaj Bojańczyk, Tree-walking automata.
↑ Muscholl, Samuelides et Segoufin 2006 cité par Mikołaj Bojańczyk.
↑ Brüggemann-Klein et Wood 2000.
↑ Ce résultat est démontré dans l'article de Engelfriet et Hoogeboom, 1999.

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)
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 ».

Articles liés

Portail de l'informatique théorique

[1] Engelfriet et Hoogeboom, 1999.

[B-2] {a b et c} Mikołaj Bojańczyk, Tree-walking automata.

[3] Muscholl, Samuelides et Segoufin 2006 cité par Mikołaj Bojańczyk.

[4] Brüggemann-Klein et Wood 2000.

[5] Ce résultat est démontré dans l'article de Engelfriet et Hoogeboom, 1999.

[1]

[2]

[3]

[4]

[5]