Investigations on categorial grammars: Parsing algorithms and equivalence of formalisms

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 thereAnother 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 CG⪯ 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.168 p