Offre de thèse
Algorithmes d'analyse syntaxique pour les grammaires catégorielles abstraites
Date limite de candidature
12-05-2024
Date de début de contrat
01-10-2024
Directeur de thèse
DE GROOTE Philippe
Encadrement
Encadrement sur base de réunions hebdomadaires.
Type de contrat
école doctorale
équipe
SEMMAGRAMMEcontexte
Les grammaires catégorielles abstraites (ACG) sont un formalisme grammatical dédié à la description de la syntaxe et de la sémantique des langues naturelles (de Groote, 2001). Leur définition est basée sur un petit ensemble de primitives mathématiques issues de la théorie des types et de la théorie de la démonstration. Techniquement, une ACG est composée de deux signatures linéaires d'ordre supérieur et d'un morphisme d'interprétation d'une signature dans l'autre. Le problème de l'analyse re- vient alors à inverser ce morphisme. Dans le cas général, la décidabilité de ce problème est ouverte. Elle est en fait équivalente à la décidabilité du fragment multiplicatif, exponentiel de la logique linéaire. Au second-ordre, en revanche, le problème est polynomial. Kanazawa (2007, 2017) montre comment toute ACG du second ordre peut être compi- lée sous la forme d'un programme Datalog, réduisant le problème de l'analyse syntaxique à une résolution de requête. En généralisant la réduction de Kanazawa au delà du second ordre, il est possible de réduire le problème de l'analyse pour les ACG d'ordre supérieur à un problème de recherche de démonstrations en logique linéaire multiplicative exponentielle (de Groote, 2015).spécialité
Informatiquelaboratoire
LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Mots clés
Grammaires formelles, Analyse syntaxique, Démonstration automatique, Logique linéaire, Théorie des types
Détail de l'offre
Le but de la thèse est de concevoir et de développer des algorithmes d'analyse syntaxique pour les grammaires catégorielles abstraites d'ordre supérieur, en réduisant le problème de l'analyse à un problème de recherche de démonstrations en logique linéaire multiplicative exponentielle.
Keywords
Formal grammars, Parsing, Automated deduction , Linear logic, Type theory
Subject details
The goal of the thesis is to design and develop parsing algorithms for higher-order abstract categorial grammars by reducing the parsing problem to a proof search problem in the exponential multiplicative fragment of linear logic.
Profil du candidat
Bac + 5 (Master ou équivalent) en informatique.
Une connaissance du lambda-calcul et une pratique de la programmation fonctionnelle.
Candidate profile
Master in computer science or equivalent.
Good knowledge of lambda-calculus and experience with functional programming.
Référence biblio
de Groote, P. (2001). Towards Abstract Categorial Grammars. In Association for Computational Linguistics, 39th Annual Meeting and 10th Conference of the European Chapter, Proceedings of the Conference, pp. 148–155.
de Groote, P. (2015). Abstract categorial parsing as linear logic programming. In M. Kuhlmann, M. Kanazawa, and G. M. Kobele (Eds.), Proceedings of the 14th Meeting on the Mathematics of Language (MoL 2015), Chicago, USA, pp. 15–25. Association for Computational Linguistics.
Kanazawa, M. (2007). Parsing and Generation as Datalog Queries. In J. Carroll, A. van den Bosch, and A. Zaenen (Eds.), Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics, pp. 176–183. Association for Computational Linguistics.
Kanazawa, M. (2017). Parsing and generation as datalog query evaluation. IfCoLog Journal of Logics and their Applications 4(4), 1103–1211.