Automate d'arbres

Introduction

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.

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, car 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

Un automate d'arbre fini ascendant sur F est défini par : (Q,F,Q_f,Δ)

Ici Q est un ensemble d'états unaires, F est un alphabet ordonné, est un ensemble d'états finaux, et Δ 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,Δ)

Il y a deux différences avec les automates d'arbres ascendants : d'abord, , 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

Déterminisme

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é

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

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

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 , un contexte non trivial et un terme de base u tels que t = C[C'[u]] et pour tout .

Fermeture

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

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 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 : .
• Elle est à index fini si son nombre de classes d'équivalence est fini.
• Pour un langage d'arbres L donné, si pour tout contexte , ssi .

Lien externe

(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.

• Portail de l'informatique théorique