Automate d'arbres

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un automate d'arbre est un type de machine à états. Les automates d'arbres traitent des arbres, plutôt que les chaînes de caractères des automates plus conventionnels.

Introduction[modifier | modifier le code]

Comme pour les automates classiques, les automates d'arbres finis (FTA pour finite tree automata en anglais) peuvent être déterministes ou pas. Suivant la façon dont les automates se "déplacent" sur l'arbre qu'ils traitent, les automates d'arbres peuvent être de deux types (a) ascendants (b) descendants. La distinction est importante, car si les automates non-déterministes (ND) ascendants et descendants sont équivalents, les automates déterministes descendants sont strictement moins puissants que leurs homologues déterministes ascendants. En effet, les propriétés d'arbres spécifiées par les automates déterministes descendants ne peuvent dépendre que des propriétés de chemins.

Définitions[modifier | modifier le code]

Un alphabet gradué (ranked alphabet en anglais) est un alphabet F muni d'une fonction \operatorname{ar} qui, à chaque symbole f de F, associe un entier naturel \operatorname{ar}(f) qui est son arité. Un alphabet gradué est donc une signature, considérée comme indépendante de l'algèbre sur laquelle elle agit éventuellement. Un symbole d'arité 0 est aussi appelé un constante[1].

Étant donné un alphabet gradué F, les termes ou arbres sur F sont définis comme suit :

  1. Un symbole de F d'arité 0 est un terme.
  2. Si f est un symbole d'arité n, est si t_1, t_2,\ldots,t_n sont des termes, alors la suite (f, t_1, t_2,\ldots,t_n) est un terme ; ce terme est généralement noté f(t_1, t_2,\ldots,t_n).
  3. Tout terme s'obtient, à partir des symboles d'arité 0, par un nombre fini d'applications de la règle précédente.

On peut voir un terme (f, t_1, t_2,\ldots,t_n) comme un arbre. La racine de l'arbre a pour étiquette le symbole f, et les enfants de la racine sont les termes t_1, t_2,\ldots,t_n.

Un automate d'arbre fini ascendant sur F est défini par les objets :

(Q, F, Q_{f}, \Delta)

Ici Q est un ensemble fini d'états, F est un alphabet gradué, Q_f \subseteq Q est un ensemble d'états finaux, et \Delta est un ensemble de règles de transition, c'est-à-dire de règles de réécritures qui transforment les nœuds dont les racines des fils sont des états en nœuds dont les racines sont des états. Par conséquent l'état d'un nœud est déduit des états de ses enfants.

Il n'y a pas d'état initial en tant que tel, mais les règles de transition pour les symboles constants peuvent être considérées comme des états initiaux. L'arbre est accepté si l'état de la racine est un état acceptant.

Un automate d'arbre fini descendant sur F est défini par : (Q, F, I, \Delta)

Il y a deux différences avec les automates d'arbres ascendants : d'abord, I \subseteq Q, l'ensemble de ses états initiaux, remplace Q_F ; ensuite, ses règles de transition sont l'inverse, c'est-à-dire des règles de réécriture qui transforment les nœuds dont les racines sont des états en nœuds dont les racines des fils sont des états. L'arbre est accepté si toutes les branches sont complètement traversées jusqu'au bout.

On peut facilement deviner intuitivement que les automates d'arbres descendants non déterministes sont équivalents à leurs homologues ascendants ; les règles de transition sont simplement inversées, et les états finaux deviennent les états initiaux.

Propriétés[modifier | modifier le code]

Déterminisme[modifier | modifier le code]

Comme il est écrit plus haut, un automate d'arbres est déterministe s'il ne possède aucune paire de règles de transition ayant le même côté gauche. Cette définition correspond à l'idée intuitive que pour qu'un automate soit déterministe, une transition et une seule doit être possible pour un nœud donné.

Reconnaissabilité[modifier | modifier le code]

Pour un automate ascendant, un terme de base t (c'est-à-dire un arbre) est accepté s'il existe une réduction qui part de t et aboutit à q(t), où q est un état final. Pour un automate descendant, un terme de base t est accepté s'il existe une réduction qui part de q(t) et aboutit à t, où q(t) est un état initial.

Le langage d'arbres L(A) reconnu par un automate d'arbres A est l'ensemble de tous les termes de base acceptés par A. Un ensemble de termes de base est reconnaissable s'il existe un automate qui le reconnaît.

Une propriété importante est que les homomorphismes linéaires (c'est-à-dire, qui préservent l'arité) préservent la reconnaissabilité.

Complétude et réduction[modifier | modifier le code]

Un automate d'arbres fini non déterministe est complet s'il y a au moins une règle de transition disponible pour chaque combinaison possible symbole-état. Un état q est accessible s'il existe un terme de base t tel qu'il existe une réduction de t à q(t). Un FTA est réduit si tous ses états sont accessibles.

Lemme de l'étoile[modifier | modifier le code]

Soit L un ensemble reconnaissable de termes de base. Alors, il existe une constante k > 0 telle que : pour chaque terme de base t dans L tel que Height(t) > k, il existe un contexte C \in C(F), un contexte non trivial C' \in C(F) et un terme de base u tels que t = C[C'[u]] et pour tout n \geq 0 C[C'^n[u]] \in L.

Fermeture[modifier | modifier le code]

La classe des langages d'arbres reconnaissables est fermée pour l'union, la complémentation et l'intersection.

Théorème de Myhill-Nerode[modifier | modifier le code]

Les trois affirmations suivantes sont équivalentes :

  • (i) L est un langage d'arbres reconnaissable.
  • (ii) L est l'union de classes d'équivalence d'une congruence à index fini.
  • (iii) la relation \equiv_L est une congruence à index fini.

Définitions nécessaires pour ce théorème :

  • une congruence sur des langages d'arbres est une relation telle que : u_i \equiv v_i 1 \leq i \leq n \Rightarrow f(u_1,\ldots,u_n) \equiv f(v_1,\ldots,v_n).
  • Elle est à index fini si son nombre de classes d'équivalence est fini.
  • Pour un langage d'arbres L donné, u \equiv_L v si pour tout contexte C \in C(F), C[u] \in L ssi C[v] \in L.

Notes et références[modifier | modifier le code]

  1. Parfois, l'ensemble des symboles d'arité 0 est partagé en deux sous-ensembles, les constantes et les variables.

Lien externe[modifier | modifier le code]

(en) H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison et M. Tommasi, Tree Automata Techniques and Applications, chapitre 1, 2007 lire en ligne.