En lingüística computacional , el término formalismos gramaticales levemente sensibles al contexto se refiere a varios formalismos gramaticales que se han desarrollado en un esfuerzo por proporcionar descripciones adecuadas de la estructura sintáctica del lenguaje natural .
Todo formalismo gramatical levemente sensible al contexto define una clase de gramáticas levemente sensibles al contexto (las gramáticas que se pueden especificar en el formalismo) y, por lo tanto, también una clase de lenguajes levemente sensibles al contexto (los lenguajes formales generados por las gramáticas).
Fondo
Para 1985, varios investigadores en lingüística descriptiva y matemática habían proporcionado evidencia en contra de la hipótesis de que la estructura sintáctica del lenguaje natural puede describirse adecuadamente mediante gramáticas libres de contexto . [1] [2] Al mismo tiempo, el paso al siguiente nivel de la jerarquía de Chomsky , a las gramáticas sensibles al contexto , parecía tanto innecesario como indeseable. En un intento de precisar el poder formal exacto requerido para la descripción adecuada de la sintaxis del lenguaje natural, Aravind Joshi caracterizó "gramáticas (y lenguajes asociados ) que son solo un poco más poderosas que las gramáticas libres de contexto (lenguajes libres de contexto)". [3] Llamó a estas gramáticas gramáticas levemente sensibles al contexto ya los lenguajes asociados levemente sensibles al contexto .
La caracterización de Joshi de las gramáticas ligeramente sensibles al contexto estaba sesgada hacia su trabajo sobre la gramática adyacente al árbol (TAG). Sin embargo, junto con sus estudiantes Vijay Shanker y David Weir, Joshi pronto descubrió que los TAG son equivalentes, en términos de los lenguajes de cadenas generados, a la gramática principal introducida de forma independiente (HG). [4] Esto fue seguido por dos resultados de equivalencia similares, para gramática indexada lineal (LIG) [5] y gramática categorial combinatoria (CCG), [6] que mostró que la noción de sensibilidad leve al contexto es muy general y no ligado a un formalismo específico.
Los formalismos equivalentes a TAG se generalizaron mediante la introducción de sistemas de reescritura lineal sin contexto (LCFRS). [7] [8] Estas gramáticas definen una jerarquía infinita de lenguajes de cadena entre los lenguajes libres de contexto y sensibles al contexto, con los lenguajes generados por los formalismos equivalentes a TAG en el extremo inferior [ aclaración necesaria ] de la jerarquía. Independientemente y casi simultáneamente a LCFRS, Hiroyuki Seki et al. propuso el formalismo esencialmente idéntico de la gramática libre de contexto múltiple (MCFG). [9] LCFRS / MCFG se considera a veces como el formalismo más general para especificar gramáticas ligeramente sensibles al contexto. Sin embargo, varios autores han notado que algunas de las propiedades características de los formalismos equivalentes a TAG no son preservadas por LCFRS / MCFG, [10] y que hay lenguajes que tienen las propiedades características de sensibilidad leve al contexto pero no son generados por LCFRS. / MCFG. [11]
En los últimos años se ha observado un mayor interés en la clase restringida de sistemas de reescritura lineal libre de contexto bien anidados / gramáticas múltiples libres de contexto, [10] [12] que definen una clase de gramáticas que incluye correctamente los formalismos equivalentes a TAG, pero que es adecuada incluido en la jerarquía LCFRS / MCFG sin restricciones.
Caracterización
A pesar de la considerable cantidad de trabajo sobre el tema, no existe una definición formal generalmente aceptada de sensibilidad leve al contexto.
Según la caracterización original de Joshi, [3] una clase de gramáticas ligeramente sensibles al contexto debería tener las siguientes propiedades:
- dependencias limitadas entre series
- crecimiento constante
- análisis polinomial
Además de estos, se entiende que cada clase de gramáticas ligeramente sensibles al contexto debería poder generar todos los lenguajes libres de contexto.
La caracterización de Joshi no es una definición formal. Él nota: [3]
Ésta es sólo una caracterización aproximada porque las condiciones 1 y 3 dependen de las gramáticas, mientras que la condición 2 depende de los idiomas; Además, la condición 1 debe especificarse con mucha más precisión de lo que lo he hecho hasta ahora.
Otros autores han propuesto caracterizaciones alternativas de sensibilidad leve al contexto, algunas de las cuales toman la forma de definiciones formales. Por ejemplo, Laura Kallmeyer [13] adopta la perspectiva de que la sensibilidad leve al contexto debería definirse como una propiedad de las clases de lenguajes en lugar de, como en la caracterización de Joshi, clases de gramáticas. Esta definición basada en el lenguaje conduce a una noción del concepto diferente a la de Joshi.
Dependencias entre series
El término dependencias entre series se refiere a ciertos patrones característicos de ordenamiento de palabras, en particular a los patrones verbo-argumento observados en las cláusulas subordinadas en holandés [1] y alemán suizo. [2] Estos son los mismos patrones que pueden usarse para argumentar en contra de la libertad de contexto del lenguaje natural; por lo tanto, requerir gramáticas levemente sensibles al contexto para modelar dependencias entre series significa que estas gramáticas deben ser más poderosas que las gramáticas libres de contexto.
Kallmeyer [13] identifica la capacidad de modelar dependencias entre series con la capacidad de generar el lenguaje de copia
y sus generalizaciones a dos o más copias de w , hasta cierto límite. Estos lenguajes no están libres de contexto, lo que se puede mostrar utilizando el lema de bombeo .
Crecimiento constante
Un lenguaje formal está en constante crecimiento si cada cadena en el idioma es más larga que la siguiente cadena más corta por como máximo una constante (específica del idioma). A menudo se considera que los lenguajes que violan esta propiedad están más allá de la capacidad humana, aunque algunos autores han argumentado que ciertos fenómenos en el lenguaje natural muestran un crecimiento que no puede estar limitado por una constante. [14]
La mayoría de los formalismos gramaticales levemente sensibles al contexto (en particular, LCFRS / MCFG) en realidad satisfacen una propiedad más fuerte que el crecimiento constante llamado semilinealidad . [7] Un lenguaje es semilineal si su imagen bajo el mapeo de Parikh (el mapeo que "olvida" la posición relativa de los símbolos en una cadena, tratándolo efectivamente como una bolsa de palabras) es un lenguaje regular . Todos los lenguajes semilineales están en constante crecimiento, pero no todos los lenguajes en constante crecimiento son semilineales. [11]
Análisis de polinomios
Se dice que un formalismo gramatical tiene análisis polinomial si su problema de pertenencia se puede resolver en un tiempo polinomial determinista . Este es el problema de decidir, dada una gramática G escrito en el formalismo y una cadena w , si w es generado por G - es decir, si w es "gramatical", según G . La complejidad temporal de este problema se mide en términos del tamaño combinado de G y w .
Bajo el punto de vista de la sensibilidad contextual leve como una propiedad de las clases de idiomas, el análisis polinomial se refiere al problema de pertenencia al idioma. Este es el problema de decidir, para un lenguaje fijo L , si una cadena dada w pertenece a L . La complejidad temporal de este problema se mide en términos de la longitud de w ; ignora la pregunta de cómo se especifica L.
Tenga en cuenta que ambas interpretaciones del análisis sintáctico polinomial son idealizaciones en el sentido de que, para las aplicaciones prácticas, uno está interesado no solo en la pregunta sí / no de si una oración es gramatical, sino también en la estructura sintáctica que la gramática asigna a la oración.
Formalismos
A lo largo de los años, se han introducido una gran cantidad de formalismos gramaticales que satisfacen algunas o todas las propiedades características planteadas por Joshi. Varios de ellos tienen caracterizaciones alternativas basadas en autómatas que no se tratan en este artículo; por ejemplo, los lenguajes generados por la gramática adyacente al árbol se pueden caracterizar por autómatas pushdown integrados .
Formalismos equivalentes a TAG
- Gramática adyacente al árbol (TAG) [3]
- Gramática principal (HG) [15] [16]
- Gramática indexada lineal (LIG) [17]
- Gramática categorial combinatoria (CCG) [6]
- LCFRS / MCFG bien anidados de fan-out 2
Formalismos equivalentes a LCFRS / MCFG generales
- Sistemas de reescritura lineal sin contexto (LCFRS) [7] [8]
- Varias gramáticas libres de contexto (MCFG) [9]
- Gramáticas adyacentes a árboles multicomponente (MCTAG) [7]
- Gramáticas minimalistas (MG) [18]
- Gramáticas de concatenación de rango positivo (sRCG) simples (lineales, que no se borran, no combinatorias ) [19]
Formalismos equivalentes a LCFRS / MCFG bien anidados
- Macro gramáticas no duplicadas [20]
- Gramáticas sin contexto acopladas (CCFG) [21]
- Sistemas de reescritura lineal sin contexto bien anidados [12]
- Varias gramáticas libres de contexto bien anidadas [10]
Relaciones entre los formalismos
Los sistemas de reescritura lineal libre de contexto / múltiples gramáticas libres de contexto forman una jerarquía bidimensional de poder generativo con respecto a dos parámetros específicos de la gramática denominados abanico y rango . [22] Más precisamente, los lenguajes generados por LCFRS / MCFG con fan-out f ≥ 1 y rango r ≥ 3 se incluyen correctamente en la clase de idiomas generados por LCFRS / MCFG con rango r + 1 y fan-out f , como así como la clase de lenguajes generados por LCFRS / MCFG con rango ry abanico f + 1 . En presencia de un buen anidamiento, esta jerarquía colapsa a una jerarquía unidimensional con respecto al abanico; esto se debe a que cada LCFRS / MCFG bien anidado se puede transformar en un LCFRS / MCFG bien anidado equivalente con la misma distribución y rango 2. [10] [12] Dentro de la jerarquía LCFRS / MCFG, los lenguajes libres de contexto se puede caracterizar por las gramáticas con abanico 1; para este despliegue no hay diferencia entre gramáticas generales y bien anidadas. Los formalismos equivalentes a TAG se pueden caracterizar como LCFRS / MCFG bien anidados de fan-out 2.
Ver también
- Gramática adyacente al árbol
- Sistema de reescritura lineal sin contexto
- Gramática de concatenación de rangos
- Jerarquía de vertedero
Referencias
- ^ a b Riny Huybregts. "La débil insuficiencia de las gramáticas de estructura de frases libres de contexto". En Ger de Haan, Mieke Trommelen y Wim Zonneveld, editores, Van periferie naar kern , páginas 81–99. Foris, Dordrecht, Países Bajos, 1984.
- ^ a b Stuart M. Shieber. " Evidencia contra el contexto libre del lenguaje natural ". Lingüística y filosofía , 8 (3): 333–343, 1985.
- ^ a b c d Aravind K. Joshi. " Gramáticas adyacentes al árbol: ¿cuánta sensibilidad al contexto se requiere para proporcionar descripciones estructurales razonables? ". En David R. Dowty, Lauri Karttunen y Arnold M. Zwicky, editores, Natural Language Parsing , páginas 206–250. Prensa de la Universidad de Cambridge, 1985.
- ^ David J. Weir, K. Vijay-Shanker y Aravind K. Joshi. " La relación entre gramáticas adyacentes de árbol y gramáticas de la cabeza ". En Actas de la 24ª Reunión Anual de la Asociación de Lingüística Computacional (ACL) , páginas 67–74, Nueva York, EE. UU., 1986.
- ^ K. Vijay-Shanker. " Un estudio de gramáticas adyacentes a árboles ". Doctor. tesis, Universidad de Pensilvania, Filadelfia, EE. UU., 1987.
- ^ a b David J. Weir y Aravind K. Joshi. " Gramáticas categóricas combinatorias: poder generativo y relación con los sistemas de reescritura libre de contexto lineal ". En Actas de la 26ª Reunión Anual de la Asociación de Lingüística Computacional (ACL) , páginas 278–285, Buffalo, EE. UU., 1988.
- ^ a b c d K. Vijay-Shanker, David J. Weir y Aravind K. Joshi. " Caracterización de descripciones estructurales producidas por varios formalismos gramaticales ". En Actas de la 25ª Reunión Anual de la Asociación de Lingüística Computacional (ACL) , páginas 104-111, Stanford, CA, EE. UU., 1987.
- ^ a b David J. Weir. " Caracterización de formalismos gramaticales ligeramente sensibles al contexto ". Doctor. tesis, Universidad de Pensilvania, Filadelfia, EE. UU., 1988.
- ^ a b Hiroyuki Seki, Takashi Matsumura, Mamoru Fujii y Tadao Kasami. " Sobre múltiples gramáticas libres de contexto ". Ciencias de la Computación Teórica , 88 (2): 191-229, 1991.
- ^ a b c d Makoto Kanazawa. " El lema de bombeo para múltiples lenguajes libres de contexto bien anidados ". En Desarrollos en Teoría del Lenguaje. 13ª Conferencia Internacional, DLT 2009, Stuttgart, Alemania, 30 de junio a 3 de julio de 2009. Actas , volumen 5583 de Lecture Notes in Computer Science , páginas 312–325, 2009.
- ^ a b Laura Kallmeyer. " Sobre la reescritura no lineal levemente sensible al contexto ". Investigación sobre lenguaje y computación , 8 (4): 341–363, 2010.
- ^ a b c Carlos Gómez-Rodríguez, Marco Kuhlmann y Giorgio Satta. " Análisis eficiente de sistemas de reescritura libre de contexto lineal bien anidados ". En Proceedings of Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL) , páginas 276–284, Los Ángeles, EE. UU., 2010.
- ^ a b Laura Kallmeyer. Análisis más allá de las gramáticas libres de contexto . Springer, 2010.
- ^ Jens Michaelis y Marcus Kracht. " Semilinealidad como invariante sintáctica ". En Aspectos lógicos de la lingüística computacional. Primera Conferencia Internacional, LACL 1996, Nancy, Francia, 23-25 de septiembre de 1996. Documentos seleccionados , volumen 1328 de Lecture Notes in Computer Science , páginas 329-345. Springer, 1997.
- ^ Carl J. Pollard . "Gramáticas de estructura de frase generalizada, gramáticas de la cabeza y lenguaje natural". Doctor. tesis, Universidad de Stanford, 1984.
- ^ Kelly Roach. " Propiedades formales de las gramáticas de la cabeza ". En Alexis Manaster-Ramer, editor, Mathematics of Language , páginas 293–347. John Benjamins, 1987.
- ^ Gerald Gazdar. " Aplicabilidad de las gramáticas indexadas al lenguaje natural ". En Uwe Reyle y Christian Rohrer, editores, Análisis del lenguaje natural y teorías lingüísticas , páginas 69–94. D. Reidel, 1987.
- ^ Jens Michaelis. "El minimalismo derivacional es ligeramente sensible al contexto ". En Logical Aspects of Computational Linguistics, Tercera Conferencia Internacional, LACL 1998, Grenoble, Francia, 14-16 de diciembre de 1998, Documentos seleccionados , volumen 2014 de Lecture Notes in Computer Science , páginas 179-198. Springer, 1998.
- ^ Pierre Boullier. " Gramáticas de concatenación de rango ". En Harry C. Bunt, John Carroll y Giorgio Satta, editores, Nuevos desarrollos en la tecnología de análisis , volumen 23 de Tecnología del texto, el habla y el lenguaje , páginas 269–289. Editores académicos Kluwer, 2004.
- ^ Michael J. Fischer. " Gramáticas con producciones tipo macro ". En el Noveno Simposio Anual sobre Teoría de la Conmutación y Autómatas , páginas 131–142, Schenectady, NY, EE.
- ^ Günter Hotz y Gisela Pitsch. "Análisis de lenguajes sin contexto acoplados". Ciencias de la Computación Teórica , 161 (1–2): 205–233, 1996.
- ^ Owen Rambow y Giorgio Satta. " Una jerarquía bidimensional para sistemas de reescritura en paralelo ". Informe técnico IRCS-94-02, Universidad de Pensilvania, Filadelfia, EE. UU., 1994.