Abstract

This work is the outcome of a research in the use of Categorial Grammars (CG) for the description and parsing of natural and formal languages.

Our work has focused on those aspects we found problematic facing the practical application of CG, such as: (a) a strong equivalence of Context Free Grammars (CFG) and CG, (b) lack of descriptive power of CG, (c) the existence of multiple systems of semantic labelling for the Lambek Calculus (LC) and thus, lack of precise definition for the spurious ambiguity, (d) efficiency and robustness of parsing algorithms.

We start dealing with the possible use of LC in CFG, and we conclude that this is possible. This is proved by the introduction of one algebraic model and the derivation of the LC there.

Another way of looking at the above results is to think we have built another CG theory by the addition of axioms to the LC. We call [special characters omitted] to this system, and it results in one unified theory for CFG and CG.

Next, we discuss the implications of using LC in CFG, as well as its advantages and disadvantages.

With respect to the existence of multiple systems of labelling for the LC, we introduce two versions for the calculus in Natural Deduction (ND) for CG. Using one of these variants is how we demostrate the Inversion Principle and the Curry-Howard isomorphism for the ND calculus. Then, we introduce two new conversion algorithms between the proofs in LC and the deductions in ND and thus, we get one semantic labelling in LC. We propose this labelling as the definition of equality in proofs and, therefore, as the definition of spurious ambiguity.

Finally, we introduce two different parsing algorithms: one for the calculus in ND—the only one we know to be complete and which generates only deductions in normal forms—and another one for the LC—being also complete and free of spurious ambiguity.

This second algorithm is specially interesting as it owns some top-down steps. Then, we discuss the possibility of using it as the kernel of an abductive semi-robust parser; abductive in the sense of Kakas and Kowalski.

Alternate abstract:

Este trabajo es el resultado de una investigación en el uso de Gramáticas Categoriales (CG) para la descripción y análisis de lenguajes naturales y formales.

Nuestro trabajo se ha centrado en aquellos aspectos que encontramos problemáticos frente a la aplicación práctica de GC, tales como: (a) una fuerte equivalencia de las gramáticas libres de contexto (CFG) y GC, (b) la falta de poder descriptivo de GC, (c) el existencia de múltiples sistemas de etiquetado semántico para Lambek Calculus (LC) y, por lo tanto, falta de definición precisa para la ambigüedad espuria, (d) eficiencia y robustez de los algoritmos de análisis.

Comenzamos a tratar el posible uso de LC en CFG y concluimos que esto es posible. Esto se prueba con la introducción de un modelo algebraico y la derivación de la LC allí.

Otra forma de ver los resultados anteriores es pensar que hemos construido otra teoría CG mediante la adición de axiomas a la LC. Llamamos [caracteres especiales omitidos] a este sistema, y da como resultado una teoría unificada para CFG y CG.

A continuación, discutimos las implicaciones del uso de LC en CFG, así como sus ventajas y desventajas.

Con respecto a la existencia de múltiples sistemas de etiquetado para la LC, presentamos dos versiones para el cálculo en Deducción Natural (ND) para CG. Usando una de estas variantes es como demostramos el Principio de Inversión y el isomorfismo de Curry-Howard para el cálculo ND. Luego, introducimos dos nuevos algoritmos de conversión entre las pruebas en LC y las deducciones en ND y así, obtenemos un etiquetado semántico en LC. Proponemos este etiquetado como definición de igualdad en las demostraciones y, por tanto, como definición de ambigüedad espuria.

Finalmente, presentamos dos algoritmos de análisis diferentes: uno para el cálculo en ND, el único que sabemos que está completo y que genera solo deducciones en formas normales, y otro para el LC, también completo y libre de ambigüedad espuria.

Este segundo algoritmo es especialmente interesante ya que posee algunos pasos de arriba hacia abajo. Luego, discutimos la posibilidad de usarlo como núcleo de un analizador sintáctico semirrobusto abductivo; abductivo en el sentido de Kakas y Kowalski.