Logique de ressources et réseaux syntaxiques
Contents
1. o dp modules le module est d duit du type par dualit il faut en effet bien noter que le calcul ordonn est bas sur un calcul unilat re c est dire o toutes les formules sont en partie droite ainsi un type A o B devient par dualit A B donnons par exemple le module enti rement d ploy associ l expression lit V d d Ze p p BA af WEE Le ER 1 lit vt SE N eeh Le Ae RK Ba qui pourra se noter lin airement H lit amp EL lt dp vp 21 amp dp lt vpl2 s1 Dans cet exemple pour des raisons de lisibilit nous donnons chaque pas de d rivation du r seau final partir des types il faut alors bien penser que la v rification de la bonne formation absence de cycle alternant se fait toujours sur les modules obtenus par dualit branchements ici seulement par axiomes pas 1 en gras les nouveaux liens introduits chaque tape en italique ce qui en r sulte chaque tape d 2 un n 1 livre d 2 lt n 1 o dp un lt livre pas 2 B it vV 3 lt dp 5 o vp 4 lit lt un lt livre dp lt vp 4 o s d 2 un n 1 livre d 2 lt n 1 o dp 5 un lt livre pas 3 dp 6 pierre l lit v 3 lt dp 5 o vp 4 lit lt un lt livre dp 6 lt vp 4 o s pierre lt lit lt un lt livre d 2 un n 1 livre d 2 lt n 12. 1996b Le calcul de Lambek et les r seaux de preuve TAL vol 37 n 2 num ro sp cial sur Grammaire et Th orie de la Preuve Retor C 1997 Pomset logic a non commutative extension of classical linear logic in J R Hindley et P de Groote eds TLCA 97 LNCS vol 1210 Springer Verlag Roorda D 1991 Resource Logics proof theoretical investigations PhD thesis Universit d Amsterdam Stabler E 1996 Acquiring and Parsing Languages with Movement Stabler E 1997 Derivational Minimalism para tre dans Actes du Colloque LACL 96 Nancy septembre 1996 Steedman M 1996 Surface Structure and Interpretation MIT Press ACTES DE TALN 97 16 GRENOBLE 12 13 JUIN 1997
3. finition 10 les r seaux ordonn s sont les pr r seaux satisfaisant e non absence de circuit alternant l mentaire e SAT entre deux points quelconques il existe toujours un chemin Le calcul ainsi obtenu poss de un certain nombre de propri t s remarquables dont la pr servation de l invariant non par suppression du lien coupure 3 6 Elimination du lien coupure dans les r seaux ordonn s Le r sultat est le m me qu au 3 3 en rajoutant un troisi me pas pour le cas e F est une formule en pr c de A lt B et FL est sa formule duale A lt B Quelques complications non abord es ici cf Retor 1997 apparaissent pour les r seaux dot s en plus d un ordre partiel sur les conclusions arcs R entre conclusions et coupures 3 7 Int r t des r seaux de preuves L int r t des r seaux de preuve est multiple ils permettent de r soudre le probl me souvent d sign comme celui des ambigu t s superflues dans les grammaires cat gorielles c est dire l existence de nombreuses d ductions formellement diff rentes mais non s mantiquement diff rentes et de ce fait ouvrent des perspectives nouvelles la th orie de l analyse syntaxique Lecomte 1993 ils fournissent un crit re g om trique simple pour tester la validit d une preuve ils donnent une g n ralisation de la notion de terme il est en effet toujours possible de calculer le terme de la preuve directement partir
4. une interpr tation en termes d alg bre de processus 1 Introduction Deux notions en rapport avec la logique jouent aujourd hui un r le central dans les th ories linguistiques celle de ressource et celle de d rivation Dans cet article nous allons revenir sur l importance de ces notions et montrer une mani re de les traiter dans un cadre logique d riv de la logique lin aire J Y Girard 1987 1995 2 Motivation pour un cadre d rivationnel et sensible aux ressources Curieuse volution que celle de la th orie syntaxique aujourd hui partie d une conception g n rative accordant une place importante la notion de r gle syntagmatique en opposition par exemple aux r gles de r duction des grammaires cat gorielles elle a gliss peu peu vers une th orie des arbres admissibles que l on trouve aussi bien dans GPSG Gazdar et al 1985 que dans le module X barre de la th orie chomskyenne pour aboutir une conception radicalement diff rente pr sente chez N Chomsky derni re mani re Chomsky 1996 mais aussi chez des auteurs comme M Steedman Steedman 1996 M Johnson Johnson 1997 ou E Stabler Stabler 1996 conception selon laquelle il n est pas d autre repr sentation de la structure d une phrase que la pure et simple preuve de sa correction De nombreux auteurs dont Berwick amp Epstein 1996 Stabler 1996 ont alors not la convergence dans l volution entre la th orie syntaxique chomskyenne e
5. consid rons qu tout item lexical correspond un r seau de preuve partielle c est dire un pr r seau v rifiant le crit re d absence de circuit altern mais avec certaines feuilles non reli es par un lien axiome d autres feuilles que nous appelons donc hypoth ses De tels r seaux partiels sont aussi appel s modules Il existe deux mani re de brancher ensemble deux modules e soit par des liens axiomes des hypoth ses appartenant aux deux modules diff rents sont reli es par lien axiome e soit par coupure limination de la coupure deux conclusions duales l une de l autre appartenant chacune un module diff rent sont reli es par un lien coupure puis ce lien est supprim en appliquant l algorithme d limination de la coupure 4 3 Exemples Exemple 1 grammaires cat gorielles de type AB ou grammaires minimalistes avec seulement op ration Merge 3 Pierre lit un livre types nous appelons type d une expression une formule de logique lin aire ordonn e associ e cette expression qui en donne la cat gorie et le mode d emploi des liens axiomes ACTES DE TALN 97 7 GRENOBLE 12 13 JUIN 1997 d j introduits c est en ceci qu il s agit d une preuve partielle ici marqu s par des indices entiers de sorte que deux atomes reli s par un lien axiome aient le m me indice dp pierre OE lit VII lt dp o vpl2 dp lt vpl21 o s d un 1 livre d lt n 1
6. les suivantes exprim es sous forme d un calcul des s quents bilat re T A BAL C TI A I l B asi E T A B Al C T I l A B TI A Kb A l C ALR E g 0 nr d 0 I A oB AIC T l A o B ACTES DE TALN 97 2 GRENOBLE 12 13 JUIN 1997 auxquelles nous ajoutons les r gles d identit axiome A l A et r gle de coupure transitivit ainsi que pour seule r gle structurelle la r gle d change pas de r gle de contraction ni d affaiblissement donc Il est bien connu van Benthem 1986 que si nous d corons ces r gles avec des lambda termes typ s nous pouvons associer toute preuve un lambda terme qui est en quelque sorte la mat rialisation de l objet preuve Cette association se fait selon l isomorphisme de Curry Howard entre types et propositions termes et d ductions la r gle g o tant associ e l op ration d application la r gle d o l abstraction les r gles pour au couplage syst me mais sans d o est utilis par Dalrymple Pereira et al Dalrymple et al 1993 dans leur d finition de la projection s mantique d une f structure en LFG Il est facile de montrer se reporter par exemple Retor 1996b qu on peut le plonger dans un calcul classique unilat re MLL logique lin aire multiplicative bas sur les deux connecteurs multiplicatifs et 9 condition d introduire une n gation telle que l on ait Al L A A OB A1 BL AGB At B une for
7. sont d finis partir de T A et de T B par UN Ge YY NE T A B A B f T A B APB D finition 6 un pr r seau de conclusions T est constitu par la famille des arbres R amp B des formules de I et par un ensemble d ar tes R disjointes reliant des feuilles deux deux orthogonales de sorte que toute feuille soit atteinte exactement une fois D finition 7 un r seau est un pr r seau satisfaisant e non absence de cycle alternant l mentaire e SAT entre deux points quelconques il existe toujours un chemin On peut alors d montrer Th or me 1 un s quent S de MLL est prouvable si et seulement s il existe un r seau dont les conclusions sont les formules de S 3 3 limination du lien coupure Dans tout r seau poss dant des liens coupure il est possible d liminer ces derniers tout en gardant un r seau ayant les m mes conclusions partir de deux pas l mentaires si F et FL sont deux formules reli es par coupure alors on peut avoir e Fest un atome et donc F1 l atome n gatif ol e Fest une formule en AQB et FL est sa formule duale AL B4 Le deuxi me pas se repr sente par ACTES DE TALN 97 4 GRENOBLE 12 13 JUIN 1997 NZ YY Y Y K Ato B EE E Des se r duit et le premier se r duit A D finition 8 un r seau est dit intuitionniste si et seulement si chaque conclusion re oit une polarit et une seule conclusion est po
8. tude et de coh rence Dans un cadre strictement cat goriel enfin il faut noter que M Steedman Steedman 1996 donne une version de la plupart des modules de la th orie chomskyenne du genre GB sans postuler de niveaux de repr sentation interm diaires en particulier donc sans d placements ni cat gories vides L nous semble tre l apport essentiel de l approche dite d rivationnelle en tant qu oppos e repr sentationnelle l o cette derni re exige plusieurs niveaux de repr sentation avec des aller retours de l un l autre pour v rifier la bonne formation d un nonc la premi re tente de construire en un seul geste et la preuve de bonne formation et la repr sentation s mantique Elle r duit galement les vari t s d objets genre cat gories vides auxquels l analyse a recours Nous cherchons dans ce qui suit poser les bases d une formalisation de ces approches qui puisse devenir ensuite le point de d part une impl mentation rigoureuse des th ories syntaxiques Nous partirons donc de l expos du syst me le plus simple que nous puissions concevoir pour la d duction sensible aux ressources le syst me de la logique lin aire multiplicative et intuitionniste 3 D une logique sensible la quantit une logique galement sensible l ordre 3 1 Logique lin aire intuitionniste restreinte 0 Les r gles de LD o syst me not aussi LP pour Lambek permutationnel sont
9. v42 ace vHI voit amp v 21 lt dp acc vpH3 amp dp nom lt vp 31 sH le acct 1 le p acc 1 lt v 21 vL 3 lt dp acc VL 216 v 3 ace commentaire le verbe fournit la fois son entr e ordinaire et une conclusion suppl mentaire v v marqu e acc pour accusatif Le clitique contient la conclusion duale vt v avec la m me marque son autre conclusion exprimant apr s conversion en formule duale le fait qu il s agit d une marque accusative et que la s quence constitu e de cette marque ACTES DE TALN 97 9 GRENOBLE 12 13 JUIN 1997 suivie d un verbe fournit l quivalent d un verbe suivi par un compl ment nominal accusatif tiquet vide module clitique le d ploy J V yI Je Es 4 Y L Ess NW E eg Sg ac le Le be d e Je T module verbal avec une entr e clitique Ki Ca D One vo v Le e p voit v Sa ef EE SE el SG E Ze Le KP ei vil lei MV Fa es Let Goal branchements Pas 1 coupure accH 1 le o acc 1 lt v 21 v4 3 lt dp acc vH2 v 31 ace v 2 vl it ace v 21 voit amp v 31 lt dp acc vpH4 dp nom lt vp 4 st ACTES DE TALN 97 10 GRENOBLE 12 13 JUIN 1997 r seau dpi p pre ly ldap fdp V V sy pa ke y EINE RAE 9 C7 a ll TRE a nono sage P voit V Da ef KR Eet SN
10. 995 Joshi A amp Kulick S 1997 Partial Proof Trees Resource Sensitive Logics and Syntactic Constraints para tre dans Actes du Colloque LACL 96 Nancy septembre 1996 Laks B 1996 Langage et Cognition une approche connexionniste du langage Hermes Paris Lecomte A 1992 Proof Nets and Dependencies Actes de COLING 92 Nantes Lecomte A 1993 Towards Efficient Parsing via Proof Nets Actes de EACL Utrecht Lecomte A 1994 Mod les logiques en th orie linguistique m moire d habilitation Grenoble Lecomte A 1996 Grammaire et Th orie de la Preuve une introduction TAL vol 37 n 2 num ro sp cial sur Grammaire et Th orie de la Preuve Lecomte A amp Retor C 1995 Pomset logic as an alternative categorial grammar in Morrill G et Oehrle R eds Formal Grammar Proceedings of the ESSLLI Workshop on Formal Grammar Barcelone Lecomte A et Retor C 1997 Words as Modules a Lexicalized Grammar in the framework of Linear Logic Proof nets para tre dans Proceedings of ICML 96 John Benjamins Rambow O Vijay Shanker K Weir D 1995 D tree grammars 33rd Meeting of the ACL Retor C 1993 Calcul des S quents Ordonn s th se Paris VII Retor C 1996a Perfect matchings and series parallel graphs multiplicative proof nets as R amp B graphs in Girard J Y et al eds Linear 96 Electronic Notes in Computer Science vol 3 Retor C
11. E e e Bi Sens we Se e Vi ef aech ei le vc ES all J e mm 7 i d ki ar Sanh ES be Jr de Pas 2 limination de la coupure acc1 1 le amp acc 1 lt v 21 amp vL 3 le lt voit lt dpL acc O vt 2 voit v 3 lt dp acc vpL 41 p dp nom lt vp 41 s aech fle t WW F Tr Pas 3 lien axiome accH1 le p acc 1 lt v 21 vL 3 le lt voit lt dpL acc 5 vL 2 voit v 3 le lt voit lt dp acc 5 vpH4 le lt voit dp nom lt vp 4 s ACTES DE TALN 97 11 GRENOBLE 12 13 JUIN 1997 Pas 4 dp 6 nom pierre acc1 1 le g acc 1 lt v 2 v 3 le lt voit lt dp_ acc 5 vL 2 voit v 3 le lt voit lt dp acc 51 vpL 4 le lt voit 6 dp nom 6 lt vp 4 s pierre lt le lt voit Remarque 1 au cas o il n y a pas de clitique mais un compl ment r alis par un NP lexicalement plein v 1 et v 2 de l entr e verbale sont identifi es 2 ce qui conduit alors une analyse semblable celle de l exemple 1 Remarque 2 afin d viter certaines constructions impossibles comme 5 Pierre le croit que Marie lit au lieu de Pierre croit que Marie le lit c est dire la cliticisation sur un verbe d une phrase matrice on doit rajouter aux r seaux des contraintes non logiques donc sp cifiquement linguistiq
12. Logique de ressources et r seaux syntaxiques Alain Lecomte Christian Retor INRIA Lorraine amp U Grenoble 2 INRIA Lorraine amp CRIN CNRS B timent SHM B timent LORIA 1251 Avenue Centrale 615 rue du Jardin Botanique BP 47 BP 101 38040 Grenoble cedex 9 54602 Villers les Nancy cedex T l 33 0 4 82 78 52 T l 33 0 3 83 59 20 17 Fax 33 0 4 82 56 65 Fax 33 0 3 83 27 83 19 email lecomte upmf grenoble fr email retore loria fr http www loria fr retore index html R sum Le but de cet article est de d velopper un cadre logique commun pour exprimer des formalismes grammaticaux loign s en apparence comme les grammaires cat gorielles calcul de Lambek les grammaires d arbres adjoints les grammaires bas es sur gouvernement et liage et les grammaires minimalistes au sens de Chomsky et de Stabler Ce cadre est fourni par le calcul ordonn extension non commutative de la logique lin aire Un outil fondamental dans cette approche est fourni par la notion de r seau de preuve Au lieu d tre associ es des formules comme dans les variantes du calcul de Lambek et selon la th orie des types usuelle les expressions sont associ es des preuves partielles appel es aussi modules et le calcul donne les mani res de les composer On fabrique de mani re g n rale des grammaires de r seaux ces r seaux ayant du fait de la s mantique de la logique lin aire m me enrichie au connecteur pr c de
13. aire cat gorielle Ils appellent stretching le fait de faire appara tre dans une preuve partielle la possibilit d ins rer une autre preuve cela correspond exactement notre introduction de conclusions suppl mentaires afin de les relier par coupure l insertion m me de la preuve correspondant alors au branchement par coupure et son limination Ajoutons que notre syst me tant bas sur une logique des ordres partiels il permet d exprimer simplement la variabilit de l ordre des mots dans certaines langues le turc par exemple ou dans certaines constructions syntaxiques topicalisation Travailler avec des preuves partielles pr sente plusieurs int r ts par rapport l approche d ductive classique D abord sur le plan de l efficacit cela vite de refaire pour chaque analyse certaines suites de pas d ductifs qui sont ainsi compact es une bonne fois cela vite donc certains probl mes d ambigu t superflue spurious ambiguity propres aux grammaires cat gorielles Ensuite sur le plan th orique comme dans les TAGs il devient ais d exprimer les ph nom nes de liage en introduisant des liens de cor f rence dans les preuves partielles initiales et plus g n ralement d exprimer des relations distance arbitraire sous formes de ph nom nes locaux obtenant ce que A Joshi d finit comme un domaine de localit tendu EDL qui va de paire avec une mise en facteur de la r cursion dans le domaine des d pendanc
14. ans LX mel NP mm pm m w bi EE Wa D e E il vp i SE yt lit v K N aA KEE Wi E P attentivement ad SE v VL vt Fe LA e fw e e J La Le Set kd limination de la coupure Tc ACTES DE TALN 97 13 GRENOBLE 12 13 JUIN 1997 M aag vil 7 es D Nc vp I AOE RS V lt Se ef More J LA P La attentivement ad NN r h ror 5 Conclusion L approche logique pr sent e ici n est pas en soi une th orie linguistique il s agit de fournir un cadre formel qui peut permettre une expression ad quate de diverses th ories linguistiques contemporaines dont certains aspects de la th orie chomskyenne incluse dans le Programme Minimaliste 3 Elle rejoint des tentatives Joshi amp Kulick 1995 Abrusci Fouquer Vauzeilles 1996 pour jeter un pont entre des mod les base d arbres adjoints TAGs et le paradigme d rivationnel ou preuve comme calcul On peut ainsi rapprocher ce travail de celui de Abrusci Fouquer et Vauzeilles d sormais AFV Abrusci et al 1996 qui utilise la logique lin aire intuitionniste non commutative N LLI qui s obtient partir du syst me LLI 3 1 en supprimant la r gle d change 4 Abrusci et al prouvent que tout arbre d une grammaire TAG G peut tre repr sent e par un s quent prouvable de N ILL et que si on consid re dans N ILL la fermeture de ces s quents sous r gle de coupure et une r gle d riv e du syst me que les auteurs nommen
15. du r seau dans LLI et on peut d finir les r seaux dans des contextes o la notion de terme n est pas d finissable en logique classique par exemple et dans le pr sent calcul ordonn de ce fait ils permettent d tendre l isomorphisme de Curry Howard cf de Groote amp Retor 1996 3 7 tiquetage des r seaux ordonn s Dans le but de projeter l ordre induit par le connecteur pr c de qui correspond un ordre d valuation des formules sur l ordre des mots nous proc dons un tiquetage des r seaux les formules associ es aux ar tes B sont tiquet es par des multi ensembles de cha nes partiellement ordonn s selon les conventions suivantes e lien axiome deux conclusions A R et AR telles que RK e lien tenseur si la conclusion est tiquet e par l une des deux pr misses est tiquet e par l union de K et du multi ensemble K tiquetant l autre pr misse donc m me tiquette pour les deux pr misses si R e lien par si les pr misses sont tiquet es par R et R la conclusion est tiquet e par RUR ACTES DE TALN 97 6 GRENOBLE 12 13 JUIN 1997 e lien pr c de si les pr misses sont tiquet es par R et R la conclusion est tiquet e par R lt R e lien coupure comme le lien tenseur avec 9 tiquet 4 Calcul ordonn et TALN 4 1 R seaux ordonn s tiquet s pour l ordre des mots L application du calcul ordonn au traitement de la langue na
16. es Il serait possible de montrer galement que des formalismes d riv s des TAGs comme les D tree grammars de Rambow et al Rambow et al 1995 peuvent s exprimer dans notre formalisme D une mani re g n rale on gagne cet expression le fait de pouvoir caract riser les structures correctes par un crit re topologique extr mement simple absence de circuit altern De plus les r seaux ont une interpr tation computationnelle int ressante en termes de parall lisme qui permet d tablir un lien entre cette approche et une certaine variante du connexionnisme Lecomte 1994 Laks 1996 6 Bibliographie Abrusci M Fouquer C amp Vauzeilles J 1996 Tree Adjoining Grammars in Noncommutative Linear Logic in Actes du Colloque LACL 96 Nancy septembre 1996 Berwick amp Epstein 1996 On the Convergence Of Minimalist Syntax and Categorial Grammar Chomsky N 1981 Lectures on Government and Binding Foris Pub 5 D une mani re g n rale et ceci pour r pondre une remarque de l un des lecteurs anonymes de cet article c est un avantage des grammaires lexicalistes de pouvoir exprimer certains ph nom nes grammaticaux d une mani re beaucoup plus simple et ad quate que ne le font des grammaires faisant usage de r gles et de principes plus g n raux C est notablement le cas pour les ph nom nes de liage et en particulier pour les anaphores r flexifs et r ciproques De nombreux travaux Reinhar
17. est dire d utiliser des cat gories pour nous des modules qui servent uniquement l assemblage des modules lexicalement pleins De tels modules correspondent AGR T ou C c est dire aux cat gories fonctionnelles Nous pourrons alors faire en sorte que seules ces modules puissent introduire de l ordre 4 ce qui a pour effet de donner deux implications lin aires au lieu d une ici not es o et o cf 3 4 ACTES DE TALN 97 14 GRENOBLE 12 13 JUIN 1997 Vo V ADV ADV o attentivement V attentivement LN VPo V NP Vo V Vo lit lit NP VP VPo V NP Vo VOADV ADV o attentivement Vo lit lit attentivement NP VP qui correspond exactement l adjonction au sens de TAG 6c Comme on peut le constater notre traduction des TAGs diff re de celle de AFV en ce que dans cette derni re l adjonction se traduit en deux applications de la r gle de coupure restreinte aux atomes condens es dans la seule r gle dite d adjonction alors que dans la notre elle se traduit en une seule coupure mais entre des formules quelconques D autre part dans ADV les arbres sont traduits en s quents prouvables alors que dans notre approche ils le sont en preuves partielles A cause de ce dernier point notre syst me se rapprocherait plut t de celui de Joshi et Kulick Joshi amp Kulick 1995 1997 Dans ce dernier en effet les auteurs obtiennent l quivalent des TAGs en combinant des preuves partielles valides en gramm
18. mule F d signe alors la formule obtenue en transportant les symboles de n gation sur les atomes au moyen de ces identit s L implication lin aire o se d finit alors par A o B AL 9B Les r gles de ce calcul sont donn es par l T A B A LIA l I B l T AfB A LIA op avec toujours r gle d change axiome exprim par l A A et r gle de coupure On a un crit re pour reconna tre dans MLL les formules et les s quents qui sont les traductions possibles de formules et de s quents de LLI Les formules sont polaris es de telle sorte qu un atome n gatif soit de polarit n gative un atome positif de polarit positive aucune sous formule ne consiste prendre soit le tenseur de formules n gatives soit le par LO de deux formules positives les s quents de LLI sont alors ceux qui ont une et une seule formule positive Gr ce cela on peut appliquer directement la m thode des r seaux de preuve de la logique lin aire afin d obtenir des repr sentations g om triques des preuves effectuables dans le syst me 3 2 R seaux intuitionnistes Il existe plusieurs conceptions des r seaux intuitionnistes Girard 1987 Danos amp R gnier 1990 Roorda 1991 Lecomte 1992 Lamarche 1994 Nous retenons ici celle de C Retor Retor 1996a Retor 1996b car elle se g n ralise ensuite facilement au calcul ordonn D finition 1 un couplage est un sous ensemble de l ensemble des ar tes d u
19. n graphe tel que deux ar tes du couplage ne sont jamais adjacentes Un tel couplage est dit parfait lorsque tout sommet est incident une ar te du couplage D finition 2 un graphe R amp B est un graphe dont les ar tes sont soit de couleur B traits pleins soit de couleur R traits pointill s tels que les ar tes B constituent un couplage parfait du graphe Les ar tes B correspondent aux formules et les ar tes R aux connecteurs Dans ces graphes l identification de ceux qui correspondent des d monstrations se fera au moyen de la notion de chemin alternant l mentaire D finition 3 un chemin alternant l mentaire dans un graphe R amp B est un chemin dont les ar tes sont alternativement de couleur B et R et qui n emprunte pas deux fois la m me ar te ACTES DE TALN 97 3 GRENOBLE 12 13 JUIN 1997 Ce D finition 4 les pr r seaux sont des R amp B graphes obtenus partir de R amp B graphes l mentaires appel s liens axiome A il tenseur par coupure Lu 1 2 Let Dag Dag KE NB dans ce dernier lien coupure F et FL sont des conclusions le est une marque indiquant l occurrence de la r gle de coupure elle est en fait quivalente une formule du second ordre IX X X D finition 5 tant donn e une formule C son arbre R amp B des sous formules T C est un graphe R amp B d fini inductivement comme suit e si C Q est atomique alors T C est a T A B et T A B
20. o dp 5 un lt livre videmment la phrase en entr e est correctement analys e si et seulement si elle contient l ordre d termin par l analyse c est dire tiquetant la sortie s Ji Le r seau final est le suivant l Ces indices n ont videmment pas de valeur par eux m mes tout module obtenu partir d un module donn en changeant les valeurs des entiers lui resterait identique pourvu que les m mes atomes demeurent identifi s Ceci explique que nous pourrons proc der toute op ration de renommage des indices ACTES DE TALN 97 8 GRENOBLE 12 13 JUIN 1997 Teal ea A eee a wf un lt livre 4 SANA ell pl yp litcundlivre ET mi KC E ke Wi A kes SH pierre lt it lt un lt livre Ke E e pierre dp Ka Sg livre int S gg un d Ze Ga Exemple 2 Grammaires de type GB Cet exemple traitera des clitiques probl me que l on rencontre classiquement dans l analyse des langues romanes Chomsky 1981 fait l hypoth se que dans une phrase comme 4 4 Pierre le voit on a une D S structure du genre Pierre yp le voit np el ceci afin que le 6 r le d objet de voit soit assign puis transmis le Nous ne faisons appel ici aucune esp ce de cat gorie vide d o l inutilit que nous nous prononcions en faveur d une trace ou d un PRO n anmoins nous proposons une analyse voisine dans la mesure simplement o ce que Chomsky exprime par un lien probl matique entre
21. our rendre ces repr sentations acceptables ou non Ainsi le principe de coh rence impose t 1l que toutes les sous f structures correspondent bien un pr dicat qui les contr le et le principe de compl tude que toutes les fonctions contr l es par le pr dicat soient bien pr sentes dans la f structure Dalrymple et al 1995 enrichissent ce syst me de mani re pouvoir produire un autre niveau de repr sentation ou s structure qui correspond la repr sentation s mantique ou pourrait on dire par analogie avec la th orie chomskyenne repr sentation en forme logique Ils d finissent pour cel une projection de la f structure qui est une application traitant chaque composant de celle ci comme une ressource utilis e une et une seule fois Pour d finir cette projection on a besoin de transformer la f structure en une formule de logique lin aire combinant au moyen des connecteurs lin aires 0 des formules de logique des pr dicats d ordre sup rieur Une logique de ressources est alors ici utilis e comme langage d assemblage des significations M Johnson 1996 a tendu cet usage de la logique lin aire l architecture g n rale de LFG il en obtient une simplification notable Dans sa conception les r gles syntagmatiques engendrent une c structure tiquet e et l interpr tation s mantique provient directement de la preuve de la bonne formation du syst me des tiquettes qui est en m me temps preuve de compl
22. sitive 3 4 R seaux de Lambek On obtient le calcul de Lambek avec produit et s quence vide partir de LLI en supprimant la r gle d change cela a pour cons quence l clatement de o en deux instances qui sont orient es et qu on peut noter selon la tradition des grammaires cat gorielles et ainsi que la non commutativit de Les r seaux correspondants sont les r seaux intuitionnistes respectant en plus certaines conditions de planarit Roorda 1991 Lecomte 1992 Retor 1996b Nous ne nous tendrons pas davantage sur ces r seaux d sormais bien connus Indiquons seulement qu il s agit de r seaux rendant compte d une logique sensible non seulement la quantit de ressources disponibles mais aussi l ordre dans lequel elles sont donn es Toutefois cette logique traite de structures totalement ordonn es ce qui est excessif relativement aux applications linguistiques envisag es 3 5 R seaux ordonn s On peut reprendre le calcul classique MLL et ajouter un nouveau type de lien D finition 9 les pr r seaux ordonn s sont des R amp B graphes obtenus partir des liens de la D finition 4 du lien suivant le connecteur pr c de est not lt ACTES DE TALN 97 5 GRENOBLE 12 13 JUIN 1997 pr c de a A D BI BI A lt B f ainsi que d arcs orient s de type R entre conclusions Remarque dans ce qui suit nous ne ferons pas usage des arcs orient s entre conclusions D
23. t amp Reuland 1993 Pollard et Sag 1992 conduisent consid rer que le liage des r flexifs et des r ciproques tant un ph nom ne strictement local a une explication naturelle dans le fait qu il est sp cifi dans le lexique Baschung 1991 fait la m me observation propos du contr le des infinitives Il n en reste pas moins que dans d autres cas un maximum d information peut et doit tre factoris afin de ne pas r appara tre de fa on excessivement redondante dans les entr es lexicales C est le sens de nos travaux futurs voir aussi note 3 ACTES DE TALN 97 15 GRENOBLE 12 13 JUIN 1997 Chomsky N 1996 The Minimalist Program The MITPress Dalrymple M et al 1995 LFG Semantics in Proceedings of the ESSLLI Workshop on Formal Grammar Barcelone aout 1995 Gazdar G al 1985 Generalized Phrase Structure Grammar Blackwell de Groote P amp Retor C 1996 On the Semantic Reading of Proof Nets in Proceedings of the ESLLI Workshop on Formal Grammar Prague ao t 1996 Girard J Y 1987 Linear Logic TCS n 50 Girard J Y Lafont Y amp R gnier L 1995 Advances in Linear Logic LMS Johnson M 1997 LFG as a Resource Sensitive Grammar rapport de recherches RXRC Grenoble Joshi A amp Kulick S 1995 Partial Proof Trees as Building Blocks in a Categorial Grammar in Morrill G et Oehrle R eds Formal Grammar Proceedings of the ESSLLI Workshop Barcelone ao t 1
24. t les grammaires cat gorielles De fait l une des deux op rations que Chomsky nomme Transformations G n ralis es savoir Merge n est rien d autre que l application fonctionnelle propre aux grammaires cat gorielles les plus simples celles dites de Ajduckiewicz Bar Hillel Toutefois Chomsky introduit une autre TG Move dont le r le est de d placer un constituant lorsque se pr sente la n cessit de v rifier un type de trait Par exemple dans les langues SVO partir de l hypoth se du sujet interne au SV le sujet monte visiblement dans la structure afin de se mettre en position de ACTES DE TALN 97 1 GRENOBLE 12 13 JUIN 1997 v rification de ses traits d accord et de cas De m me le syntagme interrogatif dans les langues non in situ est attir par un trait fort port par le noeud COMP Dans toutes ces situations il est devenu fr quent de dire que les traits en question sont des ressources et que la d rivation est termin e lorsque toutes les ressources ont t consomm es ou ventuellement v rifi es C est donc l objectif de consommation des ressources qui guide la d rivation D autres cadres th oriques utilisent d sormais cette notion On citera en particulier LFG Dans les Grammaires Lexicales Fonctionnelles on construit partir de r gles syntagmatiques une c structure ou structure en constituants appari e avec une f structure ou structure fonctionnelle Des contraintes agissent p
25. t r gle d adjonction alors cette fermeture correspond la traduction dans N ILL de l ensemble des arbres obtenus par substitution et adjonction des arbres initiaux de G Leur r gle d adjonction est la suivante T1 a IV l a A ao a A l b A li Ar F5 A2 l b o 1 A est la paire issue de mani re unique de A telle que A l a et A a A2 l b Elle se d rive des r gles de N ILL en appliquant deux fois la r gle de coupure restreinte aux atomes Dans un s quent associ un arbre TAG la formule A o A appara t toujours pour indiquer que A est un noeud o l adjonction au sens TAG peut avoir lieu Ainsi par exemple les arbres 6a et 6b se traduisent respectivement par 8a VPo V NP Vo V Vo lit lit NP VP 8b Vo V OADV ADVo attentivement V attentivement V La r gle dite d adjonction permet de faire la d duction 3 Les formules que nous associons aux items lexicaux dans ce r sum sont assez na ves linguistiquement parlant ceci des fins d exposition Rien n emp che videmment d avoir des formules beaucoup plus proches des hypoth ses faites dans Chomsky 1996 En particulier il nous para t clair qu une th orie linguistique convenable doit viter le genre de redondance que l on a en introduisant des contraintes d ordre dans chaque entr e lexicale Les conditions d ordre doivent d couler de principes g n raux Pour cela il suffira de proc der la mani re de Stabler 1996 c
26. turelle se justifie particuli rement par le fait que dans la plupart des langues des propri t s sont exprim es partir de ph nom nes d ordre des mots ainsi par exemple de la distinction des fonctions grammaticales dans les langues configurationnelles D autre part des contraintes d ordre existent plus ou moins l ches qui conduisent consid rer qu une phrase est par elle m me un multi ensemble partiellement ordonn Par exemple en fran ais dans une relative sujet et verbe peuvent tre permut s mais ce n est pas le cas dans l absolu 1 a l homme que Marie aime b l homme qu aime Marie 2 a Marie aime un homme b Aime Marie un homme L application du calcul ordonn au traitement de la LN se fait donc de la mani re suivante l les propositions voire dans un syst me plus riche int grant des variables individuelles les pr dicats sont les cat gories syntaxiques usuelles qu on peut choisir selon ses pr f rences videmment c est dire d n pour d terminant et nom dp ou np pour le groupe nominal etc 2 les sous formules sont tiquet es par des ensembles partiellement ordonn s de formes phonologiques qui ne font qu enregistrer la structure de la preuve dans l ordre des mots de sorte qu en sortie du r seau on poss de un et un seul noeud de sortie not s qui re oit comme tiquette l ordre partiel des mots correct de la phrase analys e 4 2 Branchement de modules D sormais nous
27. ues Ces contraintes ne sont rien d autre que des crit res de minimalit condition sur les cycles clitique clitique ne passant pas par un lien axiome e si Lu qui sont dans la ligne de l volution actuelle des th ories linguistiques cf en particulier Chomsky 1996 Exemple 3 Grammaires de type LTAG Une Grammaire d Arbres Adjoints Lexicalis e est d finie partir de deux ensembles d arbres dits l mentaires les arbres initiaux et les arbres auxiliaires Ces arbres ont tous au moins une feuille tiquet e par un noeud terminal c est pour cette raison qu on les dit lexicalis s Un arbre auxiliaire poss de une feuille poss dant la m me tiquette que la racine et sert ainsi exprimer l op ration d adjonction Le langage engendr par une grammaire TAG G est la fermeture de l ensemble des arbres l mentaires sous deux op rations substitution et adjonction La substitution est bien connue et facile d finir on remplace un noeud tiquet par un non terminal et qui est sans descendant par un arbre dont la racine est tiquet e par le m me non terminal L adjonction consiste couper un arbre o a lieu l adjonction en un noeud N et ins rer entre les deux parties issues de cette d coupe un arbre auxiliaire f dont la racine est tiquet e N Exemple arbre initial o 6a arbre auxiliaire B 6b VP V V NP d ADV lit attentivement 2 Rappelons 3 2 que T est quivalent 3X X1 X ce q
28. ui fait qu une formule a at peut toujours tre consid r e comme une coupure entre a et a et l limination de la coupure dans ce cas pr cis revient faire dispara tre une telle conclusion ACTES DE TALN 97 12 GRENOBLE 12 13 JUIN 1997 L adjonction des deux arbres se fait selon qui donne 6c VP erc VP V NP Sc SC Se See E eeng D V lit attentivement lit attentivement On peut montrer qu en adoptant la traduction suivante traduction des arbres l mentaires d une grammaire G en r seaux de preuve partiels on obtient dans le calcul ordonn un ensemble de r seaux ferm sous branchement axiome et branchement coupure qui correspond l ensemble des arbres engendr s par G Les noeuds des arbres sont repr sent s par des liens axiomes le noeud vp par exemple par le lien axiome vp vpt Un noeud x o une adjonction peut avoir lieu est repr sent par l introduction d une conclusion x x telle que le lien axiome initial x x repr sentant x soit scind en deux liens axiomes chacun reliant l un des deux atomes de ce lien initial l atome correspondant de la conclusion introduite Les traductions des arbres auxiliaires poss dent dualement une conclusion zl x On obtient pour le m me exemple 7a 7b Lee ml 1 ere r mm mm mm mm SZ y Rdv q Dy EH e T w lit v sue v Lee H PI UL r D v sch attentivement ad Ca v b e GE vor Branchement par coupure p
29. un l ment et un vide nous l exprimons directement par un lien axiome entre deux ports de nos modules qui se correspondent Comme d autre part le clitique Je sert non seulement recevoir un 6 r le objet du verbe mais qu il modifie le verbe lui m me en le transformant en une forme cliticis e ici le voit nous avons besoin de relier le module clitique au module verbe par deux op rations l une de branchement par coupure l autre de branchement par axiome Le branchement par coupure n est possible que si les deux modules ont des conclusions qui sont duales l une de l autre Ceci n cessite de modifier les modules verbaux de mani re leur adjoindre une conclusion vide pouvant servir pour un tel branchement Il y aura autant de telles conclusions que le verbe pourra admettre de clitiques De plus l ordre dans lequel nous les installons au sein du module verbal n est pas neutre il permet de respecter les contraintes d ordre sur les clitiques en fran ais Derni re remarque l tablissement d un lien coupure entre une conclusion vide du module clitique et la conclusion duale dans le module verbal ne pourra conduire un r seau correct que si parall lement le lien axiome entre l hypoth se correspondant au cas du clitique et celle correspondant l assignation de cas du verbe peut tre install Ceci limine toute construction impossible du genre Pierre me lui lit modules pierre dp Cas pierre voit v 1
Download Pdf Manuals
Related Search