Automate d'arbres

Un article de Wikipédia, l'encyclopédie libre.

Sommaire

1 Introduction
2 Définitions
3 Propriétés
4 Liens externes

[modifier] 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.

[modifier] 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é, $Q_f \subseteq Q$ 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 dont 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, $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.

Pourquoi les FTA descendants déterministes sont-ils alors moins puissants que leurs homologues ascendants? Parce qu’un TA déterministe ne peut par définition jamais avoir deux règles de transition dont la partie gauche est identique. Pour les automates d'arbres, les règles de transition sont des règles de réécriture ; et pour ceux qui sont descendants, le côté gauche correspondra aux nœuds ancêtres. Par conséquent un automate fini déterministe descendant ne pourra tester que des propriétés qui sont vraies dans toutes les branches sans exception, car le choix de l'état à écrire dans chaque branche fille est déterminée au nœud parent, sans connaître le contenu des branches filles en question.

[modifier] Propriétés

[modifier] 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é.

[modifier] 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é.

[modifier] 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.

[modifier] 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 $H e i g h t (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$ .

[modifier] Fermeture

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

[modifier] 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 $\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$ .