Loading AI tools
De Wikipédia, l'encyclopédie libre
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].
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 (resp. ). On pose
On note enfin TWA la classe des langages reconnus par les automates cheminant ordinaires.
Plusieurs problèmes sont ouverts[2] :
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 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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.