Gramática de árbol regular

En la ciencia informática teórica y la teoría del lenguaje formal , una gramática de árbol regular es una gramática formal que describe un conjunto de árboles dirigidos o términos . ^[1] Una gramática de palabras regulares puede verse como un tipo especial de gramática de árbol regular, que describe un conjunto de árboles de ruta única .

Definición

Una gramática de árbol regular G está definida por la tupla

G = ( N , Σ, Z , P ),

dónde

N es un conjunto finito de no terminales,
Σ es un alfabeto clasificado (es decir, un alfabeto cuyos símbolos tienen una aridad asociada ) disjunto de N ,
Z es el no terminal inicial, con $Z \in N$ , y
P es un conjunto finito de producciones de la forma A → t , con $A \in N$ , y $t \in T Σ (N)$ , donde T _Σ ( N ) es el término asociado álgebra , es decir, el conjunto de todos los árboles compuestos a partir de símbolos en $Σ \cup N$ según sus aridades, donde los no terminales se consideran nulares.

Derivación de árboles

La gramática G define implícitamente un conjunto de árboles: cualquier árbol que pueda derivarse de Z utilizando el conjunto de reglas P se dice que está descrito por G . Este conjunto de árboles se conoce como el lenguaje de G . Más formalmente, la relación ⇒ _G en el conjunto T _Σ ( N ) se define de la siguiente manera:

Un árbol $t 1 \in T Σ (N)$ puede derivarse en un solo paso en un árbol $t 2 \in T Σ (N)$ (en resumen: t ₁ ⇒ _G t ₂ ), si hay un contexto S y una producción $(A \to t) \in P$ tales que:

t ₁ = S [ A ], y
t2 = S [ _t] .

Aquí, un contexto significa un árbol con exactamente un agujero en él; si S es dicho contexto, S [ t ] denota el resultado de llenar el árbol t en el agujero de S .

El lenguaje de árbol generado por G es el lenguaje $L (G) = {t \in T Σ | Z \Rightarrow G * t}$ .

Aquí, T _Σ denota el conjunto de todos los árboles compuestos por símbolos de Σ, mientras que ⇒ _{G *} denota aplicaciones sucesivas de ⇒ _G .

Un lenguaje generado por alguna gramática de árbol regular se denomina lenguaje de árbol regular .

Ejemplos

Sea G ₁ = ( N ₁ ,Σ ₁ , Z ₁ , P ₁ ), donde

N ₁ = { Bool , BList } es nuestro conjunto de no terminales,
Σ ₁ = { true , false , nil , cons (.,.) } es nuestro alfabeto clasificado, las aridades se indican mediante argumentos ficticios (es decir, el símbolo cons tiene aridad 2),
Z ₁ = BList es nuestro no terminal inicial, y
El conjunto P ₁ consta de las siguientes producciones:
- Bool → falso
- Bool → verdadero
- Lista B → nulo
- BList → contras ( Bool , BList )

Un ejemplo de derivación de la gramática G ₁ es

BList ⇒ cons ( Bool , BList ) ⇒ cons ( falso , cons ( Bool , BList )) ⇒ cons ( falso , cons ( verdadero , nulo )).

La imagen muestra el árbol de derivación correspondiente ; es un árbol de árboles (imagen principal), mientras que un árbol de derivación en gramáticas de palabras es un árbol de cadenas (tabla superior izquierda).

El lenguaje de árbol generado por G ₁ es el conjunto de todas las listas finitas de valores booleanos, es decir, L ( G ₁ ) resulta ser igual a T _Σ1 . La gramática G ₁ corresponde a las declaraciones de tipos de datos algebraicos (en el lenguaje de programación ML estándar ):

  tipo de datos  Bool 
    =  falso 
    |  verdadero 
  tipo de datos  BList 
    =  nulo 
    |  desventajas  de  Bool  *  BList

Cada miembro de L ( G ₁ ) corresponde a un valor Standard-ML de tipo BList.

Para otro ejemplo, sea $G 2 = (N 1, Σ 1, BList 1, P 1 \cup P 2)$ , utilizando el conjunto no terminal y el alfabeto de arriba, pero extendiendo el conjunto de producción por P ₂ , que consiste en las siguientes producciones:

BList ₁ → contras ( verdadero , BList )
BList ₁ → contras ( falso , BList ₁ )

El lenguaje L ( G ₂ ) es el conjunto de todas las listas finitas de valores booleanos que contienen verdadero al menos una vez. El conjunto L ( G ₂ ) no tiene un tipo de datos equivalente en ML estándar ni en ningún otro lenguaje funcional. Es un subconjunto propio de L ( G ₁ ). El término del ejemplo anterior también está en L ( G ₂ ), como lo muestra la siguiente derivación:

BList ₁ ⇒ contras ( falso , BList ₁ ) ⇒ contras ( falso , contras ( verdadero , BList )) ⇒ contras ( falso , contras ( verdadero , nulo )).

Propiedades del lenguaje

Si L ₁ , L ₂ son ambos lenguajes de árbol regulares, entonces los conjuntos de árbol $L 1 \cap L 2, L 1 \cup L 2$ y L ₁ \ L ₂ también son lenguajes de árbol regulares, y es decidible si $L 1 \subseteq L 2$ y si L ₁ = L ₂ .

Caracterizaciones alternativas y relación con otros lenguajes formales

Las gramáticas de árboles regulares son una generalización de las gramáticas de palabras regulares .
Los lenguajes de árbol regulares también son los lenguajes reconocidos por los autómatas de árbol de abajo hacia arriba y los autómatas de árbol de arriba hacia abajo no deterministas. ^[2]
Rajeev Alur y Parthasarathy Madhusudan relacionaron una subclase de lenguajes de árboles binarios regulares con palabras anidadas y lenguajes visiblemente pushdown . ^[3]^[4]

Aplicaciones

Las aplicaciones de las gramáticas de árboles regulares incluyen:

Selección de instrucciones en la generación de código del compilador ^[5]
Un procedimiento de decisión para la teoría de fórmulas de lógica de primer orden sobre igualdad (=) y pertenencia al conjunto (∈) como únicos predicados ^[6]
Resolución de restricciones sobre conjuntos matemáticos ^[7]
El conjunto de todas las verdades expresables en lógica de primer orden acerca de un álgebra finita (que siempre es un lenguaje de árbol regular) ^[8]
Búsqueda gráfica ^[9]

Véase también

Restricción de conjunto : una generalización de las gramáticas de árboles regulares
Gramática de árboles adyacentes

Referencias

^ "Gramáticas de árboles regulares como formalismo para la subespecificación del alcance". CiteSeerX 10.1.1.164.5484 .
^ Comon, Hubert; Dauchet, Max; Gilleron, Remi; Löding, Christof; Jacquemard, Florent; Lugiez, Denis; Tison, Sophie; Tommasi, Marc (12 de octubre de 2007). «Técnicas y aplicaciones de autómatas de árboles» . Consultado el 25 de enero de 2016 .
^ Alur, R.; Madhusudan, P. (2004). "Lenguajes visiblemente pushdown" (PDF) . Actas del trigésimo sexto simposio anual de la ACM sobre teoría de la computación - STOC '04. págs. 202-211. doi :10.1145/1007352.1007390. ISBN 978-1581138528.S2CID 7473479 .Sección 4, Teorema 5,
^ Alur, R.; Madhusudan, P. (2009). "Añadir estructura de anidación a las palabras" (PDF) . Revista de la ACM . 56 (3): 1–43. CiteSeerX 10.1.1.145.9971 . doi :10.1145/1516512.1516518. S2CID 768006. Sección 7
^ Emmelmann, Helmut (1991). "Selección de código mediante reescritura de términos controlada regularmente". Generación de código: conceptos, herramientas y técnicas . Talleres de informática. Springer. pp. 3–29.
^ Comon, Hubert (1990). "Fórmulas ecuacionales en álgebras ordenadas". Proc. ICALP .
^ Gilleron, R.; Tison, S.; Tommasi, M. (1993). "Resolución de sistemas de restricciones de conjuntos utilizando autómatas de árbol". 10.º Simposio anual sobre aspectos teóricos de la informática . LNCS. Vol. 665. Springer. págs. 505–514.
^ Burghardt, Jochen (2002). "Axiomatización de álgebras finitas". Avances en inteligencia artificial . LNAI. Vol. 2479. Springer. págs. 222–234. arXiv : 1403.7347 . Código Bibliográfico :2014arXiv1403.7347B. ISBN . 3-540-44185-9.
^ Ziv-Ukelson, Smoly (2016). Algoritmos para búsqueda en red de gramática de árbol regular y su aplicación a la minería de patrones de infección humano-viral . J. of Comp. Bio.[1]

Lectura adicional

Las gramáticas de árboles regulares ya fueron descritas en 1968 por:
- Brainerd, WS (1968). "La minimalización de los autómatas arbóreos". Información y control . 13 (5): 484–491. doi : 10.1016/s0019-9958(68)90917-0 . hdl : 10945/40204 .
- 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): 57–81. doi :10.1007/BF01691346. S2CID 31513761.
Un libro dedicado a las gramáticas arbóreas es: Nivat, Maurice; Podelski, Andreas (1992). Tree Automata and Languages . Estudios en informática e inteligencia artificial. Vol. 10. Holanda Septentrional.
Los algoritmos sobre gramáticas de árboles regulares se analizan desde una perspectiva orientada a la eficiencia en: Aiken, A.; Murphy, B. (1991). "Implementing Regular Tree Expressions". Conferencia ACM sobre lenguajes de programación funcional y arquitectura informática . pp. 427–447. CiteSeerX 10.1.1.39.3766 .
Dada una aplicación de árboles a pesos, la generalización de Donald Knuth del algoritmo de la ruta más corta de Dijkstra se puede aplicar a una gramática de árbol regular para calcular para cada no terminal el peso mínimo de un árbol derivable. Con base en esta información, es sencillo enumerar su lenguaje en orden creciente de peso. En particular, cualquier no terminal con un peso mínimo infinito produce el lenguaje vacío. Véase: Knuth, DE (1977). "Una generalización del algoritmo de Dijkstra". Information Processing Letters . 6 (1): 1–5. doi :10.1016/0020-0190(77)90002-3.
Los autómatas de árboles regulares se han generalizado para admitir pruebas de igualdad entre nodos hermanos en árboles. Véase: Bogaert, B.; Tison, Sophie (1992). "Restricciones de igualdad y desigualdad en subtérminos directos en autómatas de árboles". Proc. 9th STACS . LNCS. Vol. 577. Springer. págs. 161–172.
Permitir pruebas de igualdad entre nodos más profundos conduce a la indecidibilidad. Véase: Tommasi, M. (1991). Automates d'Arbres avec Tests d'Égalités entre Cousins Germains . LIFL-IT.

[1] "Gramáticas de árboles regulares como formalismo para la subespecificación del alcance". CiteSeerX 10.1.1.164.5484 .

[Comon-2] Comon, Hubert; Dauchet, Max; Gilleron, Remi; Löding, Christof; Jacquemard, Florent; Lugiez, Denis; Tison, Sophie; Tommasi, Marc (12 de octubre de 2007). «Técnicas y aplicaciones de autómatas de árboles» . Consultado el 25 de enero de 2016 .

[Alur2004-3] Alur, R.; Madhusudan, P. (2004). "Lenguajes visiblemente pushdown" (PDF) . Actas del trigésimo sexto simposio anual de la ACM sobre teoría de la computación - STOC '04. págs. 202-211. doi :10.1145/1007352.1007390. ISBN 978-1581138528.S2CID 7473479 .Sección 4, Teorema 5,

[Alur2009-4] Alur, R.; Madhusudan, P. (2009). "Añadir estructura de anidación a las palabras" (PDF) . Revista de la ACM . 56 (3): 1–43. CiteSeerX 10.1.1.145.9971 . doi :10.1145/1516512.1516518. S2CID 768006. Sección 7

[5] Emmelmann, Helmut (1991). "Selección de código mediante reescritura de términos controlada regularmente". Generación de código: conceptos, herramientas y técnicas . Talleres de informática. Springer. pp. 3–29.

[6] Comon, Hubert (1990). "Fórmulas ecuacionales en álgebras ordenadas". Proc. ICALP .

[7] Gilleron, R.; Tison, S.; Tommasi, M. (1993). "Resolución de sistemas de restricciones de conjuntos utilizando autómatas de árbol". 10.º Simposio anual sobre aspectos teóricos de la informática . LNCS. Vol. 665. Springer. págs. 505–514.

[8] Burghardt, Jochen (2002). "Axiomatización de álgebras finitas". Avances en inteligencia artificial . LNAI. Vol. 2479. Springer. págs. 222–234. arXiv : 1403.7347 . Código Bibliográfico :2014arXiv1403.7347B. ISBN . 3-540-44185-9.

[9] Ziv-Ukelson, Smoly (2016). Algoritmos para búsqueda en red de gramática de árbol regular y su aplicación a la minería de patrones de infección humano-viral . J. of Comp. Bio.[1]