Automate à jetons
De Wikipedia, l'encyclopédie encyclopedia
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].