Gramàtiques de adjunción d'arbres

Gramàtiques de adjunción d'arbres

Les gramàtiques de adjunción d'arbres (Tree Adjoining Grammars, TAG) són una extensió de les gramàtiques formals independents del context i varen ser definides inicialment per Joshi, Levy i Takahashi en Joshi refina certs aspectes en el seu treball posterior, establint la definició moderna de TAG.

Definició

Formalment, una gramàtica de adjunción d'arbres és una quíntupla $(V_T,V_N,I,A,S)$ a on

• $V_T$ és un conjunt finito de símbols terminals.
• $V_N$ és un conjunt finito de símbols no-terminals.
• $I$ és un conjunt finito de arbres inicials.
• $A$ és un conjunt finito de arbres auxiliars.
• $S$ és un símbol distinguit de $V_N$ denominat axioma de la gramàtica.

Els arbres de $I$ i $A$ es denominen arbres elementals de la gramàtica. Els arbres inicials es caracterisen perque la seua raïl està etiquetada per l'axioma de la gramàtica, els seus nodos interiors estan etiquetats per no-terminals i els seus nodos full estan etiquetats per terminals o per la paraula buida. Els arbres auxiliars són com els arbres inicials en l'excepció de que l'etiqueta de la seua raïl pot ser un no-terminal arbitrari i perque un dels seus nodos full, que rep el nom de peu està etiquetat pel mateix no-terminal que etiqueta la seua raïl. El camí des del nodo raïl fins al nodo peu rep el nom de espina.

Explicació

Mentres que les gramàtiques lliures de context tenen regles per a reescriure símbols com a cadenes d'atres símbols, les gramàtiques de adjunción d'arbres tenen regles per a reescriure els nodos dels arbres com atres arbres (vore Arbre (teoria de grafos) i Arbre (estructura de senyes)

Els arbres inicials representen relacions de valència bàsiques, mentres que els arbres auxiliars permeten la recursión. Els arbres auxiliars tenen els nodos raïl i peu etiquetats en el mateix símbol. Una derivació comença en un arbre inicial, que es combina en uns atres per mig de les operacions de substitució o adjunción. La substitució reemplaça un nodo de la frontera per un arbre inicial la raïl del qual té la mateixa etiqueta que dit nodo. La adjunción inserta un arbre auxiliar en l'interior d'un atre arbre. Les etiquetes dels nodos raïl i peu de l'arbre auxiliar deuen coincidir en l'etiqueta del nodo al com s'adjunta.

Atres variants de TAG permeten arbres multi-component, arbres en múltiples nodos peu, aixina com atres extensions.

Les gramàtiques de adjunción d'arbres es descriuen freqüentment com suaument sensibles al context, ya que podeen certes propietats que les fan més potents (en térmens de capacitat generativa dèbil que les gramàtiques lliures de context, pero menys potents que les gramàtiques indexades o les sensibles al context.

S'ha conjeturado que les gramàtiques suaument sensibles al context són lo suficientment poderoses per a modelar el llenguage natural a l'hora que es poden analisar eficientemente (en temps polinomial).

Referències

Bibliografia

• Joshi, Aravind (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», D. Dowty, L. Karttunen, and A. Zwicky, (eds.) (ed.). Natural Language Processing: Theoretical, Computational, and Psychological Perspectives, New York, NY: Cambridge University Press, pp. 206–250.

• Joshi, Aravind (1987). «An introduction to tree adjoining grammars», Alexis Manaster-Ramer, (ed.) (ed.). Mathematics of Language, John Benjamins Publishing Co., pp. 87-115.
• Jurafsky, Daniel (2000). Speech and Language Processing, Prentice Hall, pp. 354.
• Alonso Pardo (2000). Interpretació tabular d'autómates per a llenguages de adjunción d'arbres (tesis doctoral), Universitat de La Corunya.

Enllaces externs

• The XTAG project, una gramàtica d'àmplia cobertura de l'anglés, desenrollada manualment.
• Un tutorial sobre TAG (en anglés)
• Interpretació tabular d'autómates per a llenguages de adjunción d'arbres, una tesis doctoral en una àmplia introducció a les TAG i als seus algoritmes d'anàlisis sintàctic
• Grup COLE de l'Universitat de Vigo
• Grup LYS de l'Universitat de La Corunya
• Grup Itálica de l'Universitat de Sevilla