Logic and Linguistics

Marseille - Luminy
February 13 - 17, 2006

Organizer: M-Renée Fleury, M. Quatrini, J. Vauzeilles.

Context: This workshop is part of Geometry of Computation 2006 (Geocal06), a special series of events in theoretical computer science organized by the GEOCAL group and taking place at the CIRM from January 30 to March 3. Geocal06 is supported by the following institutions: CIRM, CNRS, Luminy, Paris Nord, FRUMAM, IML, PPS, LIPN,

Preliminary programme

Thematic presentation: Linguists and logicians tried to specify grammars as logical theories. As compared to the traditional linguistics, the advantage of the logical approach is that we can prove important properties of the grammars such as soundness, completeness and consistency.

J-Y. Girard has introduced linear logic (1987) as a resource sensitive logic. The basic feature of linear logic that is essential for linguistic applications, is the absence of contraction and weakening rules. But the unlimited commutativity rule is not acceptable from the linguistic point of view either. If we do not allow the commutativity rule at all, we strongly restrict the expressive power to generate natural languages.

One of the promising approaches among various extensions and generalizations of Lambek grammars is to use proof nets technics inspired by linear logic.

This "Linguistics and logic" workshop aims at bringing together logicians, linguists, and computational scientists to discuss the problems of logical applications to linguistics.

Preregistration: on the Geocal06 site. Deadline: October 30, 2005.

Invited speakers:

• Anne ABEILLE, Laboratoire de Linguistique Formelle, Paris, France
• Michele ABRUSCI, Dipartimento di Filosofia, Università di Roma tre, Italia
• Denis BECHET, Laboratoire d'Informatique de Nantes Atlantique, France
• Philippe BLACHE,Laboratoire Parole et Langage, Aix en provence, France
• Claudia CASADIO ,Università degli Studi "G. d'Annunzio", Chieti, Italia
• Philippe de GROOTE, LORIA, INRIA, Nancy, France
• Max KANOVICH ,Queen Mary, University of London, England
• Alain LECOMTE, GEOD, CLIPS-IMAG, Grenoble, France
• Mickaël MOORTGAT, University of Utrecht, Nederlands
• Glyn MORRILL, Universitat Politècnica de Catalunya, Espagne
• Reinhard MUSKENS, Department of Linguistics, Le Tilburg, The Netherlands
• Guy PERRIER, LORIA ,INRIA, Nancy, France
• Aarne RANTA, Chalmers University of Technology, Göteborg, Sweden
• Christian RETORE, LaBRI, Université Bordeaux 1, France.

Preliminary programme

Speakers, titles and abstracts

• Anne ABEILLE,Laboratoire de Linguistique Formelle, Paris, France
  Title: Can we model coordinations (or not )?
  Abstract: Coordination has always been a problem for syntactic models. It challenges X-bar theory of syntactic structures (cf Borsley 2005), and more generally usual assumptions of phrase structure since partial constituents can be coordinated :
  "John gave a book to John and - a record to Mary"
  "John likes - and Paul dislikes red beans"
  Such elliptical constructions have been successfully accommodated within Categorial Grammar (Dowty 1988, Steedman 2000), but at the cost of losing phrase structure for more flexible constituency and spurious ambiguity.
  Coordination also questions the useufulness of unification as an operation on feature structures (Ingria 1990), given the fact that syncretic forms can simultaneously fulfill incompatible requests from coordinated heads, as in the French following example (where pousser expects an accusative pronominal complement whereas donner expects a dative one) :
  Paul nous a poussés et donné des coups de pied
  We show how both problems can be adressed within HPSG. We build on Ginzburg and Sag (2002) and Beavers and Sag (2004) for modelling elliptical constructions. We build on Sag (2005) for extending the type hierarchies to include syncretic forms.
  
  Références
  Beavers J. et I. Sag 2004. Coordinate ellipsis and apparent non constituent coordination, Proceedings HPSG Conference, CSLI on-line Publications.
  Borsley, R. 2005. Against ConjP, Lingua.115-4, p. 461-482
  Borsley, R. 2005. Les coordinations relèvent-elles de la syntaxe X-barre ?
  Langages, 160, p.25-40.
  Dalrymple, M., R.M. Kaplan 2000. 'Feature indeterminacy and feature resolution', Language 4, 759-798.
  Dowty D. 1988. Type raising, functional composition and non constituent coordination, in Oehrle, Bach, (eds) Categorial grammars and Natural language structures, p. 153-198.
  Ginzburg et I Sag 2000. Interrogative investigations, CSLI Publications.
  Godard D & Abeillé, A. 2005 (eds) La syntaxe de la coordination, Langages, 160.
  Ingria R 1990. The limits of unification, Proceedings ACL, p. 194-204.
  Jackendoff, R.S. 1977. X'-Syntax: A Study of Phrase Structure, Cambridge, Mass: MIT Press.
  Sag I 2005 La coordination et l'identité syntaxique des termes, Langages, p. 110-127 Steedman M 2000 The Syntactic Process, Cambridge, Mass: MIT Press.

• Michele ABRUSCI,Dipartimento di Filosofia, Università di Roma tre
  Title: Remarks on relationships between logic and linguistics
  Abstract: XXX.

• Denis BECHET,Laboratoire d'Informatique de Nantes Atlantique, France
  Title: Parsing Lambek calculus using partial composition
  Abstract: A proof of Lambek calculus or cyclic linear logic can be seen as a planar proof-net. In this context, we show that each proof-net can be transformed into a binary tree using a partial composition rule in such a way that, at each step, the complexity of the result of each partial composition does not increase. This result gives a direct parsing algorithm for Lambek grammars which is polytime wrt the length of the string (for a fixed grammar). Moreover, this kind of partial composition leads to a new approch for decomposing a sentences in subcomponents which is more associative than a traditional parse tree.

• Philippe BLACHE,Laboratoire Parole et Langage, Aix en provence, France
  Title: Au-delà des grammaires génératives : l'utilisation des contraintes pour des grammaires de description.
  Résumé: A la nécessité de traiter du matériel linguistique à tout venant, typiquement de la langue parlée, conduit aujourd'hui à la proposition de modèles dépassant les limites connues des approches génératives classiques. Il devient en effet indispensable de traiter des données dispersées, incomplètes ou non canoniques. La réponse à ce besoin repose la plupart du temps sur l'introduction d'heuristiques ou de techniques de rattrapage. Nous proposons au contraire de prendre en compte ces questions dans le modèle théorique lui-même. Dans notre approche, toutes les informations syntaxiques sont représentées sous la forme de contraintes : l'analyse syntaxique devient ainsi un processus de satisfaction plutôt que de déduction
  Après une présentation du cadre théorique, nous proposons une illustration de son intérêt dans le traitement de trois problèmes fondamentaux :
  - la robustesse : la rechercher de la grammaticalité est remplacée par la construction d'une caractérisation de l'énoncé exploitant la possibilité de relachement de contrainte
  - la gradience : il est nécessaire d'expliquer pourquoi certains énoncés sont plus acceptables ou plus difficiles à interpréter que d'autres. La représentation sous forme de contraintes permet une quantification de ce phénomène.
  - l'interaction entre domaines de l'analyse linguistique : la construction du sens repose sur l'exploitation de parties d'informations provenant de domaines différents (prosodie, syntaxe, etc.).
  L'utilisation de systèmes de contraintes permet d'en expliquer l'interaction.
  

  Title: Beyond generative grammar : the role of constraints toward description grammars
  Abstract : The need of dealing with unrestricted linguistic material (typically spoken languages) necessitates to elaborate new models, pushing forward the limits of generative grammars. Parsing such material requires the treatment of spread, incomplete and non canonical data. Usually, the solution to this problem consists in using heuristics or ad hoc techniques. We propos, on the opposite, in integrate these question to the theoretical model itself. In our approach, called Property Grammars, all information is represented by means of constraints parsing becomes a satisfaction process, instead of a deduction one.
  After a presentation of the theoretical framework, we propose to illustrate the interest of the approach in the resolution of three different problems:
  - Robustness: the notion of grammaticality gives the floor to a more general one called characterization that exploits constraint relaxation techniques.
  - Gradience: we need to explain why (and how) some utterances are more complex than other. The representation by means of constraints makes it possible to explain and quantify this phenomenon.
  - Domain interaction: the different linguistic domains (prosody, syntax, etc.) interact to form meaning. Our constraint-based approach shows how such interaction works in order to build a structure from partial information. .

• Claudia CASADIO, Università degli Studi "G. d'Annunzio", Chieti, Italia
  Title: Non commutative linear logic vs. pregroup grammar
  Abstract: Recently a new kind of categorial grammar has been developed by J.Lambek with the cooperation of a number of scholars: C. Casadio, D. Bargelli, M. Barr, W. Buszkowski, A. Preller among others. Pregroups are based on a special logic called "compact bilinear logic" that is connected to non-commutative linear logic, with two negations, studied in particular by V. M. Abrusci, as a refinement of Yetter's cyclic linear logic.
  Pregroups have been studied on the theoretical side (Lambek (1999),(2001), (2004), Casadio & Lambek (2002), Buszkowski (2001) ), and on the linguistic side; linguistic applications include: English (Lambek 2004), French (Lambek & Bargelli 2001, Preller 2005), Italian (Casadio & Lambek 2001, Casadio 2005), German (Lambek 2000), Japanese (Cardinal 2002), Arabic, Turkish (Bargelli & Lambek 2004), Latin (Casadio & Lambek 2005).
  In this paper I first introduce pregroups and discuss the relations with Lambek's Syntactic Calculus on one side, and non-commutative linear logic on the other. In particular, the relevant features of compact bilinear logic will be considered and the definition of a Pregroup Grammar (PG)will be given, with its relevant dimensions: contractions vs. expansions, ordering postulates, lexical conditions, metarules, features and templates.
  The distinctive feature of PG is that linguistic well-formedness and grammaticality are proved by successful calculations on (a finite set of) types assigned by the lexicon to the words and morphemes of a language. Finally some linguistic applications will be presented: unbounded dependencies, direct questions and wh-questions, romance clitics, quantifiers and scope.
  These examples will show that pregroups are interesting not only from the point of view of theoretical and computational linguistics, as a tool powerful enough to give the syntactical analysis of languages belonging to different families, through a system of algebraic computations, but also from the cognitive point of view, in offering an explanation of the operations involved in the speaker's mind during the processing of linguistic communication.

• Philippe DE GROOTE,LORIA, INRIA, Nancy, France
  Title: Abstract Categorial Grammars: definition and formal properties
  Abstract: Abstract Categorial Grammars (ACGs) are a new formalism intended for the description of natural language syntax and semantics. This formalism, which derives from current type-logical grammars, is based on the implicative fragment of linear logic.
  Consequently, ACGs generate linear lambda-term languages (this generalizes both string and tree languages).
  In this talk, I will motivate and introduce the formalism, and study its formal properties (expressive power, decidability and complexity of universal membership, membership, and emptyness).

• Valeria DE PAIVA, PARC (Palo Alto Research Center) UK
  Title: Glue Semantics for Linear Logicians
  Abstract: That Linear Logic is connected to Linguistics through the Lambek Calculus and related systems is well-knonw. I would like to report on a different kind of relationhip between linguistics and linear logic. This is work relating natural language semantics (instead of syntax) to commutative multiplicative linear logic, via the use of Glue Semantics of Dalrymple et al.

• Max KANOVICH,Queen Mary, University of London, England
  Title: Lambek Calculus and its generalizations: Expressiveness, Complexity
  Abstract: In order to describe a natural language, Lambek designed a `linguistic' calculus, which could be conceived of as a natural generalization of categorial grammars. From a logical point of view, Lambek calculus can be thought of as a non-commutative version of the multiplicative fragment of Girard's linear logic.
  To improve the linguistic expressive power of Lambek calculus, we can enrich this purely multiplicative system with additive connectives (expressing the `union' of grammar categories for instance), or second order quantifiers (which allows us to express a number of intricate phenomena such as a so-called linguistic polymorphism), etc
  I will also address the complexity issues of these generalizations of Lambek calculus..

• Alain LECOMTE,GEOD, CLIPS-IMAG, Grenoble
  Title: Exposé introductif: peut-on parler d'une logique de la langue ?
  Résumé: Les travaux présentés dans ces journées ont tous pour soubassement implicite l'idée que la logique fournit « naturellement » un modèle pour penser la langue. Mais est-ce si sûr ? Quel sens devons-nous donner à un tel présupposé ? Par exemple : la découverte de la logique linéaire repose en grande partie sur le respect de symétries fondamentales : un système logique se doit de respecter certaines symétries si on veut qu'il possède des propriétés intéressantes (élimination des coupures?). Or, une affirmation souvent faite par les linguistes (Chomsky, Kayne, Stabler entre autres) est que justement la langue est de façon inhérente asymétrique. Comment concilier ces deux exigences ? Le modèle catégoriel multimodal (Moortgat) se présente souvent avec l'hypothèse implicite d'un « raisonnement grammatical ». Comment devons-nous interpréter une telle hypothèse ? La thèse défendue dans cet exposé sera que les travaux qui relèvent de notre paradigme s'inscrivent plus dans une tradition philosophique (renvoyant à une phénoménologie) que dans une perspective de « traitement automatique des langues ». Ce sera l'occasion de passer en revue de nombreux travaux du domaine et de répondre à la question « qu'apporte le cadre logique à la compréhension du phénomène linguistique ? ». Cet exposé, essentiellement à destination des étudiants, sera donné en français.

• Alain LECOMTE,GEOD, CLIPS-IMAG, Grenoble
  Title: How to use primitives of Linear Logic to modelize linguistic phenomena like anaphora and ellipis?
  Abstract: In this talk, I shall present a model of grammar quite similar to ACG (de Groote and al.) and Lambda Grammars (Muskens) but designed to simulate Minimalist Grammars (Stabler). The abstract syntax uses formulae of Intuitionistic Linear Logic. Phonological and semantical interpretations are provided by a calculus on labels, driven by the abstract syntax. Move operations depend on the design of labels. The exponential allows for reusing or discarding some formulae involved in phenomena like anaphora and ellipsis in order to give a foundation to slogans like "anaphora is contraction".

• Mickaël MOORTGAT ,University of Utrecht, Nederlands
  Title: Lambek calculus with Grishin interactions
  Abstract: Recent efforts to equip the Lambek calculus with facilities to study language diversity and its limitations have focused on structural rules controlled by modalities. This strategy is by now well understood, in its logical (Kurtonina/Moortgat 1997), computational (Moot 2002) and linguistic aspects (Bernardi 2002, Vermaat 2006).
  Structural rules are non-logical axioms: as such, they do not contribute to our understanding of invariant properties of grammatical organization. In this talk, I explore an alternative, enhancing logical rather than structural expressivity. In addition to the Lambek tensor and its residual left and right slash, I consider a dual residuated family (cotensor and its co-implications). In linear logic, these are related by De Morgan duality. For linguistic purposes, a more subtle interaction is required, preserving the individual characteristics of the operators involved. The general framework of Grishin (1983) provides such interaction principles.
  I investigate the relation of type similarity (aka conjoinability) for the resulting system L2G4 (bi-Lambek calculus with Grishin Type IV interactions). I show that for Lambek formulas this can be characterized in terms of an interpretation in the free Abelian group generated by the atomic types. This means that the L2G4 similarity relation recovers the expressivity of conjoinability in LP/MLL (Pentus 1993).
  To express structural generalizations, one can now replace Lambek type assignments by ancestor or descendant types with respect to the similarity relation. Such types can derivationally adapt to LP conditions, without actually using structural rules. For linguistic motivation, I discuss scope construal and displacement phenomena.
  
  REFERENCES Kurtonina & Moortgat, Structural control, in Blackburn & de Rijke (eds.) Specifying Syntactic Structures, CSLI, Stanford, 1997, 75-113.
  Bernardi, Reasoning with polarity in categorial type logic. PhD thesis, Utrecht 2002.
  Vermaat, The logic of variation. A cross-linguistic account of wh-question formation. PhD thesis, Utrecht 2006.
  Moot, Proof nets for linguistic analysis. PhD thesis, Utrecht 2002.
  Grishin, On a generalization of the Ajdukiewicz-Lambek system. In Mikhailov (ed.) Studies in Nonclassical Logics and Formal Systems, Moscow, 1983, 315-343.
  Pentus, The conjoinability relation in {L}ambek calculus and linear logic. Tech report, ILLC, Amsterdam, 1993.

• Reinhard MUSKENS,Department of Linguistics, Le Tilburg, The Netherlands
  Title: Abstract syntax, concrete syntax, semantics, and natural langage
  Abstract: In a now famous paper, written mainly in the 1940's but published in 1961, Haskell Curry draws a distinction between the grammatical structure of a language and the way this grammatical structure is represented in terms of expressions. The structure proper he calls 'tectogrammatics' and its representation is called 'phenogrammatics'. More precisely, the paper starts with phrases of two types ('S' and 'N', for sentence and noun phrase) and then considers a functional type hierarchy over these, so that we have functions from N to S, functions from functions from N to S to phrases of type S, etc., etc. Tectogrammatics now concerns these typed functions and their combination, while phenogrammatics looks at the result of evaluating tectogrammatical expressions. Curry's distinction is identical to the 'abstract syntax'-'concrete syntax' distinction in the theory of programming languages but is meant to be applied to natural language.
  In my talk I will highlight two proposals for the architecture of natural language grammars that can be seen as formalizations and extensions of Curry's idea: the Abstract Categorial Grammars of De Groote (2001) and my own Lambda Grammars (Muskens 2001). These two proposals were made independently but are very close. They treat the logic of abstract syntax as that of the linear combinators, which, unlike the Lambek calculus, is commutative. Word order is dealt with at the concrete syntax level and semantics is directly dependent on abstract syntax. Concrete syntax and semantics are treated in a completely symmetrical way. I will argue that setting up the grammar along these lines gives many advantages of modularization and simplification.

• Guy PERRIER, LORIA ,INRIA, Nancy, France
  Title: Interaction Grammars and their implementation
  Abstract: Interaction Grammars and their implementation Abstract : Interaction Grammars are a new formalism for the syntactic and the semantic analysis of natural languages. This formalism is inspired by Categorial Grammars, putting forward the notion of polarity to manage the resource sensitivity of natural languages. It is also inspired by work on TAG, using underspecification in the description of syntactic and semantic structures.
  In a first part, we describe the formalism, showing how the key notions of polarity and underspecification are used.
  A second part is devoted to the presentation of the parser LEOPAR (http://www.loria.fr/equipes/calligramme/leopar/), which is based on Interaction Grammars.

• Anne PRELLER, LIRMM-CNRS, Montpellier, France
  Title: Compact 2-categories, a semantical interface for Natural Language Processing
  Abstract: The free compact 2-categories are defined geometrically. They can be identified with the (2-category of) derivations in pregroup grammars, a recent concept developed by Joachim Lambek where they play the role of an interface between syntax and semantics.

• Gabriele PULCINI, Università Roma Tre-IML Marseille, rance
  Title: Permutative Logic
  Abstract: Recent work establishes a direct link between the complexity of a linear logic proof in terms of the exchange rule and the topological complexity of its corresponding proof net, expressed as the minimal rank of the surfaces on which the proof net can be drawn without crossing edges. That surface is essentially computed by sequentialising the proof net into a sequent calculus which is derived from that of linear logic by attaching an appropriate structure to the sequents. We show that this topological calculus can be given a better-behaved logical status, when viewed in the variety-presentation framework introduced by J.-M.Andreoli [2004]. This change of viewpoint gives rise to permutative logic (J.-M.Andreoli, G.P., P.Ruet [2005]), which enjoys cut elimination and focussing properties and comes equipped with new modalities for the management of the exchange rule. Moreover, both cyclic and linear logic are shown to be embedded into permutative logic. It provides the natural logical framework in which to study and constrain the topological complexity of proofs, and hence the use of the exchange rule.

• Aarne RANTA,Chalmers University of Technology, Göteborg, Sweden
  Title: Parametrized Grammar Modules for Romance Languages
  Abstract: It is a common experience that Romance languages, e.g. French and Italian, are so close to each other that anyone who knows one of them can easily learn any other easily, by, so to say, just learning the differences. The talk will exploit this idea on the level of formal grammars, by using the method of parametrized modules (functors). This idea originates in the programming language ML, and a version of it has been adapted in the grammar formalism GF. Thus we have built in GF a grammar system for Romance languages by writing functors that define a shared Romance grammar base. The individual languages are obtained from this base by different instantiations of a set of parameters. The GF resource grammar library succeeds in this way to share 70% of the code of the grammars for French, Italian, and Spanish, covering a fragment that is comparable in size to the CLE (Core Language Engine) fragment.

• Christian RETORE, LABRI, Bordeaux
  Title: Exposé introductif
  Abstract: XXX.

• Christian RETORE, LABRI, Bordeaux
  Title: TBA
  Abstract: XXX.

• Patrick THEVENON, LAMA, Chambery, France
  Title: Typage principal avec deux flèches
  Abstract: Dans le cadre des grammaires catégorielles abstraites (ACG) introduites par Ph. de Groote, il est possible de faire des traductions entre divers formalismes, par exemple entre une structure syntaxique et une structure sémantique. Développé à la base sur le lambda calcul linéaire très utile en linguistique, le système connaît des limites sur l'expressivité notamment dans le cadre sémantique, où l'on souhaite pouvoir utiliser plusieurs fois une même variable. D'où l'idée d'introduire dans le lambda calcul linéaire de l'intuitionnisme, ce qui fait donc un lambda-calcul avec deux types de variables et surtout deux types de flèches (intuitionniste et linéaire). Il est alors naturel de se demander quel peut être le type principal d'un terme écrit dans ce lambda-calcul, et quelles sont ses propriétés. Une difficulté vient du fait que lors de la recherche du type d'un terme, des flèches peuvent être sous-spécifiées, c'est à dire qu'elles peuvent être indifféremment remplacées soit par une flèche intuitionniste, soit par une flèche linéaire. Afin de ne pas compliquer ce lambda-calcul, il est préférable de ne pas avoir à garder les flèches sous-spécifiées (ou indéterminées), et donc d'être capable de donner des cas pour lesquels on peut avoir une notion de type principal sans ces flèches. Dans le cas général, nous verrons que c'est impossible. Mais il existe deux cas, le cas linéaire et le cas $\eta$-long, pour lesquels nous avons un résultat.