Automate d'arbres

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

En informatique théorique, plus précisément en théorie des langages, un automate d'arbre est une machine à états qui prend en entrée un arbre, plutôt qu'une chaîne de caractères pour les automates plus conventionnels, comme les automates finis.

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]

Alphabet gradué[modifier | modifier le code]

Un alphabet gradué (ranked alphabet en anglais) est un alphabet muni d'une fonction qui, à chaque symbole de , associe un entier naturel qui est son arité (le nombre d'arguments qu'elle requiert).

On considère les constantes comme des opérateurs nullaires (i.e. d'arité 0). Parfois, l'ensemble des symboles d'arité 0 est partagé en deux sous-ensembles, les constantes et les variables.

Un alphabet gradué est donc une signature (ensemble de symboles de constante, de fonction et de relation), considérée comme indépendante de l'algèbre sur laquelle elle agit éventuellement.

Terme, arbre[modifier | modifier le code]

  • Étant donné un alphabet gradué , les termes (de base) ou arbres sur sont définis comme suit :
  1. Un symbole de d'arité 0 est un terme ;
  2. Si est un symbole d'arité , et si sont des termes, alors la suite est un terme ; ce terme est généralement noté  ;
  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 comme un arbre. La racine de l'arbre a pour étiquette le symbole , et les enfants de la racine sont les termes .

  • Un terme clos est un terme sans variable.
  • Un terme linéaire est un terme où chaque variable apparaît au plus une fois.
  • Un contexte est un terme linéaire.
  • On définit la hauteur d'un terme par :

Automate d'arbres ascendant[modifier | modifier le code]

Un automate d'arbres fini ascendant (bottom-up finite tree automaton en anglais) sur est défini par les objets :

Ici est un ensemble fini d'états, est un alphabet gradué, 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. est constitué d'éléments de la forme , où sont des états de , et est un symbole d'arité . Par conséquent l'état d'un nœud est déduit des états de ses fils.

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.

Exemple[modifier | modifier le code]

Un automate d'arbres ascendant reconnaissant les expressions booléennes valant vrai sur l'alphabet est avec:

Automate d'arbres descendant[modifier | modifier le code]

Un automate d'arbres fini descendant sur est défini par :

est un ensemble fini d'états, est un alphabet gradué, est l'ensemble des états initiaux, et l'ensemble des règles de transition, constitué d'éléments de la forme , où sont des états de , et est un symbole d'arité .

Il y a deux différences avec les automates d'arbres ascendants : d'abord, , l'ensemble de ses états initiaux, remplace  ; 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.

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

Déterminisme[modifier | modifier le code]

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é. De plus, pour un arbre descendant , on a .

Pour les automates d'arbres non déterministes, on peut remarquer qu'il suffit d'inverser les règles de transition pour transformer un automate ascendant en un automate descendant et inversement; les états finaux deviennent les états initiaux. Ainsi, les automates d'arbres descendants non déterministes sont équipotents à leurs homologues ascendants.

Dans le cas déterministe, les arbres ascendants sont strictement plus puissants que les automates d'arbres descendants. En effet, pour les premiers, l'état d'un nœud est déterminé par l'étiquette de ses fils, alors que pour les seconds, les états des fils sont déterminés seulement par l'étiquette de leur père.

Reconnaissabilité[modifier | modifier le code]

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

Le langage d'arbres reconnu par un automate d'arbres est l'ensemble de tous les termes de base acceptés par . Un ensemble de termes de base est reconnaissable s'il existe un automate qui le reconnaît. Les langages d'arbres réguliers sont les langages d'arbres reconnu par les automates d'arbres non-déterministes et les automates d'arbres déterministes ascendants.

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

Un langage d'arbres finis binaires est définissable en logique monadique du second ordre (ou de manière équivalente en WMSO, pour logique monadique du second ordre faible, ou la quantification porte sur des sous-ensembles finis) si, et seulement si est reconnaissable par un automate ascendant[1],[2],[3].

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 est accessible s'il existe un terme de base tel qu'il existe une réduction de à . Un FTA est réduit si tous ses états sont accessibles.

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

Soit un ensemble reconnaissable de termes de base. Alors, il existe une constante telle que : pour chaque terme de base dans tel que , il existe un contexte , un contexte non trivial et un terme de base tels que et pour tout .

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]

Congruence sur des langages d'arbres[modifier | modifier le code]

  • 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 donné, si pour tout contexte , si et seulement si .

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

Les trois affirmations suivantes sont équivalentes :

  1. L est un langage d'arbres reconnaissable ;
  2. L est l'union de classes d'équivalence d'une congruence à index fini ;
  3. La relation est une congruence à index fini.

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

  1. (en) J. W. Thatcher et J. B. Wright, « Generalized finite automata theory with an application to a decision problem of second-order logic », Mathematical systems theory, vol. 2, no 1,‎ , p. 57–81 (ISSN 0025-5661 et 1433-0490, DOI 10.1007/BF01691346, lire en ligne, consulté le )
  2. (en) « Tree acceptors and some of their applications », Journal of Computer and System Sciences, vol. 4, no 5,‎ , p. 406–451 (ISSN 0022-0000, DOI 10.1016/S0022-0000(70)80041-1, lire en ligne, consulté le )
  3. (en) Mark Weyer, Automata Logics, and Infinite Games, Springer, Berlin, Heidelberg, coll. « Lecture Notes in Computer Science », , 392 p. (ISBN 978-3-540-36387-3, DOI 10.1007/3-540-36387-4_12, lire en ligne), p. 207–230, Theorem 12.27

Bibliographie[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.

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]