Investigaciones sobre gramáticas categorialesalgoritmos de Parsing y equivalencia entre formalismos

Abstract

Esta Tesis Doctoral muestra el resultado de una investigación sobre la utilización del formalismo de las Gramáticas Categoriales (GC) para la descripción y parsing de los lenguajes naturales y formales, El estudio se ha centrado sobre algunos aspectos que encontrábamos problemáticos para la aplicación práctica de las GC, a saber: A,- Equivalencia fuerte entre las Gramáticas Independientes de Contexto (GIC) y GC. B,- Falta de expresividad de las GC. C,- Existencia de múltiples sistemas de etiquetado semántico para el Cálculo de Lamberk (CL) y ausencia de una definición precisa de la ambigüedad espuria. D,- Eficiencia y robustez de los algoritmos de parsing. Se comienza estudiando la posible utilización del CL a las GIC, concluyendo que esto es posible. Para demostrarlo introducimos un modelo algebraico, y comprobamos que el CL es válido en él. Otra forma de considerar el resultado anterior es pensar que hemos extendido las GC a una teoría conseguida al añadir axiomas al CL. El sistema resultante constituye una teoría unificada de las GC y las GIC. A continuación discutimos las implicaciones que conlleva la utilización del CL en las GIC, así como sus ventajas y desventajas. Respecto a la existencia de múltiples sistemas de etiquetado en CL, comenzamos introduciendo dos versiones diferentes para el Cálculo en Deducción Natural (DN) de las GC. Utilizando una de las variantes es como mostramos la validez del Principio de Inversión y la equivalencia Curry-Howard en DN. Posteriormente, y utilizando dos algoritmos nuevos de conversión entre las pruebas en CL y las deduciones en DN. Obtenemos un etiquetado semántico en CL que proponemos como definición de la ambigüedad espuria. Por último mostramos dos algoritmos de parsing. Uno para el cálculo en DN, que es único completo que conocemos y que genera sólo formas normales, y otra para el CL, que también es completo y libre de ambigüedad espuri