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 ${\displaystyle F}$ muni d'une fonction ${\displaystyle \operatorname {ar} }$ qui, à chaque symbole ${\displaystyle f}$ de ${\displaystyle F}$, associe un entier naturel ${\displaystyle \operatorname {ar} (f)}$ 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é ${\displaystyle F}$, les termes (de base) ou arbres sur ${\displaystyle F}$ sont définis comme suit :

1. Un symbole de ${\displaystyle F}$ d'arité 0 est un terme ;
2. Si ${\displaystyle f}$ est un symbole d'arité ${\displaystyle n}$, et si ${\displaystyle t_{1},t_{2},\ldots ,t_{n}}$ sont des termes, alors la suite ${\displaystyle (f,t_{1},t_{2},\ldots ,t_{n})}$ est un terme ; ce terme est généralement noté ${\displaystyle f(t_{1},t_{2},\ldots ,t_{n})}$ ;
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 ${\displaystyle (f,t_{1},t_{2},\ldots ,t_{n})}$ comme un arbre. La racine de l'arbre a pour étiquette le symbole ${\displaystyle f}$, et les enfants de la racine sont les termes ${\displaystyle t_{1},t_{2},\ldots ,t_{n}}$.

• 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 ${\displaystyle t}$ par :

${\displaystyle h(t)=\left\{{\begin{array}{c @{=} c}0&{\text{si }}t{\text{ est d'arité }}0\\\max(h(t_{1}),...,h(t_{n}))+1&{\text{si }}t=f(t_{1},...t_{n})\\\end{array}}\right.}$

Automate d'arbres ascendant

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

${\displaystyle (Q,F,Q_{f},\Delta )}$

Ici ${\displaystyle Q}$ est un ensemble fini d'états, ${\displaystyle F}$ est un alphabet gradué, ${\displaystyle Q_{f}\subseteq Q}$ est un ensemble d'états finaux, et ${\displaystyle \Delta }$ 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. ${\displaystyle \Delta }$ est constitué d'éléments de la forme ${\displaystyle (f(q_{1},...,q_{n})\rightarrow q)}$, où ${\displaystyle q_{1},...,q_{n},q}$ sont des états de ${\displaystyle Q}$, et ${\displaystyle f\in F}$ est un symbole d'arité ${\displaystyle n}$. 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 ${\displaystyle \{et:2\ ,\ ou:2\ ,\ non:1\ ,\ vrai:0\ ,\ faux:0\}}$ est ${\displaystyle A=(Q,F,Q_{f},\Delta )}$ avec:

${\displaystyle Q=\{q_{0},\ q_{1}\}}$

${\displaystyle F=\{et,\ ou,\ non,\ faux,\ vrai\}}$

${\displaystyle Q_{f}=\{q_{1}\}}$

${\displaystyle \Delta =\left\{{\begin{array}{c c c}faux&\rightarrow &q_{0}\\vrai&\rightarrow &q_{1}\\et(q_{a},q_{b})&\rightarrow &q_{min(a,b)}\\ou(q_{a},q_{b})&\rightarrow &q_{max(a,b)}\\non(q_{a})&\rightarrow &q_{1-a}\end{array}}\right.}$

Automate d'arbres descendant

Un automate d'arbres fini descendant sur ${\displaystyle F}$ est défini par :

${\displaystyle (Q,F,I,\Delta )}$

${\displaystyle Q}$ est un ensemble fini d'états, ${\displaystyle F}$ est un alphabet gradué, ${\displaystyle I\subseteq Q}$ est l'ensemble des états initiaux, et ${\displaystyle \Delta }$ l'ensemble des règles de transition, constitué d'éléments de la forme ${\displaystyle ((q,f)\rightarrow (q_{1},...,q_{n}))}$, où ${\displaystyle q_{1},...,q_{n},q}$ sont des états de ${\displaystyle Q}$, et ${\displaystyle f\in F}$ est un symbole d'arité ${\displaystyle n}$.

Il y a deux différences avec les automates d'arbres ascendants : d'abord, ${\displaystyle I\subseteq Q}$, l'ensemble de ses états initiaux, remplace ${\displaystyle 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.

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 ${\displaystyle (Q,F,I,\Delta )}$, on a ${\displaystyle |I|=1}$.

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 ${\displaystyle n}$ fils, alors que pour les seconds, les états des ${\displaystyle n}$ fils sont déterminés seulement par l'étiquette de leur père.

Démonstration

Considérons le langage ${\displaystyle L=\{f(a,b),f(b,a)\}}$ défini sur l'alphabet ${\displaystyle F=\{f:2\ ,\ a:0\ ,\ b:0\}}$.

• ${\displaystyle L}$ est reconnaissable par l'automate ascendant ${\displaystyle A=(Q,F,Q_{f},\Delta )}$ où:

${\displaystyle Q=\{q_{a},q_{b},q_{f}\}}$, ${\displaystyle Q_{f}=\{q_{f}\}}$ et ${\displaystyle \Delta =\left\{{\begin{array}{c c c}a&\rightarrow &q_{a}\\b&\rightarrow &q_{b}\\f(q_{a},q_{b})&\rightarrow &q_{f}\\f(q_{b},q_{a})&\rightarrow &q_{f}\end{array}}\right.}$

• Supposons que ${\displaystyle L}$ est accepté par un automate descendant déterministe ${\displaystyle B=(Q,F,I,\Delta )}$.

${\displaystyle B}$ étant déterministe, on a ${\displaystyle |I|=1}$. Posons ${\displaystyle I=\{q_{0}\}}$. De plus, pour tout état ${\displaystyle q\in Q}$ et ${\displaystyle x\in F}$, ${\displaystyle \Delta }$ contient au plus une règle dont le membre gauche est ${\displaystyle (q,x)}$.

En particulier, il existe une unique règle de transition de la forme ${\displaystyle (q_{0},f)\rightarrow (q_{1},q_{2})}$. Et comme ${\displaystyle L=\{f(a,b),f(b,a)\}}$ est reconnu par l'automate ${\displaystyle B}$, on a ${\displaystyle q_{1}=q_{2}}$.

Donc l'automate ${\displaystyle B}$ reconnaîtrait les termes ${\displaystyle f(a,b)}$, ${\displaystyle f(b,a)}$ mais aussi ${\displaystyle f(a,a)}$ et ${\displaystyle f(b,b)}$ qui n'appartiennent pas au langage ${\displaystyle L}$.

${\displaystyle L}$ n'est donc pas reconnaissable par un automate descendant déterministe.

Reconnaissabilité

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

Le langage d'arbres ${\displaystyle L(A)}$ reconnu par un automate d'arbres ${\displaystyle A}$ est l'ensemble de tous les termes de base acceptés par ${\displaystyle A}$. 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 ${\displaystyle L}$ 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 ${\displaystyle q}$ est accessible s'il existe un terme de base ${\displaystyle t}$ tel qu'il existe une réduction de ${\displaystyle t}$ à ${\displaystyle q(t)}$. Un FTA est réduit si tous ses états sont accessibles.

Lemme de l'étoile

Soit ${\displaystyle L}$ un ensemble reconnaissable de termes de base. Alors, il existe une constante ${\displaystyle k>0}$ telle que : pour chaque terme de base ${\displaystyle t}$ dans ${\displaystyle L}$ tel que ${\displaystyle h(t)>k}$, il existe un contexte ${\displaystyle C\in C(F)}$, un contexte non trivial ${\displaystyle C'\in C(F)}$ et un terme de base ${\displaystyle u}$ tels que ${\displaystyle t=C[C'[u]]}$ et pour tout ${\displaystyle n\geq 0}$ ${\displaystyle C[C'^{n}[u]]\in L}$.

Fermeture

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

Démonstration

Soit ${\displaystyle L_{1}}$ et ${\displaystyle L_{2}}$ sont deux langages d'arbres, ${\displaystyle {\mathcal {A}}_{1}=(Q_{1},F,Q_{f_{1}},\Delta _{1})}$ et ${\displaystyle {\mathcal {A}}_{2}=(Q_{2},F,Q_{f_{2}},\Delta _{2})}$ des automates ascendants reconnaissant ${\displaystyle L_{1}}$ et ${\displaystyle L_{2}}$ respectivement.

On peut supposer ${\displaystyle {\mathcal {A}}_{1}}$ et ${\displaystyle {\mathcal {A}}_{2}}$ complets (quitte à leur ajouter un "état puits", c'est-à-dire un état non terminal tel que les transitions bloquant l'automate pointent sur cet état à la place).

On peut également supposer ${\displaystyle Q_{1}\cap Q_{2}=\emptyset }$.

L'automate ${\displaystyle {\mathcal {A}}=(Q_{1},F,Q_{1}\setminus Q_{f_{1}},\Delta _{1})}$ reconnaît ${\displaystyle {\overline {L_{1}}}}$.

L'automate ${\displaystyle {\mathcal {A}}=(Q_{1}\times Q_{2},F,Q_{f_{1}}\times Q_{f_{2}},\Delta )}$ reconnaît ${\displaystyle L_{1}\cap L_{2}}$, où ${\displaystyle f((q_{1},q_{1}'),...,(q_{n},q_{n}'))\rightarrow (q,q')}$ avec ${\displaystyle f(q_{1},...,q_{n})\rightarrow q}$ dans ${\displaystyle \Delta _{1}}$ et ${\displaystyle f(q_{1}',...,q_{n}')\rightarrow q'}$ dans ${\displaystyle \Delta _{2}}$.

L'automate ${\displaystyle {\mathcal {A}}=(Q_{1}\times Q_{2},F,Q_{f_{1}}\times Q_{2}\cup Q_{1}\times Q_{f_{2}},\Delta )}$ reconnaît ${\displaystyle L_{1}\cup L_{2}}$, où ${\displaystyle f((q_{1},q_{1}'),...,(q_{n},q_{n}'))\rightarrow (q,q')}$ avec ${\displaystyle f(q_{1},...,q_{n})\rightarrow q}$ dans ${\displaystyle \Delta _{1}}$ et ${\displaystyle f(q_{1}',...,q_{n}')\rightarrow q'}$ dans ${\displaystyle \Delta _{2}}$.

Théorème de Myhill-Nerode

Congruence sur des langages d'arbres

• Une congruence sur des langages d'arbres est une relation ${\displaystyle \equiv }$ telle que : ${\displaystyle 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 ${\displaystyle L}$ donné, ${\displaystyle u\equiv _{L}v}$ si pour tout contexte ${\displaystyle C\in C(F)}$, ${\displaystyle C[u]\in L}$ si et seulement si ${\displaystyle C[v]\in L}$.

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 ${\displaystyle \equiv _{L}}$ 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, n^o 1,‎ 1^er mars 1968, p. 57–81 (ISSN 0025-5661 et 1433-0490, DOI 10.1007/BF01691346, lire en ligne, consulté le 12 février 2018)
2. (en) « Tree acceptors and some of their applications », Journal of Computer and System Sciences, vol. 4, n^o 5,‎ 1^er octobre 1970, p. 406–451 (ISSN 0022-0000, DOI 10.1016/S0022-0000(70)80041-1, lire en ligne, consulté le 12 février 2018)
3. (en) Mark Weyer, Automata Logics, and Infinite Games, Springer, Berlin, Heidelberg, coll. « Lecture Notes in Computer Science », 2002, 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

• Automate cheminant
• Théorème de Courcelle, un théorème dont la preuve s'appuie sur la notion d'automate d'arbre.
• Automate d'arbres infinis

• Portail de l'informatique théorique