Gramática de adición de árboles

La gramática contigua al árbol TAG ) es una gramática formal inventada por Aravind Joshi ( inglés  Esta gramática generaliza la gramática libre de contexto en el sentido de que las unidades elementales en las reglas de inferencia son árboles en lugar de caracteres individuales. Por lo tanto, la gramática define las reglas para reemplazar los nodos del árbol con subárboles (ver árbol en teoría de grafos y árbol en informática ).

Historia

TAG surgió como resultado de la investigación de Joshi y sus estudiantes de una familia de gramáticas adjuntas [1] . Las gramáticas adjuntas son adecuadas para analizar frases que incluyen una palabra principal y muchas palabras dependientes que limitan el significado de la palabra principal (por ejemplo, "una casa muy grande"). Sin embargo, no caracterizan claramente las frases en las que ni una sola palabra puede cumplir la función de toda la estructura. Lo mismo se aplica a la gramática con estructura de frase . En 1969, Joshi introdujo una familia de gramáticas que explotaba esta complementariedad mezclando dos tipos de reglas. Esta familia no forma parte de la jerarquía de Chomsky [2] y pertenece a las gramáticas débilmente sensibles al contexto , es decir, en términos de generación de propiedades, es más fuerte que las gramáticas libres de contexto , pero más débil que las sensibles al contexto [3] . Las gramáticas de adición de árboles son débilmente equivalentes a las gramáticas indexadas lineales , las gramáticas categóricas combinatorias y las gramáticas de encabezado [4] (para cualquier gramática de adición de árboles, se puede construir una gramática correspondiente a partir de cualquiera de estas tres familias que generará las mismas cadenas).

Descripción

Una regla TAG es un árbol con un nodo de hoja al que se puede adjuntar una palabra (LTAG).

Hay dos tipos de árboles: "inicial" (a menudo denominado ' ') y "auxiliar" (' '). Los árboles iniciales representan las valencias principales de la frase, mientras que los árboles auxiliares permiten el uso de la recursividad [5] . Los árboles auxiliares tienen el nodo superior y el nodo hoja marcados con el mismo símbolo.

Los reemplazos parten del árbol inicial y se realizan por sustitución o adición . Un reemplazo reemplaza un nodo con un árbol cuyo nodo superior está etiquetado con el mismo símbolo que el que se reemplaza. Append inserta un subárbol auxiliar en el centro del árbol [6] . Un árbol auxiliar debe etiquetarse con la misma etiqueta que el nodo al que está conectado.

Notas

  1. ↑ Joshi, Aravind; S. R. Kosaraju, H. Yamada. Gramáticas  adjuntas de cadenas (neopr.) . - Actas del Décimo Simposio Anual sobre Teoría de Autómatas, Waterloo, Canadá, 1969.
  2. ↑ Joshi, Aravind. Propiedades de las gramáticas formales con tipos mixtos de reglas y su relevancia lingüística  (inglés)  : revista. - Actas del Tercer Simposio Internacional de Lingüística Computacional, Estocolmo, Suecia, 1969.
  3. ↑ Joshi, Aravind. Cuánta sensibilidad al contexto es necesaria para caracterizar las descripciones estructurales // Procesamiento del lenguaje natural: perspectivas teóricas, computacionales y psicológicas  (inglés) / D. Dowty, L. Karttunen y A. Zwicky, (eds.). - Nueva York, NY: Cambridge University Press , 1985. - P. 206-250.
  4. ↑ Vijay-Shanker, K. y Weir, David J. 1994. La equivalencia de cuatro extensiones de gramáticas libres de contexto . Teoría de sistemas matemáticos 27 (6): 511-546.
  5. ↑ Jurafsky, Daniel; James H. Martín. Procesamiento del habla y lenguaje  (indefinido) . - Upper Saddle River, NJ: Prentice Hall , 2000. - Pág  . 354 .
  6. ↑ Joshi, Aravind; Owen Rambow (2003). "Un formalismo para la gramática de dependencia basado en la gramática contigua al árbol" (PDF) . Actas de la Conferencia sobre Teoría del Significado-Texto . Parámetro obsoleto utilizado |coauthors=( ayuda ) Archivado el 29 de noviembre de 2020 en Wayback Machine .

Enlaces

En inglés: