Automate d'arbres

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

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

Alphabet gradué

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

  • É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

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

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

Automate d'arbres descendant

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

Déterminisme

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é

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

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

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

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

Congruence sur des langages d'arbres

  • 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

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

  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

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

Articles connexes

  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.