Gramáticas de adjunción de árboles

Las gramáticas de adjunción de árboles (Tree Adjoining Grammars, TAG) son una extensión de las gramáticas formales independientes del contexto y fueron definidas inicialmente por Joshi, Levy y Takahashi en^[1] Joshi refina ciertos aspectos en su trabajo posterior^[2] , estableciendo la definición moderna de TAG.

Definición

Formalmente, una gramática de adjunción de árboles es una quíntupla donde

• es un conjunto finito de símbolos terminales.
• es un conjunto finito de símbolos no-terminales.
• es un conjunto finito de árboles iniciales.
• es un conjunto finito de árboles auxiliares.
• es un símbolo distinguido de denominado axioma de la gramática.

Los árboles de y se denominan árboles elementales de la gramática. Los árboles iniciales se caracterizan porque su raíz está etiquetada por el axioma de la gramática, sus nodos interiores están etiquetados por no-terminales y sus nodos hoja están etiquetados por terminales o por la palabra vacía. Los árboles auxiliares son como los árboles iniciales con la excepción de que la etiqueta de su raíz puede ser un no-terminal arbitrario y porque uno de sus nodos hoja, que recibe el nombre de pie está etiquetado por el mismo no-terminal que etiqueta su raíz. El camino desde el nodo raíz hasta el nodo pie recibe el nombre de espina.

Explicación

Mientras que las gramáticas libres de contexto tienen reglas para reescribir símbolos como cadenas de otros símbolos, las gramáticas de adjunción de árboles tienen reglas para reescribir los nodos de los árboles como otros árboles (véase Árbol (teoría de grafos) y Árbol (estructura de datos)

Los árboles iniciales representan relaciones de valencia básicas, mientras que los árboles auxiliares permiten la recursión.^{[3] [4]} Los árboles auxiliares tienen los nodos raíz y pie etiquetados con el mismo símbolo. Una derivación comienza con un árbol inicial, que se combina con otros mediante las operaciones de sustitución o adjunción. La sustitución reemplaza un nodo de la frontera por un árbol inicial cuya raíz tiene la misma etiqueta que dicho nodo. La adjunción inserta un árbol auxiliar en el interior de otro árbol. Las etiquetas de los nodos raíz y pie del árbol auxiliar deben coincidir con la etiqueta del nodo al cual se adjunta.

Otras variantes de TAG permiten árboles multi-componente, árboles con múltiples nodos pie, así como otras extensiones.

Las gramáticas de adjunción de árboles se describen frecuentemente como suavemente sensibles al contexto, ya que podeen ciertas propiedades que las hacen más potentes (en términos de capacidad generativa débil que las gramáticas libres de contexto, pero menos potentes que las gramáticas indexadas o las sensibles al contexto.

Se ha conjeturado que las gramáticas suavemente sensibles al contexto son lo suficientemente poderosas para modelar el lenguaje natural al tiempo que se pueden analizar eficientemente (en tiempo polinomial).^[5]

Aplicaciones

El ámbito más habitual en el que se usan las TAG es el de la lingüística computacional y el procesamiento del lenguaje natural ya que poseen propiedades que les permiten caracterizar adecuadamente las descripciones estructurales asociadas a las frases de un idioma. Entre estas propiedades podemos citar:

• El dominio extendido de localidad. Las TAG poseen un dominio de localidad más amplio que las gramáticas libres de contexto y que las gramáticas basadas en un esqueleto libre de contexto. Al aplicar las TAG al reconocimiento de lenguajes naturales, las estructuras lingüísticas mínimas (oraciones simples) se representan mediante árboles iniciales, mientras que las estructuras lingüísticas mínimas pero con una faceta recurrente adicional (adjuntos de oraciones) se corresponden con los árboles auxiliares.

• La factorización de la recursión en el dominio de dependencias. Los árboles son los dominios sobre los cuales se establecen dependencias tales como la concordancia, subcategorización y relleno de huecos. La operación de adjunción, mediante la inserción de árboles auxiliares dentro de otros árboles, permite que tales dependencias sean de larga distancia, aunque hayan sido especificadas localmente en un sólo árbol.

• La lexicalización. Existe actualmente una tendencia en dar gran importancia a la información léxica debido a la influencia que ejerce en los dems niveles del lenguaje. Este nuevo escenario ha sido propicio para desviar hacia el componente sintctico ciertos aspectos que anteriormente eran contemplados en el componente léxico. Las TAGs se encuadran en dicha corriente puesto que exigen que la frontera de todos los árboles que conforman la gramática incluyan necesariamente al menos un símbolo terminal.

Referencias

Bibliografía

• Joshi, Aravind; Leon Levy, and M. Takahashi (1975). «Tree adjunt grammars». Journal of Computer and System Sciences, 10(1). pp. 136-162. 
• Joshi, Aravind (1985). «How much context-sensitivity is necessary for characterizing structural descriptions». En D. Dowty, L. Karttunen, and A. Zwicky, (eds.). Natural Language Processing: Theoretical, Computational, and Psychological Perspectives. Cambridge University Press. pp. 206–250. 
• Joshi, Aravind (1987). «An introduction to tree adjoining grammars». En Alexis Manaster-Ramer, (ed.). Mathematics of Language. John Benjamins Publishing Co.. pp. 87-115. 
• Jurafsky, Daniel; James H. Martin (2000). Speech and Language Processing. Prentice Hall. pp. 354. 
• Alonso Pardo, Miguel Ángel (2000). Interpretación tabular de autómatas para lenguajes de adjunción de árboles (tesis doctoral). Universidad de La Coruña. 

Enlaces externos

• The XTAG project, una gramática de amplia cobertura del inglés, desarrollada manualmente.
• Un tutorial sobre TAG (en inglés)
• Interpretación tabular de autómatas para lenguajes de adjunción de árboles, una tesis doctoral con una amplia introducción a las TAG y a sus algoritmos de análisis sintáctico
• Grupo COLE de la Universidad de Vigo
• Grupo LYS de la Universidad de La Coruña
• Grupo Itálica de la Universidad de Sevilla