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

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

Alphabet gradué modifier

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

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

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

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

 

 

 

 

Automate d'arbres descendant modifier

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

Déterminisme modifier

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

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

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

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

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

Congruence sur des langages d'arbres modifier

  • 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

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

  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

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

Articles connexes modifier