Lecture Notes in Artificial Intelligence

Subseries of Lecture Notes in Computer Science Edited by J. G. Carbonell and J. Siekmann

1328

Lecture Notes in Computer Science

Edited by G. Goos, J. Hartmanis and J. van Leeuwen

3
Berlin Heidelberg New York Barcelona Budapest Hong Kong London Milan Paris Santa Clara Singapore Tokyo

Christian Retor (Ed.) e

Logical Aspects of Computational Linguistics

First International Conference, LACL 96 Nancy, France, September 23-25, 1996 Selected Papers

13

Series Editors Jaime G. Carbonell, Carnegie Mellon University, Pittsburgh, PA, USA J rg Siekmann, University of Saarland, Saarbr cken, Germany o u Volume Editors Christian Retor e INRIA Lorraine & CRIN-C.N.R.S. 615 rue du jardin botanique, BP 101 F-54602 Villers l` s Nancy cedex, France e E-mail: retore@loria.fr

Cataloging-in-Publication data applied for Die Deutsche Bibliothek - CIP-Einheitsaufnahme Logical aspects of computational linguistics : rst International conference ; selected papers / LACL 96, Nancy, France, September 23 - 25, 1996. Christian Retore (ed.) - Berlin ; Heidelberg ; New York ; Barcelona ; Budapest ; Hong Kong ; London ; Milan ; Paris ; Santa Clara ; Singapore ; Tokyo : Springer, 1997 (Lecture notes in computer science ; Vol. 1328 : Lecture notes in articial intelligence) ISBN 3-540-63700-1

CR Subject Classication (1991): F.4, F.3, I.2.7, I.2.3, J.5

ISBN 3-540-63700-1 Springer-Verlag Berlin Heidelberg New York
This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microlms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. c Springer-Verlag Berlin Heidelberg 1997 Printed in Germany Typesetting: Camera-ready by author SPIN 10645624 06/3142 5 4 3 2 1 0 Printed on acid-free paper

Preface
This volume contains selected papers of the rst international conference on Logical Aspects of Computational Linguistics, held in Nancy, France, from April 23 to 25, 1996.1 A general introduction by some members of the committee explains the relevance of developing a conference on this topic, situates the papers, and provides an account of the discussions, namely, New syntaxes for linguistic theories, Logical aspects of the minimalist program and Logical semantics. The volume contains eigtheen selected papers and four invited papers. There were forty four submissions, their overall quality was high, and selection was dicult. The Programme Committee is very grateful to everyone who submitted a paper and to all the referees listed overleaf for their essential assistance and generously given time. Let us also thank the participants for the pleasant and stimulating atmosphere during the meeting. The Committee is especially grateful to the invited speakers, namely, Jean-Yves Girard,2 Aravind K. Joshi, Marcus Kracht, Dale Miller and Edward Stabler (respectively from Marseilles, Philadelphia, Berlin, Philadelphia and Los Angeles). Indeed, not only did they accept our invitation and give their lectures, but they also substantially contributed to the conference, in particular to the discussions. Finally we wish to thank the two institutions under one roof that co-organized this event, namely inria-Lorraine and crin-c.n.r.s. , as well as the sponsors of this event: France-Tlcom CNET, Rank-Xerox Research Center, lInstitut Naee tional Polytechnique de Lorraine, lUniversit Henri Poincar, La Rgion Lore e e raine, La Communaut Urbaine du Grand Nancy. e More personally, I wish to thank the members of the Programme Committee and the Organizing Committee, listed overleaf, for their hard work and support, as well as Roger Hindley, Claude Kirchner and Pierre Lescanne who gave me precious advice, not to forget my research project without whom nothing would have happen, Calligramme.3 Nancy, July 1997
1

Christian Retor e

The idea of this conference germinated during a workshop we organized in september 1995 on the same topic, whose selected papers are to be published in the January 1998 isssue of the Journal of Logic, Language and Information. His contribution, Introduction to linear logic is not included in this volume, but Jean-Yves Girard recently published an introduction to linear logic: Linear logic: its syntax and semantics. In J.-Y. Girard, Y. Lafont and L. Regnier (Eds.) Advances in Linear Logic, volume 222 of London Mathematical Society Lecture Notes. Cambridge University Press, 1995. pp. 142 Calligramme, Logique linaire, rseaux de dmonstration et grammaires e e e catgorielles (inria-Lorraine & crin-c.n.r.s.): D. Bechet, Ph. de Groote, e F. Lamarche, A. Lecomte, S. Malecki, J.-Y. Marion, G. Perrier, N. Pierre (secretary), C. Retor. e

Programme Committee
V. Michele Abrusci Universit` di Roma tre a Patrick Blackburn Universitt des Saarlandes, Saarbrcken a u Marc Dymetman Rank-Xerox Research Center, Grenoble Mark Johnson Brown University , Providence Alain Lecomte Universit Grenoble 2 & INRIA-Lorraine e Michael Moortgat OTS, Universiteit Utrecht Glyn V. Morrill Universitat Polit`cnica de Catalunya, Barcelona e Aarne Ranta Helsingin Yliopisto Christian Retor (Chair) e INRIA-Lorraine & CRIN-CNRS, Nancy Eric Villemonte de la Clergerie INRIA-Rocquencourt

Additional Reviewers
Jos L. Balczar e a Franois Barthlmy c ee Kalyan Basu Denis Bechet Francine Blanchet-Sadri Joachim Gabarr o Bertrand Gaie Philippe de Groote Herman Hendriks Miki Hermann Barbara Heyd Hl`ne Kirchner ee Franois Lamarche c Bernard Lang Denis Lugiez Sophie Malecki Richard Oehrle Guy Perrier Anne Reboul Laurent Romary Michael Rusinovitch Klaus Schulz Pascale Sbillot e

Organizing Committee
Denis Bechet, Anne-Lise Charbonnier, Philippe de Groote, Franois Lamarche, Bernard Lang , Guy Perrier, Nathalie Pierre, c Christian Retor (Chair), Armelle Savary e INRIA-Lorraine & CRIN-CNRS, Nancy : INRIA, Rocquencourt

Table of Contents
Logical Aspects of Computational Linguistics: an introduction Patrick Blackburn, Marc Dymetman, Alain Lecomte, Aarne Ranta, Christian Retor, and Eric Villemonte de la Clergerie . . . . . . . 1 e

Invited papers
Partial proof trees, resource sensitive logics, and syntactic constraints Aravind K. Joshi and Seth Kulick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Inessential features Marcus Kracht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Linear logic as logic programming: an abstract Dale Miller . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Derivational minimalism Edward Stabler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

Selected papers
Tree adjoining grammars in non-commutative linear logic V. Michele Abrusci, Christophe Fouquer and Jacqueline Vauzeilles . . . . . . . 96 e Constructing dierent phonological bracketings from a proof net Denis Bechet and Philippe de Groote . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Vagueness and type theory Pascal Boldini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 A natural language explanation for formal proofs Yann Coscoy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 Models for polymorphic Lambek calculus Martin Emms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 Sloppy identity Claire Gardent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 A family of decidable feature logics which support HPSG-style set and list construction Stephen J. Hegner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Language understanding: a procedural perspective Ruth Kempson, Wilfried Meyer Viol and Dov Gabbay . . . . . . . . . . . . . . . . . . . 228

VIII

Table of Contents

The automatic deduction of classicatory systems from linguistic theories Paul John King and Kiril Ivanov Simov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 A belief-centered treatment of pragmatic presupposition Lucia H. B. Manara and Anne de Roeck . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 Connected sets of types and categorial consequence Jacek Marciniec . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 Generation as deduction on labelled proof nets Josep M. Merenciano and Glyn V. Morrill . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 Semilinearity as a syntactic invariant Jens Michaelis and Marcus Kracht . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 Quantitative constraint logic programming for weighted grammar applications Stefan Riezler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 Strict LT2: regular :: Local: recognizable James Rogers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 Pomset logic and variants in natural languages Irene Schena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386 Constraint logic programming for computational linguistics Frieder Stolzenburg, Stephan Hhne, Ulrich Koch and Martin Volk . . . . . . 406 o Representation theorems for residuated groupoids Marek Szczerba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435

Author Index
Abrusci , V. Michele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Bechet , Denis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Blackburn , Patrick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Boldini , Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Coscoy , Yann . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 Dymetman , Marc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Emms , Martin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 Fouquer , Christophe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 e Gabbay , Dov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 Gardent , Claire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Groote (de) , Philippe . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 Hegner , Stephen J. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 Hone , Stephan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406 Joshi , Aravind K. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Kempson , Ruth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 King , Paul John . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 Koch , Ulrich . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406 Kracht , Marcus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43, 329 Kulick , Seth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Lecomte , Alain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Manara , Lucia H. B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 Marciniek , Jacek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 Meyer Viol , Wilfried . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 Merenciano , Josep M. . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 Michaelis , Jens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329 Miller , Dale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Morrill , Glyn V. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310 Ranta , Aarne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Retor , Christian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 e Riezler , Stefan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 Roeck (de) , Anne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 Rogers , James . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366 Schena , Irene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386 Simov , Kiril Ivanov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 Stabler , Edward . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 Stolzenburg , Frieder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406 Szczerba , Marek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 Vauzeilles , Jacqueline . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 Villemonte de la Clergerie , Eric . . . . . . . . . . . . . . . 1 Volk , Martin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406