Gramática de adjunción de árboles

La gramática de adjunción de árboles ( TAG ) es un formalismo gramatical definido por Aravind Joshi . Las gramáticas de adjunción de árboles son similares a las gramáticas libres de contexto , pero la unidad elemental de reescritura es el árbol en lugar del símbolo. 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) ).

Historia

TAG se originó en las investigaciones de Joshi y sus estudiantes sobre la familia de gramáticas de adjunción (AG), ^{[ 1 ]} la "gramática de cadenas" de Zellig Harris . ^{[ 2 ]} Las AG manejan propiedades exocéntricas del lenguaje de manera natural y efectiva, pero no tienen una buena caracterización de las construcciones endocéntricas ; lo contrario es cierto para las gramáticas de reescritura , o gramática de estructura de frases (PSG). En 1969, Joshi introdujo una familia de gramáticas que explota esta complementariedad al mezclar los dos tipos de reglas. Unas pocas reglas de reescritura muy simples son suficientes para generar el vocabulario de cadenas para las reglas de adjunción. Esta familia es distinta de la jerarquía de Chomsky-Schützenberger , pero se cruza con ella de maneras interesantes y lingüísticamente relevantes. ^{[ 3 ]} Las cadenas centrales y las cadenas adjuntas también pueden generarse mediante una gramática de dependencia , evitando por completo las limitaciones de los sistemas de reescritura. ^{[ 4 ]}^{[ 5 ]}

Descripción

Ilustración esquemática de la operación de adjunción: el árbol $\alpha$ se combina con un árbol auxiliar $\beta$ en un nodo etiquetado con un símbolo no terminal $X$ , que también debe ser el nodo raíz y pie del árbol auxiliar. El árbol resultante es más profundo que el original.

{\displaystyle \alpha } — Ilustración esquemática de la operación de adjunción: el árbol $\alpha$ se combina con un árbol auxiliar $\beta$ en un nodo etiquetado con un símbolo no terminal $X$ , que también debe ser el nodo raíz y pie del árbol auxiliar. El árbol resultante es más profundo que el original.

Ilustración esquemática de la operación de sustitución: dos árboles ( $\alpha$ y $\beta$ ; tenga en cuenta que estos no tienen por qué ser árboles *elementales* ) se unen en un nodo etiquetado con no terminal. $X$ ; este nodo es uno de los nodos hoja marcados para sustitución en $\alpha$ y la raíz de $\beta$ es un nodo con el mismo no terminal.

Una etiqueta se puede definir como una tupla de 5 elementos. $\langle \Sigma ,NT,I,A,S\rangle$ con: ^{[ 6 ]}

$\Sigma$ como el conjunto finito de símbolos terminales ;
$NT$ como el conjunto finito de símbolos no terminales, disjuntos de $\Sigma$ ;
$I$ $I$ como un conjunto finito de árboles finitos llamados árboles iniciales ;
- Los árboles iniciales tienen nodos internos no terminales. La frontera puede constar de terminales y no terminales. Los no terminales en la frontera están marcados para sustitución (normalmente añadiendo el símbolo ' $\downarrow$ ' después del símbolo no terminal). Los nodos marcados para sustitución no pueden ser conexos.
$A$ $A$ como un conjunto finito de árboles finitos llamados árboles auxiliares ;
- Los árboles auxiliares tienen un nodo de hoja especial conocido como nodo de pie (normalmente marcado con ' $\ast$ ') que debe tener el mismo símbolo no terminal que la raíz del árbol. Los nodos pie no se pueden sustituir; todos los demás nodos no terminales en la frontera están marcados para sustitución. Al igual que en los árboles iniciales, los nodos internos tienen símbolos no terminales.
$S$ como símbolo de inicio especial, perteneciente al conjunto de no terminales.

Además, se han introducido TAGs con restricciones de adjunción en los nodos. Una restricción de adjunción en un nodo puede: prohibir completamente la adjunción (NA, para adjunción nula ); hacerla obligatoria (OA); o permitir solo la adjunción de árboles auxiliares seleccionados (SA). ^{[ 6 ]}

Los dos tipos de árboles básicos en TAG: árboles iniciales (a menudo denotados por ' $\alpha$ ') y árboles auxiliares (' $\beta$ Los árboles iniciales representan relaciones de valencia básicas, mientras que los árboles auxiliares permiten la recursión. ^{[ 7 ]}

Una derivación comienza con un árbol inicial, que se combina con otros árboles mediante sustitución o adjunción. La sustitución reemplaza un nodo frontera con un árbol inicial cuyo nodo raíz tiene la misma etiqueta que la hoja que se sustituye. La adjunción inserta un árbol auxiliar —ya sea en un nodo frontera o interno— cuyas etiquetas de raíz y pie coinciden con la etiqueta del nodo al que se une. De este modo, la adjunción puede tener el efecto de insertar un árbol auxiliar en el centro de otro árbol, operación que puede aplicarse recursivamente. ^{[ 4 ]}

Complejidad y aplicación

Para cada gramática libre de contexto , se puede generar una gramática de adjunción de árboles que acepte el mismo lenguaje de cadenas. Por lo tanto, las TAG pueden generar todos los lenguajes libres de contexto ; ^{[ 8 ]} también pueden generar algunos —pero no todos— los lenguajes sensibles al contexto .

Dos ejemplos de lenguajes sensibles al contexto/no libres de contexto que pueden generar los TAG (con restricciones de adjunción) son: ^{[ 8 ]}

El lenguaje de copia (es decir, el lenguaje de los cuadrados ), en el que se repite una cadena arbitraria: $\left\{ww\mid w\in \Sigma ^{*}\right\}$
Los tres árboles elementales necesarios para generar el lenguaje de copia con el alfabeto que contiene solo las letras a y b.
El lenguaje count-4: $\{a^{n}b^{n}c^{n}d^{n}|1\leq n\}$
Árboles necesarios para generar el lenguaje count-4 incluyendo la palabra vacía. $\epsilon$ , formalmente definido como ${\text{Count}}_{4}=\left\{a^{n}b^{n}c^{n}d^{n}\mid n\geq 0\right\}$ .

Las gramáticas de adjunción de árboles son más potentes (en términos de capacidad generativa débil ) que las gramáticas libres de contexto, pero menos potentes que los sistemas de reescritura lineales libres de contexto , ^{[ 9 ]} indexados , ^{[ nota 1 ]} o las gramáticas sensibles al contexto .

Dos ejemplos de lenguajes sensibles al contexto que los TAG no pueden generar son: ^{[ 8 ]}

El lenguaje de las cadenas triplicadas (es decir, el lenguaje de los cubos ): $\left\{www\mid w\in \Sigma ^{*}\right\}$
Lenguajes con más de cuatro cadenas de caracteres distintas de igual longitud; por ejemplo, el lenguaje count-5: $\{a^{n}b^{n}c^{n}d^{n}f^{n}|1\leq n\}$

El procesamiento de los lenguajes que pueden generar los TAG puede representarse mediante un autómata de pila integrado .

Las gramáticas de adjunción de árboles se describen a menudo como ligeramente sensibles al contexto . Se conjetura que estas clases de gramáticas son lo suficientemente potentes como para modelar lenguajes naturales , manteniendo al mismo tiempo una eficiente analizabilidad sintáctica en el caso general. ^{[ 8 ]}

Equivalencias

Vijay-Shanker y Weir (1994) ^{[ 10 ]} demostraron que las gramáticas indexadas lineales , la gramática categorial combinatoria , las gramáticas de adjunción de árboles y las gramáticas de cabeza son formalismos débilmente equivalentes , en el sentido de que todas definen los mismos lenguajes de cadenas.

Variantes

Las gramáticas de adjunción de árboles lexicalizadas (LTAG) son una variante de las gramáticas de adjunción de árboles (TAG) en las que cada árbol elemental (inicial o auxiliar) se asocia con un elemento léxico. Cada árbol tiene al menos un terminal como nodo hoja, que se denomina ancla (léxica) del árbol. El Grupo de Investigación XTAG del Instituto de Investigación en Ciencias Cognitivas de la Universidad de Pensilvania ha desarrollado una gramática lexicalizada para el inglés. ^{[ 5 ]}

Otras variantes de TAG permiten árboles multicomponente , árboles con múltiples nodos de pie y otras extensiones.

Véase también

gramática de cadenas

Notas

↑ Esto se debe a que, para cada gramática de adjunción de árboles,se puede encontrar una gramática indexada lineal que produce el mismo lenguaje (véase más abajo ); y, para esta última, a su vez se puede encontrar una gramática indexada débilmente equivalente (propia) (véase: Gramática indexada#Poder computacional ).

Referencias

↑ Joshi, Aravind; SR Kosaraju; H. Yamada (1969). "Gramáticas adjuntas de cadenas" (Documento). Actas del Décimo Simposio Anual sobre Teoría de Autómatas, Waterloo, Canadá.Joshi, Aravind K.; Kosaraju, S. Rao; Yamada, HM (1972), "Gramáticas adjuntas de cadenas: I. Adjunción local y distribuida", Information and Control , 21 (2): 93– 116, doi : 10.1016/S0019-9958(72)90051-4Joshi, Aravind K.; Kosaraju, S. Rao; Yamada, HM (1972), "Gramáticas adjuntas de cadenas: II. Representación ecuacional, símbolos nulos y relevancia lingüística", Information and Control , 21 (3): 235–260 , doi : 10.1016/S0019-9958(72)80005-6
↑ Harris, Zellig S. (1962). Análisis de cadenas de la estructura de las oraciones . Artículos sobre lingüística formal. Vol. 1. La Haya: Mouton & Co.
↑ Joshi, Aravind (1969). "Propiedades de las gramáticas formales con tipos mixtos de reglas y su relevancia lingüística" (Documento). Actas del Tercer Simposio Internacional sobre Lingüística Computacional, Estocolmo, Suecia.
1 2 Joshi, Aravind; Owen Rambow (2003). "Un formalismo para la gramática de dependencias basado en la gramática de adjunción de árboles" (PDF) . Actas de la Conferencia sobre Teoría del Texto-Significado .
1 2 "Una gramática adjunta de árbol lexicalizada para el inglés" .
1 2 Joshi, Aravind K. Joshi; Shabes, Yves (marzo de 1991). Gramáticas de adjunción de árboles y gramáticas lexicalizadas . MS-CIS-91-22 (Informe técnico). Departamento de Ciencias de la Computación e Información, Universidad de Pensilvania.
↑ Jurafsky, Daniel ; James H. Martin (2000). Procesamiento del habla y del lenguaje . Upper Saddle River, NJ: Prentice Hall. pág. 354.
1 2 3 4 Joshi, Aravind (1985). "¿Cuánta sensibilidad al contexto es necesaria para caracterizar las descripciones estructurales?". En D. Dowty; L. Karttunen; A. Zwicky (eds.). Procesamiento del lenguaje natural: perspectivas teóricas, computacionales y psicológicas . Nueva York, NY: Cambridge University Press. pp. 206-250 . ISBN 9780521262033.
↑ Kallmeyer, Laura (2010). Análisis sintáctico más allá de las gramáticas libres de contexto. Springer. Aquí: págs. 215-216
↑ Vijay-Shanker, K. y Weir, David J. 1994. La equivalencia de cuatro extensiones de gramáticas libres de contexto . Mathematical Systems Theory 27(6): 511–546.

Enlaces externos

El proyecto XTAG , que utiliza una etiqueta (TAG) para el procesamiento del lenguaje natural.
Un tutorial sobre TAG
Documentación de SemConst: Un breve repaso sobre la sintaxis y la interfaz semántica problemáticas dentro del marco TAG.
El proyecto TuLiPa La arquitectura de análisis lingüístico de Tübingen (TuLiPA) es un entorno de análisis sintáctico (y semántico) multiformalista, diseñado principalmente para gramáticas de adjunción de árboles multicomponente con tuplas de árbol.
El Metagrammar Toolkit ofrece diversas herramientas para editar y compilar metagramáticas en etiquetas (TAG). También incluye una amplia cobertura de metagramáticas en francés.
LLP2 Un analizador sintáctico de gramática lexicalizada con árbol adjunto que proporciona un entorno gráfico fácil de usar (página en francés)

[10] Esto se debe a que, para cada gramática de adjunción de árboles,se puede encontrar una gramática indexada lineal que produce el mismo lenguaje (véase más abajo ); y, para esta última, a su vez se puede encontrar una gramática indexada débilmente equivalente (propia) (véase: Gramática indexada#Poder computacional ).

[JoshiKosarajuYamada1969-1] Joshi, Aravind; SR Kosaraju; H. Yamada (1969). "Gramáticas adjuntas de cadenas" (Documento). Actas del Décimo Simposio Anual sobre Teoría de Autómatas, Waterloo, Canadá.Joshi, Aravind K.; Kosaraju, S. Rao; Yamada, HM (1972), "Gramáticas adjuntas de cadenas: I. Adjunción local y distribuida", Information and Control , 21 (2): 93– 116, doi : 10.1016/S0019-9958(72)90051-4Joshi, Aravind K.; Kosaraju, S. Rao; Yamada, HM (1972), "Gramáticas adjuntas de cadenas: II. Representación ecuacional, símbolos nulos y relevancia lingüística", Information and Control , 21 (3): 235–260 , doi : 10.1016/S0019-9958(72)80005-6

[2] Harris, Zellig S. (1962). Análisis de cadenas de la estructura de las oraciones . Artículos sobre lingüística formal. Vol. 1. La Haya: Mouton & Co.

[Joshi1969-3] Joshi, Aravind (1969). "Propiedades de las gramáticas formales con tipos mixtos de reglas y su relevancia lingüística" (Documento). Actas del Tercer Simposio Internacional sobre Lingüística Computacional, Estocolmo, Suecia.

[joshi-rambow2003-4] 1 2 Joshi, Aravind; Owen Rambow (2003). "Un formalismo para la gramática de dependencias basado en la gramática de adjunción de árboles" (PDF) . Actas de la Conferencia sobre Teoría del Texto-Significado .

[xtagenglish-5] 1 2 "Una gramática adjunta de árbol lexicalizada para el inglés" .

[joshi-shabes-1991-6] 1 2 Joshi, Aravind K. Joshi; Shabes, Yves (marzo de 1991). Gramáticas de adjunción de árboles y gramáticas lexicalizadas . MS-CIS-91-22 (Informe técnico). Departamento de Ciencias de la Computación e Información, Universidad de Pensilvania.

[jurafsky-martin2000-7] Jurafsky, Daniel ; James H. Martin (2000). Procesamiento del habla y del lenguaje . Upper Saddle River, NJ: Prentice Hall. pág. 354.

[joshi1985-8] 1 2 3 4 Joshi, Aravind (1985). "¿Cuánta sensibilidad al contexto es necesaria para caracterizar las descripciones estructurales?". En D. Dowty; L. Karttunen; A. Zwicky (eds.). Procesamiento del lenguaje natural: perspectivas teóricas, computacionales y psicológicas . Nueva York, NY: Cambridge University Press. pp. 206-250 . ISBN 9780521262033.

[9] Kallmeyer, Laura (2010). Análisis sintáctico más allá de las gramáticas libres de contexto. Springer. Aquí: págs. 215-216

[vijayshankarAndWeir1995-11] Vijay-Shanker, K. y Weir, David J. 1994. La equivalencia de cuatro extensiones de gramáticas libres de contexto . Mathematical Systems Theory 27(6): 511–546.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ nota 1 ]

[ 10 ]