Automate d'arbres
752365
31862897
2008-07-24T22:39:41Z
Ptbotgourou
223685
robot Retire: [[eo:Vikipedio:Projekto matematiko/Arba aŭtomato]]
==Introduction==
Un '''automate d'arbre''' est un type de [[machine d'état|machine à états]]. Les automates d'arbres traitent des [[arbre (informatique)|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 <math>F</math> est défini par :
<math>(Q, F, Q_{f}, \Delta)</math>
Ici <math>Q</math> est un ensemble d'états unaires, <math>F</math> est un alphabet ordonné, <math>Q_f \subseteq Q</math> est un ensemble d'états finaux, et <math>\Delta</math> 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 <math>F</math> est défini par :
<math>(Q, F, I, \Delta)</math>
Il y a deux différences avec les automates d'arbres ascendants : d'abord, <math>I \subseteq Q</math>, l'ensemble de ses états initiaux, remplace <math>Q_F</math> ; 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.
==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 <math>t</math> (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 <math>t</math> 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 <math>L(A)</math> '''reconnu''' par un automate d'arbres <math>A</math> est l'ensemble de tous les termes de base acceptés par <math>A</math>. 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 <math>q</math> est '''accessible''' s'il existe un terme de base <math>t</math> tel qu'il existe une réduction de <math>t</math> à <math>q(t)</math>. Un FTA est '''réduit''' si tous ses états sont accessibles.
===[[Lemme de l'étoile]]===
Soit <math>L</math> un ensemble reconnaissable de termes de base. Alors, il existe une constante <math>k > 0</math> telle que : pour chaque terme de base <math>t</math> dans <math>L</math> tel que <math>Height(t) > k</math>, il existe un contexte <math>C \in C(F)</math>, un contexte non trivial <math>C' \in C(F)</math> et un terme de base <math>u</math> tels que <math>t = C[C'[u]]</math> et pour tout <math>n \geq 0</math> <math>C[C'^n[u]] \in L</math>.
===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 <math>\equiv_L</math> 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 :
<math>u_i \equiv v_i 1 \leq i \leq n \Rightarrow f(u_1,\ldots,u_n) \equiv f(v_1,\ldots,v_n)</math>
Elle est à index fini si son nombre de classes d'équivalence est fini.
Pour un langage d'arbres <math>L</math> donné, <math>u \equiv_L v</math> si pour tout contexte <math>C \in C(F)</math>, <math>C[u] \in L</math> ssi <math>C[v] \in L</math>.
==Liens externes==
Toutes les informations de cette page ont été prises du chapitre 1 de
[http://www.grappa.univ-lille3.fr/tata TATA]
[[Catégorie:Langage formel]]
[[Catégorie:Calculabilité]]
[[Catégorie:Algorithmique]]
[[en:Tree automaton]]