L'objet de ce travail est la modélisation informatique de la capacité d'apprentissage de la syntaxe de leur langue naturelle par les enfants. Une synthèse des connaissances psycho-linguistiques sur la question est donc tout d'abord proposée. Le point de vue adopté pour la modélisation accorde une place privilégiée à la sémantique, qui est supposée acquise avant la syntaxe. Le Principe de compositionnalité, éventuellement adapté, est mis à contribution pour formaliser les liens entre syntaxe et sémantique, et le modèle d'apprentissage ''à la limite'' par exemples positifs de Gold est choisi pour régir les conditions de l'apprentissage. Nous présentons dans ce contexte divers résultats d'apprenabilité de classes de grammaires catégorielles à partir de divers types de données qui véhiculent des informations sémantiques. Nous montrons que, dans tous les cas, la sémantique contribue à spécifier les structures sous-jacentes aux énoncés, et à réduire ainsi l'espace de recherche des algorithmes d'apprentissage.

L'étude de la relation entre syntaxe et sémantique qu'établissent les grammaires de types<br />logiques a essentiellement privilégié le sens de l'analyse - syntaxe vers sémantique. Cette thèse souligne le profit que la génération - sémantique vers syntaxe - tire de l'étroitesse de cette relation.<br /><br />Elle s'appuie sur l'étude logique de ces modèles grammaticaux et met en avant l'utilisation de la logique linéaire et de ses réseaux de preuve. Autour du calcul de Lambek, un fragment intuitionniste de la logique linéaire non commutative, nous étudions le comportement des extensions de ce calcul en tant que modèles syntaxiques, notamment avec le calcul ordonné. Nous montrons par exemple qu'un fragment de ce dernier permet d'engendrer la même classe de langage que les grammaires d'arbres adjoints.<br /><br />D'autre part, l'adéquation de la syntaxe, portée par la notion de preuve, à la sémantique de Montague, portée par la notion de lambda-terme, s'illustre dans la correspondance de Curry-Howard. L'utilisation des réseaux de preuve nous permet de montrer que, pour le calcul de Lambek et pour des représentations sémantiques linéaires avec une constante au moins, le problème de génération est décidable et que ces grammaires sont intrinsèquement réversibles. Nous caractérisons les formes sémantiques permettant une réalisation syntaxique polynomiale. Aussi pouvons-nous proposer une méthode complète de génération dans ce cadre.<br /><br />Ces résultats, de même que l'implémentation dont ils ont fait l'objet, exploitent la théorie de la démonstration sous-jacente et en particulier les réseaux de preuve sous forme de graphes. Nous obtenons ainsi un cadre uniforme pour l'analyse et la génération. Pour le conserver, dans l'optique d'une prise en compte sémantique de termes non linéaires grâce aux connecteurs exponentiels de la logique linéaire, nous donnons une nouvelle syntaxe et un nouveau critère de correction pour les réseaux avec exponentiels sous forme de graphes.

Cette thèse explore l'usage des Grammaires Categorielles Abstraites (CGA) pour la Génération Automatique de Texte (GAT) dans un contexte industriel. Les systèmes GAT basés sur des théories linguistiques ont un long historique, cependant ils sont relativement peu utilisés en industrie, qui préfère les approches plus "pragmatiques", le plus souvent pour des raisons de simplicité et de performance. Cette étude montre que les avancées récentes en linguistique computationnelle permettent de concilier le besoin de rigueur théorique avec le besoin de performance, en utilisant CGA pour construire les principaux modules d'un système GAT de qualité industrielle ayant des performances comparables aux méthodes habituellement utilisées en industrie. / This thesis explores the usage of Abstract Categorial Grammars (ACG) for Natural Language Generation (NLG) in an industrial context. While NLG system based on linguistic theories have a long history, they are not prominent in industry, which, for the sake of simplicity and efficiency, usually prefer more ``pragmatic" methods. This study shows that recent advances in computational linguistics allow to conciliate the requirements of soundness and efficiency, by using ACG to build the main elements of a production grade NLG framework (document planner and microplanner), with performance comparable to existing, less advanced methods used in industry

Les contributions majeures de cette thèse s'articulent autour des trois axes de base de la linguistique computationnelle, à savoir la logique, la linguistique et l'informatique. Nous proposons ainsi un nouveau système non-directionnel GLE permettant de simuler les opérations transformationnelles du Programme Minimaliste dans un cadre logique qui fait appel au raisonnement hypothétique de manière contrôlée. La pertinence de ce formalisme est soulignée en montrant sa capacité à prendre en charge des phénomènes linguistiques complexes, nécessitant un partage contraint de ressources, tels que le liage d'anaphores ou la résolution d'ellipse. En outre, nous présentons un atelier logique, nommé ICHARATE, destiné à la recherche et l'enseignement de la linguistique computationnelle. Cet outil est composé de bibliothèques pour l'assistant à la démonstration Coq, qui comprennent la formalisation de systèmes logiques avancés dédiés au traitement des langues naturelles, dont la logique multimodale.

L'inférence grammaticale désigne le problème qui consiste à découvrir les règles de formation des phrases d'un langage, c'est-à-dire une grammaire de celui-ci. Dans le modèle d'apprentissage de Gold, les exemples fournis sont constitués uniquement des phrases appartenant au langage. L'algorithme doit fournir une grammaire qui représente le langage énuméré. Les grammaires catégorielles sont l'un des nombreux formalismes existants pour représenter des langages. Kanazawa a montré que certaines sous-classes de ces grammaires sont apprenables, mais ses résultats ne sont pas applicables directement aux langues naturelles. Sur le plan théorique, nous proposons de généraliser les résultats de Kanazawa à différents types de grammaires. Les grammaires combinatoires générales sont un modèle flexible permettant de définir des systèmes grammaticaux à base de règles de réécriture. Nous démontrons dans ce cadre que certaines classes de langages sont apprenables. Dans un souci de généralité maximale, nos résultats sont exprimés sous forme de critères sur les règles des systèmes grammaticaux considérés. Ces résultats sont appliqués à plusieurs formalismes relativement adaptés à la représentation des langues naturelles. Nous abordons également le problème de la mise en œuvre de l'apprentissage sur des données réelles. En effet, les algorithmes existants capables d'apprendre des classes de langages intéressantes sont NP-complets. Afin de contourner cet obstacle, nous proposons un cadre d'apprentissage plus souple, l'apprentissage partiel : le contexte d'utilisation est modifié dans le but d'obtenir une complexité algorithmique plus réaliste. Nous testons cette approche sur des données de taille moyenne, et obtenons des résultats relativement encourageants.

Ce travail de thèse vise à proposer les analyses formelles de phénomènes langagiers, tels que le système casuel, le double cas, la flexibilité de l'ordre des mots, la coordination, la subordination et la thématisation, dans deux langues structurellement très distinctes : le coréen et le français. Le choix théorique s'est porté sur le formalisme de la Grammaire Catégorielle Combinatoire Applicative, développée par Jean-Pierre Desclés et Ismail Biskri, en mettant en œuvre les combinateurs de la Logique Combinatoire de Curry et le calcul fonctionnel des types de Church. Le problème à résoudre est le suivant : en prenant une langue « à cas » comme le coréen, avec les constructions « à double cas » et la flexibilité dans l'ordre des mots, spécifiques à certaines langues extrêmes orientales, cette langue est-elle analysable avec un formalisme catégoriel et selon quelle stratégie de calcul ? Nous donnons un certain nombre d'exemples qui répondent à cette question. Les analyses formelles proposées dans ce travail permettent ensuite d'examiner la pertinence syntaxique de l'hypothèse « anti-anti relativiste » en dégageant certains invariants syntaxiques à partir des opérations de prédication, de détermination, de transposition, de quantification et de coordination. Nous proposons également un analyseur catégoriel, ACCG, applicable au coréen et au français, qui permet d'engendrer, de façon automatique, les calculs catégoriels, ainsi que les structures opérateur/opérande. / This dissertation aims at proposing the formal analysis of the linguistic phenomena, such as the case system, the double case, the flexible word order, the coordination, the subordination and the thematisation, in the two structurally distinct languages: Korean and French. The formalism of Applicative Combinatory Categorial Grammar, developed by Jean-Pierre Desclés and Ismail Biskri, allow us to analyze these problems by means of the combinators of the Combinatory Logic of Curry and the functional calculus of the Church's types. By taking account of these formal analysis applied to Korean and to French, we discuss on the « anti-anti relativist » hypothesis by finding some syntactic invariants from the different operations such as the predication, the determination, the quantification, the transposition and the coordination. We propose also a categorial parser, ACCG, applicable to Korean and French sentences, which generates automatically categorial calculus and the operator-operand structures.

Cette thèse s'intéresse à la modélisation de la syntaxe et de l'interface syntaxe-sémantique de la phrase, et explore la possibilité de contrôler au niveau des structures de dérivation la surgénération que produit le traitement des dépendances à distance par des types d'ordre supérieur. À cet effet, nous étudions la possibilité d'étendre le système de typage des Grammaires Catégorielles Abstraites avec les constructions de la somme disjointe, du produit cartésien et du produit dépendant, permettant d'étiqueter les catégories syntaxiques par des structures de traits. Nous prouvons dans un premier temps que le calcul résultant de cette extension bénéficie des propriétés de confluence et de normalisation, permettant d'identifier les termes beta-équivalents dans le formalisme grammatical. Nous réduisons de plus le même problème pour la beta-eta-équivalence à un ensemble d'hypothèse de départ. Dans un second temps, nous montrons comment cette introduction de structures de traits peut être appliquée au contrôle des dépendances à distances, à travers les exemples des contraintes de cas, des îlots d'extraction pour les mouvements explicites et implicites, et des extractions interrogatives multiples, et nous discutons de la pertinence de placer ces contrôles sur les structures de dérivation / This thesis focuses on the modelisation of syntax and syntax-semantics interface of sentences, and investigate how the control of the surgeneration caused by the treatment of linguistics movements with higher order types can take place at the level of derivation structures. For this purpose, we look at the possibility to extend the type system of Abstract Categorial Grammars with the constructions of disjoint sum, cartesian product and dependent product, which enable syntactic categories to be labeled by feature structures. At first, we demonstrate that the calculus associated with this extension enjoy the properties of confluence and normalization, by which beta-equivalence can be computed in the grammatical formalism. We also reduce the same problem for beta-eta-equivalence to a few hypothesis. Then, we show how this feature structures can be used to control linguistics movements, through the examples of case constraints, extraction islands for overt and covert movements and multiples interrogative extractions, and we discuss the relevancy of operating these controls on the derivation structures

Ces travaux s’intéressent à la modélisation formelle de la sémantique des langues naturelles. Pour cela, nous suivons le principe de compositionnalité qui veut que le sens d’une expression complexe soit une fonction du sens de ses parties. Ces fonctions sont généralement formalisées à l’aide du [lambda]-calcul. Cependant, ce principe est remis en cause par certains usages de la langue, comme les pronoms anaphoriques ou les présuppositions. Ceci oblige à soit abandonner la compositionalité, soit modifier les structures du sens. Dans le premier cas, le sens n’est alors plus obtenu par un calcul qui correspond à des fonctions mathématiques, mais par un calcul dépendant du contexte, ce qui le rapproche des langages de programmation qui manipulent leur contexte avec des effets de bord. Dans le deuxième cas, lorsque les structures de sens sont ajustées, les nouveaux sens ont tendance à avoir une structure de monade. Ces dernières sont elles-mêmes largement utilisées en programmation fonctionnelle pour coder des effets de bord, que nous retrouvons à nouveau. Par ailleurs, s’il est souvent possible de proposer le traitement d’un unique phénomène, composer plusieurs traitements s’avère être une tâche complexe. Nos travaux proposent d’utiliser les résultats récents autour des langages de programmation pour parvenir à combiner ces modélisations par les effets de bord. Pour cela, nous étendons le [lambda]-calcul avec une monade qui implémente les effects et les handlers, une technique récente dans l’étude des effets de bord. Dans la première partie de la thèse, nous démontrons les propriétés fondamentales de ce calcul (préservation de type, confluence et terminaison). Dans la seconde partie, nous montrons comment utiliser le calcul pour le traitement de plusieurs phénomènes linguistiques : deixis, quantification, implicature conventionnelle, anaphore et présupposition. Enfin, nous construisons une unique grammaire qui gère ces phénomènes et leurs interactions. / In formal semantics, researchers assign meanings to sentences of a natural language. This work is guided by the principle of compositionality: the meaning of an expression is a function of the meanings of its parts. These functions are often formalized using the [lambda]-calculus. However, there are areas of language which challenge the notion of compositionality, e.g. anaphoric pronouns or presupposition triggers. These force researchers to either abandon compositionality or adjust the structure of meanings. In the first case, meanings are derived by processes that no longer correspond to pure mathematical functions but rather to context-sensitive procedures, much like the functions of a programming language that manipulate their context with side effects. In the second case, when the structure of meanings is adjusted, the new meanings tend to be instances of the same mathematical structure, the monad. Monads themselves being widely used in functional programming to encode side effects, the common theme that emerges in both approaches is the introduction of side effects. Furthermore, different problems in semantics lead to different theories which are challenging to unite. Our thesis claims that by looking at these theories as theories of side effects, we can reuse results from programming language research to combine them.This thesis extends [lambda]-calculus with a monad of computations. The monad implements effects and handlers, a recent technique in the study of programming language side effects. In the first part of the thesis, we prove some of the fundamental properties of this calculus: subject reduction, confluence and termination. Then in the second part, we demonstrate how to use the calculus to implement treatments of several linguistic phenomena: deixis, quantification, conventional implicature, anaphora and presupposition. In the end, we build a grammar that features all of these phenomena and their interactions.

La linguistique informatique a pour objet de construire un modèle formel des connaissances linguistiques, et d’en tirer des algorithmes permettant le traitement automatique des langues. Pour ce faire, elle s’appuie fréquemment sur des grammaires dites génératives, construisant des phrases valides par l’application successive de règles de réécriture. Une approche alternative, basée sur la théorie des modèles, vise à décrire la grammaticalité comme une conjonction de contraintes de bonne formation, en s’appuyant sur des liens profonds entre logique et automates pour produire des analyseurs efficaces. Notre travail se situe dans ce dernier cadre. En s’appuyant sur plusieurs résultats existants en informatique théorique, nous proposons un outil de modélisation linguistique expressif, conçu pour faciliter l’ingénierie grammaticale. Celui-ci considère dans un premier temps la structure abstraite des énoncés, et fournit un langage logique s’appuyant sur les propriétés lexicales des mots pour caractériser avec concision l’ensemble des phrases grammaticalement correctes. Puis, dans un second temps, le lien entre ces structures abstraites et leurs représentations concrètes (en syntaxe et en sémantique) est établi par le biais de règles de linéarisation qui exploitent la logique et le lambda-calcul. Par suite, afin de valider cette approche, nous proposons un ensemble de modélisations portant sur des phénomènes linguistiques divers, avec un intérêt particulier pour le traitement des langages présentant des phénomènes d’ordre libre (c’est-à-dire qui autorisent la permutation de certains mots ou groupes de mots dans une phrase sans affecter sa signification), ainsi que pour leur complexité algorithmique. / The goal of computational linguistics is to provide a formal account linguistical knowledge, and to produce algorithmic tools for natural languageprocessing. Often, this is done in a so-called generative framework, where grammars describe sets of valid sentences by iteratively applying some set of rewrite rules. Another approach, based on model theory, describes instead grammaticality as a set of well-formedness logical constraints, relying on deep links between logic and automata in order to produce efficient parsers. This thesis favors the latter approach. Making use of several existing results in theoretical computer science, we propose a tool for linguistical description that is both expressive and designed to facilitate grammar engineering. It first tackles the abstract structure of sentences, providing a logical language based on lexical properties of words in order to concisely describe the set of grammaticaly valid sentences. It then draws the link between these abstract structures and their representations (both in syntax and semantics), through the use of linearization rules that rely on logic and lambda-calculus. Then in order to validate this proposal, we use it to model various linguistic phenomenas, ending with a specific focus on languages that include free word order phenomenas (that is, sentences which allow the free reordering of some of their words or syntagmas while keeping their meaning), and on their algorithmic complexity.

Les travaux de cette thèse se situent dans le cadre de la linguistique computationnelle. La problématique est de définir une interface syntaxe / sémantique basée sur les théories de la grammaire générative.<br />Une première partie, concernant le problème de l'analyse syntaxique, présente tout d'abord, la syntaxe générative, puis un formalisme la réalisant: les grammaires minimalistes de Stabler. <br />À partir de ces grammaires, nous réalisons une étude sur les propriétés de l'opération de fusion pour laquelle nous définissons des notions d'équivalence, ainsi qu'une modélisation abstraite des lexiques.<br />Une seconde partie revient sur le problème de l'interface. Pour cela, nous proposons un formalisme de type logique, basé sur la logique mixte (possédant des connecteurs commutatifs et non-commutatifs), qui équivaut, sous certaines conditions, aux grammaires de Stabler. <br />Dans ce but, nous introduisons une normalisation des preuves de cette logique, normalisation permettant de vérifier la propriété de la sous-formule. Ces propriétés sont également étendues au calcul de Lambek avec produit.<br />À partir de l'isomorphisme de Curry-Howard, nous synchronisons un calcul sémantique avec les preuves réalisant l'analyse syntaxique. Les termes de notre calcul font appel aux propriétés du lambda mu-calcul, ainsi qu'à celles de la DRT (Discourse Representative Theory).<br />Une dernière partie applique ces formalismes à des cas concrets. Nous établissons des fragments d'une grammaire du français autour du problème des clitiques.