Automate à jetons
En informatique théorique, et notamment en théorie des automates, un automate à jetons (en anglais Modèle:Citation étrangère) 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 » (Modèle:Citation étrangère) parce que « dans un arbre binaire, quand tous les nœuds ont la même étiquette, tous les nœuds se ressemblent » (Modèle:Citation étrangère)[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 (resp. ). On pose
- et .
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 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 : . 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 et .
Plusieurs problèmes sont ouverts[2] :
- on ne sait pas s'il est possible de déterminiser un automate à jetons, donc si ;
- 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 Modèle:Citation étrangère), 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 l'ensemble des propriétés des arbres décrites par la logique du premier ordre avec fermeture transitive, et les mêmes propriétés pour la fermeture transitive positive. On peut montrer que et que , 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
Bibliographie
- Modèle:Article
- Modèle:Chapitre
- Modèle:Chapitre,
- Modèle:Article
- Modèle:Chapitre
- Modèle:Article.
- Modèle:Chapitre
- Modèle:Lien web.
Articles liés
- ↑ Modèle:Harvsp.
- ↑ 2,0 2,1 et 2,2 Modèle:Harvsp.
- ↑ Modèle:Harvsp cité par Modèle:Harvsp.
- ↑ Modèle:Harvsp.
- ↑ Ce résultat est démontré dans l'article de Modèle:Harvsp.