Matching problem and parsing problem for abstract categorial grammars
Problèmes de filtrage et problème d'analyse pour les grammaires catégorielles abstraites
Résumé
This thesis presents detailed results about complexity of parsing in abstract catégorial grammars and parsing algorithms for those grammars. Abstract categorial grammars were introduced by Philippe de groote as a framework for modeling naturallanguage and the connections between its dimensions. Abstract categorial grammars are based on linear logic and linear lambda-calculus. An important part of this work is dedicated to the study of matching in the linear lambda-calculus. Most of the ideas involved in the design of the parsing algorithms we present corne from that study. Furthermore, this study allows to extend the formalism so that it fits better to its goals.
Ce travail de thèse contient une étude détaillée de la complexité de l'analyse des grammaires catégorielles abstraites et il présente des algorithmes d'analyse pour ce formalisme. Les grammaires catégorielles abstraites ont été introduites par Philippe de Groote comme un cadre formel pour l'étude du langage et des liens entre ces diverses dimensions. Les grammaires catégorielles abstraites utilisent comme bases formelles la logique linéaire et le lambda-calcul linéaire. Une partie substantielle de ce travail est consacrée à l'étude du filtrage dans le lambda-calcul linéaire; la conception des algorithmes d'analyse proposés est issue pour une bonne part de cette étude qui de plus permet d'envisager une extension du formalisme afin qu'il réponde au mieux à ses ambitions.