Autómata de árbol

Un autómata de árbol es un tipo de máquina de estados . Los autómatas de árbol trabajan con estructuras de árbol , en lugar de las secuencias de las máquinas de estados más convencionales.

El siguiente artículo trata sobre autómatas de árboles ramificados, que corresponden a lenguajes regulares de árboles .

Al igual que los autómatas clásicos, los autómatas de árbol finito (ATF) pueden ser deterministas o no. Según cómo procesen el árbol de entrada, pueden ser de dos tipos: (a) de abajo hacia arriba y (b) de arriba hacia abajo. Este es un aspecto importante, ya que, si bien los autómatas de árbol no deterministas (ND) de arriba hacia abajo y los ND de abajo hacia arriba tienen un poder expresivo equivalente, los autómatas deterministas de arriba hacia abajo son estrictamente menos potentes que sus contrapartes deterministas de abajo hacia arriba, porque las propiedades del árbol especificadas por los autómatas deterministas de arriba hacia abajo solo dependen de las propiedades de la ruta. (Los autómatas de árbol deterministas de abajo hacia arriba tienen el mismo poder que los autómatas de árbol ND).

Definiciones

Un autómata de árbol finito ascendente sobre F se define como una tupla ( Q , F , Q _f , Δ ), donde Q es un conjunto de estados, F es un alfabeto jerarquizado (es decir, un alfabeto cuyos símbolos tienen una aridad asociada ), $Q f \subseteq Q$ es un conjunto de estados finales, y Δ es un conjunto de reglas de transición de la forma f ( q ₁ ( x ₁ ),..., q _n ( x _n )) → q ( f ( x ₁ ,..., x _n )), para un $f$ $\in$ $F$ n -ario $,$ $q$ $,$ $q$ $i$ $\in$ $Q$ , y x _i variables que denotan subárboles. Es decir, los miembros de Δ son reglas de reescritura de nodos cuyas raíces de hijos son estados, a nodos cuyas raíces son estados. Por lo tanto, el estado de un nodo se deduce de los estados de sus hijos.

Para n = 0, es decir, para un símbolo constante f , la definición de la regla de transición anterior se lee f () → q ( f ()); a menudo se omiten los paréntesis vacíos por conveniencia: f → q ( f ). Dado que estas reglas de transición para símbolos constantes (hojas) no requieren un estado, no se necesitan estados iniciales definidos explícitamente. Se ejecuta un autómata de árbol ascendente sobre un término base sobre F , comenzando en todas sus hojas simultáneamente y moviéndose hacia arriba, asociando un estado de ejecución de Q con cada subtérmino. El término es aceptado si su raíz está asociada a un estado de aceptación de $Q f$ . ^{[ 1 ]}

Un autómata de árbol finito descendente sobre F se define como una tupla ( Q , F , Q _i , Δ), con dos diferencias respecto a los autómatas de árbol ascendentes. Primero, $Q i \subseteq Q$ , el conjunto de sus estados iniciales, reemplaza $a Q f$ ; segundo, sus reglas de transición están orientadas inversamente: q ( f ( x ₁ ,..., x _n )) → f ( q ₁ ( x ₁ ),..., q _n ( x _n )), para un n -ario $f \in F, q, q i \in Q$ , y x _i variables que denotan subárboles. Es decir, los miembros de Δ son aquí reglas de reescritura de nodos cuyas raíces son estados a nodos cuyas raíces de hijos son estados. Un autómata descendente comienza en algunos de sus estados iniciales en la raíz y se mueve hacia abajo a lo largo de las ramas del árbol, asociando a lo largo de una ejecución un estado con cada subtérmino inductivamente. Se acepta un árbol si se puede recorrer cada rama de esta manera. ^{[ 2 ]}

Un autómata de árbol se denomina determinista (abreviado DFTA ) si no hay dos reglas de Δ que tengan el mismo lado izquierdo; de lo contrario, se denomina no determinista ( NFTA ). ^{[ 3 ]} Los autómatas de árbol no deterministas descendentes tienen el mismo poder expresivo que los no deterministas ascendentes; ^{[ 4 ]} las reglas de transición simplemente se invierten y los estados finales se convierten en los estados iniciales.

En contraste, los autómatas de árbol deterministas descendentes ^{[ 5 ]} son menos potentes que sus contrapartes ascendentes, porque en un autómata de árbol determinista no hay dos reglas de transición con el mismo lado izquierdo. Para los autómatas de árbol, las reglas de transición son reglas de reescritura; y para los descendentes, el lado izquierdo serán los nodos padre. En consecuencia, un autómata de árbol determinista descendente solo podrá probar propiedades de árbol que sean verdaderas en todas las ramas, porque la elección del estado a escribir en cada rama hija se determina en el nodo padre, sin conocer el contenido de las ramas hijas. Por ejemplo, si F consta de f , g y a , que son 2arios, 1arios y 0arios, respectivamente, el conjunto de todos los términos que tienen una instancia base de f ( a , g ( x )) como subtérmino, puede ser reconocido por un DFTA ascendente, pero no por un DFTA de arriba a abajo. ^{[ a ]}^{[ 6 ]}

Los autómatas de árbol infinito extienden los autómatas descendentes a árboles infinitos y pueden usarse para demostrar la decidibilidad de S2S , la teoría monádica de segundo orden con dos sucesores. Los autómatas de árbol finito (no deterministas si son descendentes) son suficientes para WS2S. ^{[ 7 ]}

Ejemplos

Autómata ascendente que acepta listas booleanas

Empleando colores para distinguir los miembros de F y Q , y usando el alfabeto clasificado F = { false , true , nil , cons (.,.) }, donde cons tiene aridad 2 y todos los demás símbolos tienen aridad 0, se puede definir un autómata de árbol ascendente que acepta el conjunto de todas las listas finitas de valores booleanos como ( Q , F , Q _f , Δ) con $Q$ $= {$ $Bool$ $,$ $BList$ $},$ $Q$ $f$ $= {$ $BList$ $},$ y Δ que consta de las reglas

En este ejemplo, las reglas se pueden entender intuitivamente como la asignación de un tipo a cada término de forma ascendente; por ejemplo, la regla (4) se puede leer como "Un término cons ( x ₁ , x ₂ ) tiene el tipo BList , siempre que x ₁ y x ₂ tengan el tipo Bool y BList , respectivamente". Un ejemplo de ejecución aceptable es

Cf. la derivación del mismo término a partir de una gramática de árbol regular correspondiente al autómata, que se muestra en Gramática de árbol regular#Ejemplos .

Un ejemplo de ejecución rechazada es

Intuitivamente, esto corresponde a que el término cons ( falso , verdadero ) no esté bien tipificado.

Autómata descendente que acepta múltiplos de 3 en notación binaria.

Utilizando la misma coloración que la anterior, este ejemplo muestra cómo los autómatas de árbol generalizan los autómatas de cadena ordinarios. El autómata de cadena determinista finito que se muestra en la imagen acepta todas las cadenas de dígitos binarios que denotan un múltiplo de 3. Utilizando las nociones de Autómata finito determinista#Definición formal , se define de la siguiente manera:

el conjunto Q de estados es { S ₀ , S ₁ , S ₂ },
el alfabeto de entrada es { 0 , 1 },
siendo el estado inicial S ₀ ,
el conjunto de estados finales es { S ₀ }, y
Las transiciones son las que se muestran en la columna (B) de la tabla.

En la configuración del autómata de árbol, el alfabeto de entrada se modifica de tal manera que los símbolos 0 y 1 son unarios, y se utiliza un símbolo nulo, por ejemplo, nil , para las hojas del árbol. Por ejemplo, la cadena binaria " 110 " en la configuración del autómata de cadena corresponde al término " 1 ( 1 ( 0 ( nil )))" en la configuración del autómata de árbol; de esta forma, las cadenas se pueden generalizar a árboles o términos. El autómata de árbol finito descendente que acepta el conjunto de todos los términos correspondientes a múltiplos de 3 en notación de cadena binaria se define entonces de la siguiente manera:

el conjunto Q de estados sigue siendo { S ₀ , S ₁ , S ₂ },
el alfabeto de entrada clasificado es { 0 , 1 , nil }, con Arity ( 0 )= Arity ( 1 )=1 y Arity ( nil )=0, como se explicó,
el conjunto de estados iniciales es { S ₀ }, y
Las transiciones son las que se muestran en la columna (C) de la tabla.

Por ejemplo, el árbol " 1 ( 1 ( 0 ( nil )))" es aceptado por la siguiente ejecución del autómata de árboles:

Por el contrario, el término " 1 ( 0 ( nil ))" conduce a la siguiente ejecución de autómata no aceptante:

Dado que no hay otros estados iniciales que S ₀ para comenzar una ejecución del autómata, el término " 1 ( 0 ( nil ))" no es aceptado por el autómata de árbol.

Para fines comparativos, la tabla muestra en las columnas (A) y (D) una gramática regular (de cadena) (derecha) y una gramática regular de árbol , respectivamente, cada una aceptando el mismo lenguaje que su contraparte de autómata.

Propiedades

Reconocibilidad

Para un autómata ascendente, se acepta un término base t (es decir, un árbol) si existe una reducción que comienza en t y termina en q ( t ), donde q es un estado final. Para un autómata descendente, se acepta un término base t si existe una reducción que comienza en q ( t ) y termina en t , donde q es un estado inicial.

El lenguaje de árbol L ( A ) aceptado o reconocido por un autómata de árbol A es el conjunto de todos los términos básicos aceptados por A. Un conjunto de términos básicos es reconocible si existe un autómata de árbol que lo acepta.

Un homomorfismo de árbol lineal (es decir, que preserva la aridad) preserva la reconocibilidad. ^{[ 8 ]}

Completitud y reducción

Un autómata de árbol finito no determinista es completo si existe al menos una regla de transición disponible para cada posible combinación de símbolos y estados. Un estado q es accesible si existe un término fundamental t tal que existe una reducción de t a q ( t ). Un NFTA es reducido si todos sus estados son accesibles. ^{[ 9 ]}

Lema de bombeo

Todo término fundamental t suficientemente grande ^{[ 10 ]} en un lenguaje de árbol reconocible L puede ser tripartito verticalmente ^[¹¹^] de tal manera que la repetición arbitraria ("bombeo") de la parte central mantiene el término resultante en L . ^[¹²^]^[¹³^]

Para el lenguaje de todas las listas finitas de valores booleanos del ejemplo anterior, todos los términos más allá del límite de altura k = 2 pueden ser bombeados, ya que necesitan contener una ocurrencia de cons . Por ejemplo,

Todos pertenecen a ese idioma.

Cierre

La clase de lenguajes de árbol reconocibles es cerrada bajo unión, bajo complementación y bajo intersección. ^{[ 14 ]}

Teorema de Myhill-Nerode

Una congruencia en el conjunto de todos los árboles sobre un alfabeto jerarquizado F es una relación de equivalencia tal que $u 1 \equiv v 1$ y ... y $u n \equiv v n$ implica $f (u 1,..., u n) \equiv f (v 1,..., v n)$ , para todo $f \in F$ . Es de índice finito si su número de clases de equivalencia es finito.

Para un lenguaje de árbol L dado , se puede definir una congruencia mediante $u \equiv L v$ si $C [u] \in L \Leftrightarrow C [v] \in L$ para cada contexto C .

El teorema de Myhill-Nerode para autómatas de árbol establece que las siguientes tres afirmaciones son equivalentes: ^{[ 15 ]}

L es un lenguaje de árboles reconocible
L es la unión de algunas clases de equivalencia de una congruencia de índice finito.
La relación $\equiv L$ es una congruencia de índice finito.

Historia

Según Engelfriet, ^{[ 16 ]} los autómatas de árboles finitos ascendentes fueron inventados alrededor de 1965 de forma independiente por ( Doner 1965 ) ( Doner 1970 ) y ( Thatcher & Wright 1968 ) , y algo más tarde por ( Pair & Quere 1968 ) ; los autómatas de árboles finitos descendentes fueron introducidos por ( Rabin 1969 ) y ( Magidor & Moran 1969 ) , y las gramáticas de árboles regulares por ( Brainerd 1969 ) .

En el número de noviembre de 1965 de Notices of the AMS , se presentaron dos resúmenes ( Doner 1965 ) y ( Thatcher & Wright 1965 ) , ambos recibidos el 17 de septiembre. Ambos resúmenes se hacen referencia el uno al otro, afirmando que los autómatas de árboles finitos se descubrieron de forma independiente, mientras que Thatcher & Wright admiten que su aplicación para demostrar la decidibilidad de "la teoría débil de segundo orden de las funciones sucesoras k " fue obtenida por primera vez por Doner.

Véase también

Teorema de Courcelle : una aplicación de autómatas de árbol para demostrar un metateorema algorítmico sobre grafos.
Los transductores de árbol extienden los autómatas de árbol de la misma manera que los transductores de palabra extienden los autómatas de palabra .
Autómatas de árbol alternantes
Autómatas de árbol infinito

Notas

↑ Comon et al. 2008 , sec. 1.1, p. 20.
↑ Comon et al. 2008 , sección 1.6, pág. 38.
↑ Comon et al. 2008 , sec. 1.1, p. 23.
^ Comon y col. 2008 , secc. 1.6, teorema 1.6.1, pág. 38.
↑ En sentido estricto, los autómatas deterministas descendentes no están definidos por Comon et al. (2008) , pero se utilizan allí (sección 1.6, proposición 1.6.2, pág. 38). Aceptan la clase de lenguajes de árboles cerrados por caminos (sección 1.8, ejercicio 1.6, págs. 43-44).
↑ Comon et al. 2008 , sección 1.8, ejercicios 1.2 y 1.6.3, págs. 43-44.
↑ Morawietz, Frank; Cornell, Tom (1997-07-07). "Representación de restricciones con autómatas" . Actas de la 35.ª reunión anual de la Asociación de Lingüística Computacional - ACL '98/EACL '98. EE. UU.: Asociación de Lingüística Computacional. págs. 468–475 . doi : 10.3115/976909.979677 .
↑ La noción en Comon et al. (2008 , sec. 1.4, teorema 1.4.3, p. 31-32) de homomorfismo de árboles es más general que la del artículo "homomorfismo de árboles".
↑ Comon et al. 2008 , sección 1.1, págs. 23-24.
↑ Formalmente: altura ( t ) > k , con k > 0 dependiendo solo de L , no de t
↑ Formalmente: hay un contexto C [.], un contexto no trivial $C' [.]$ y un término base u tal que $t = C [C' [u]]$ . Un "contexto" C [.] es un árbol con un agujero (o, correspondientemente, un término con una ocurrencia de una variable). Un contexto se llama "trivial" si el árbol consta solo del nodo agujero (o, correspondientemente, si el término es solo la variable). La notación C [ t ] significa el resultado de insertar el árbol t en el agujero de C [.] (o, correspondientemente, instanciar la variable a t ). Comon et al. 2008 , p. 17 , da una definición formal.
↑ Formalmente: $C [C' n [u]] \in L$ para todo n ≥ 0. La notación C ⁿ [.] significa el resultado de apilar n copias de C [.] una dentro de otra, cf. Comon et al. 2008 , p. 17 .
↑ Comon et al. 2008 , sección 1.2, pág. 29.
^ Comon y col. 2008 , secc. 1.3, teorema 1.3.1, pág. 30.
↑ Comon et al. 2008 , sec. 1.5, p. 36.
↑ Engelfriet 1975 .

↑ Sea Q = { q _a , q _g , q _f , q ₀ }, con el significado informal q _a : "vi una a ", q _g : "vi alguna g (...)", q _f : vi alguna f ( a , g (...))", q ₀ : "no vi ninguna de esas". Sea Q _f = { q _f } el conjunto de estados finales. El conjunto de reglas de transición Δ = { a → q _a ( a ), f ( q _a ( x ), q _g ( y )) → q _f ( f ( x , y )) }∪ { g ( q _f ( x )) → q _f ( g ( x )) }∪ { f ( q _f ( x ), q ( y )) → q _f ( f ( x , y )), f ( q ( x ), q _f ( y )) → q _f ( f ( x , y )), : q ∈ Q }∪ { g ( q ( x )) → q _g ( g ( x )), : q ∈ Q \ { q _f } }∪ { f ( q _g ( x ), q ( y )) → q ₀ ( f ( x , y )), f ( q ( x ), q _a ( y )) → q ₀ ( f (x , y )) : q ∈ Q } mantiene los significados informales de los estados durante el movimiento ascendente a través de un árbol t y, por lo tanto, acepta t si, y solo si, t contiene en algún lugar un subárbol f ( a , g (...)).

Referencias

Brainerd, Walter Scott (junio de 1967). Sistemas generadores de árboles y autómatas de árboles (tesis doctoral). Universidad de Purdue.
Brainerd, Walter Scott (1968). "La minimización de los autómatas de árbol" (PDF) . Information and Control . 13 (5): 484– 491. doi : 10.1016/S0019-9958(68)90917-0 .
Brainerd, Walter Scott (febrero de 1969). "Sistemas regulares generadores de árboles" . Información y control . 14 (2): 217– 231. doi : 10.1016/S0019-9958(69)90065-5 .
Común, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Loding, Christof; Tison, Sophie ; Tommasi, Marc (noviembre de 2008). Técnicas y aplicaciones de autómatas de árboles . Consultado el 11 de febrero de 2014 .
Doner, John (noviembre de 1965). "Decidibilidad de la teoría débil de segundo orden de dos sucesores (resumen)" . Notices of the AMS . 12 (7): 819.
Doner, John (julio de 1967). Receptores de árboles y algunas de sus aplicaciones (PDF) (Informe científico). Oficina de Investigación Científica de la Fuerza Aérea.
Doner, John (octubre de 1970). "Aceptores de árboles y algunas de sus aplicaciones" . Journal of Computer and System Sciences . 4 (5): 406– 451. doi : 10.1016/S0022-0000(70)80041-1 .
Engelfriet, Joost (1975). "Autómatas de árboles y gramáticas de árboles". arXiv : 1510.02036 [ cs.FL ].
Gécseg, Ferenc; Steinby, Magnus (1984). "Árbol autómata". arXiv : 1509.06233 [ cs.FL ].
Hosoya, Haruo (4 de noviembre de 2010). Fundamentos del procesamiento XML: El enfoque de autómatas de árbol . Cambridge University Press. ISBN 978-1-139-49236-2.
Magidor, Menachem; Moran, Gadi (1969). Autómatas finitos sobre árboles finitos (Informe técnico). Universidad Hebrea de Jerusalén.
Par, C.; Quere, A. (diciembre de 1968). "Définition et etude des Bilangages réguliers" . Información y Control . 13 (6): 565– 593. doi : 10.1016/S0019-9958(68)90999-6 .
Rabin, MO (1969). "Decidibilidad de teorías de segundo orden y autómatas en árboles infinitos" (PDF) . Transactions of the AMS . 141 : 1–35 . doi : 10.2307/1995086 . JSTOR 1995086 .
Thatcher, JW (1967). Caracterización de árboles de derivación de gramáticas libres de contexto mediante la teoría de autómatas finitos generalizados (nota de investigación). IBM. NC 719.
Thatcher, JW (dic. 1967). "Caracterización de árboles de derivación de gramáticas libres de contexto mediante una generalización de la teoría de autómatas finitos" . Journal of Computer and System Sciences . 1 (4): 317– 322. doi : 10.1016/S0022-0000(67)80022-9 .
Thatcher, JW; Wright, JB (noviembre de 1965). "Autómatas finitos generalizados (resumen 65T-469)" . Notices of the AMS . 12 (7): 820.
Thatcher, JW; Wright, JB (1966). Teoría generalizada de autómatas finitos con una aplicación a un problema de decisión de lógica de segundo orden (documento de investigación). IBM. RC-1713.
Thatcher, JW; Wright, JB (1968). "Teoría generalizada de autómatas finitos con una aplicación a un problema de decisión de lógica de segundo orden". Teoría de sistemas matemáticos . 2 (1).

Enlaces externos

Implementaciones

Grappa ( Archivado el 1 de febrero de 2019 en Wayback Machine ) - Bibliotecas de autómatas de árboles clasificados y no clasificados (OCaml)
Timbuk : herramientas para el análisis de alcanzabilidad y cálculos de autómatas de árbol (OCaml)
LETHAL - biblioteca para trabajar con autómatas de árboles finitos y setos (Java)
Biblioteca de autómatas de árbol verificada por máquina (Isabelle [OCaml, SML, Haskell])
VATA : una biblioteca para la manipulación eficiente de autómatas de árbol no deterministas (C++)

[FOOTNOTEComon_et_al.2008sect._1.1,_p._20-1] Comon et al. 2008 , sec. 1.1, p. 20.

[FOOTNOTEComon_et_al.2008sect._1.6,_p._38-2] Comon et al. 2008 , sección 1.6, pág. 38.

[FOOTNOTEComon_et_al.2008sect._1.1,_p._23-3] Comon et al. 2008 , sec. 1.1, p. 23.

[FOOTNOTEComon_et_al.2008sect._1.6,_theorem_1.6.1,_p._38-4] Comon y col. 2008 , secc. 1.6, teorema 1.6.1, pág. 38.

[5] En sentido estricto, los autómatas deterministas descendentes no están definidos por Comon et al. (2008) , pero se utilizan allí (sección 1.6, proposición 1.6.2, pág. 38). Aceptan la clase de lenguajes de árboles cerrados por caminos (sección 1.8, ejercicio 1.6, págs. 43-44).

[FOOTNOTEComon_et_al.2008sect._1.8,_exercise_1.2_and_1.6.3,_p.43-44-7] Comon et al. 2008 , sección 1.8, ejercicios 1.2 y 1.6.3, págs. 43-44.

[8] Morawietz, Frank; Cornell, Tom (1997-07-07). "Representación de restricciones con autómatas" . Actas de la 35.ª reunión anual de la Asociación de Lingüística Computacional - ACL '98/EACL '98. EE. UU.: Asociación de Lingüística Computacional. págs. 468–475 . doi : 10.3115/976909.979677 .

[9] La noción en Comon et al. (2008 , sec. 1.4, teorema 1.4.3, p. 31-32) de homomorfismo de árboles es más general que la del artículo "homomorfismo de árboles".

[FOOTNOTEComon_et_al.2008sect._1.1,_p._23-24-10] Comon et al. 2008 , sección 1.1, págs. 23-24.

[11] Formalmente: altura ( t ) > k , con k > 0 dependiendo solo de L , no de t

[12] Formalmente: hay un contexto C [.], un contexto no trivial $C' [.]$ y un término base u tal que $t = C [C' [u]]$ . Un "contexto" C [.] es un árbol con un agujero (o, correspondientemente, un término con una ocurrencia de una variable). Un contexto se llama "trivial" si el árbol consta solo del nodo agujero (o, correspondientemente, si el término es solo la variable). La notación C [ t ] significa el resultado de insertar el árbol t en el agujero de C [.] (o, correspondientemente, instanciar la variable a t ). Comon et al. 2008 , p. 17 , da una definición formal.

[13] Formalmente: $C [C' n [u]] \in L$ para todo n ≥ 0. La notación C ⁿ [.] significa el resultado de apilar n copias de C [.] una dentro de otra, cf. Comon et al. 2008 , p. 17 .

[FOOTNOTEComon_et_al.2008sect._1.2,_p._29-14] Comon et al. 2008 , sección 1.2, pág. 29.

[FOOTNOTEComon_et_al.2008sect._1.3,_theorem_1.3.1,_p._30-15] Comon y col. 2008 , secc. 1.3, teorema 1.3.1, pág. 30.

[FOOTNOTEComon_et_al.2008sect._1.5,_p_.36-16] Comon et al. 2008 , sec. 1.5, p. 36.

[FOOTNOTEEngelfriet1975-17] Engelfriet 1975 .

[6] Sea Q = { q _a , q _g , q _f , q ₀ }, con el significado informal q _a : "vi una a ", q _g : "vi alguna g (...)", q _f : vi alguna f ( a , g (...))", q ₀ : "no vi ninguna de esas". Sea Q _f = { q _f } el conjunto de estados finales. El conjunto de reglas de transición Δ = { a → q _a ( a ), f ( q _a ( x ), q _g ( y )) → q _f ( f ( x , y )) }∪ { g ( q _f ( x )) → q _f ( g ( x )) }∪ { f ( q _f ( x ), q ( y )) → q _f ( f ( x , y )), f ( q ( x ), q _f ( y )) → q _f ( f ( x , y )), : q ∈ Q }∪ { g ( q ( x )) → q _g ( g ( x )), : q ∈ Q \ { q _f } }∪ { f ( q _g ( x ), q ( y )) → q ₀ ( f ( x , y )), f ( q ( x ), q _a ( y )) → q ₀ ( f (x , y )) : q ∈ Q } mantiene los significados informales de los estados durante el movimiento ascendente a través de un árbol t y, por lo tanto, acepta t si, y solo si, t contiene en algún lugar un subárbol f ( a , g (...)).

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ a ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[

[

[

[ 14 ]

[ 15 ]

[ 16 ]