Logical Aspects of Computational Linguistics

Thisvolumecontainstheproceedingsofthe4thInternationalConferenceonL- icalAspectsofComputationalLinguistics,heldJune27 29,2001inLeCroisic, France. TheLACLconferencesaimtoprovideaforumforthepresentationand discussionofcurrentresearchinalltheformalandlogicalaspectsofcompu- tionallinguistics. Theprogramcommitteeselected16papersfromsubmissionsofoverallhigh quality. Thepaperscoverawiderangeoftopics,includingcategorialgrammars, dependency grammars,formal languagetheory, grammaticalinference, hyp- intensionalsemantics,minimalism,andtype-logicalsemantics,byauthorsfrom Australia,Canada,Denmark,France,Germany,Italy,TheNetherlands,Poland, Spain,Sweden,UnitedKingdom,andUSA. M. Moortgat (Universiteit Utrecht), G. K. Pullum (University of Calif- nia, Santa Cruz), and M. Steedman (University of Edinburgh) presented - vitedtalks,on StructuralEquationsinLanguageLearning , OntheDisti- tion between Model-Theoretic and Generative-Enumerative Syntactic Fra- works ,and ReconcilingType-LogicalandCombinatoryExtensionsofCate- rialGrammar respectively. Wewouldliketothankallthepeoplewhomadethis4thLACLpossible:the programcommittee,theexternalreviewers,theorganizationcommittee,andthe LACLsponsors. April2001 PhilippedeGroote &GlynMorrill Organization ProgramCommittee W. Buszkowski(Poznan) M. Kanazawa(Tokyo) R. Crouch,(PaloAlto) G. Morrill,co-chair(Barcelona) A. Dikovsky(Nantes) R. Muskens(Tilburg) M. Dymetman(Grenoble) F. Pfenning(Pittsburgh) C. Gardent(Nancy) B. Rounds,(AnnArbor) Ph. deGroote,co-chair(Nancy) E. Stabler(LosAngeles) OrganizingCommittee B. Daille(Nantes) C. Piliere,publicitychair(Nancy) A. Dikovsky(Nantes) C. Retor e,chair(Rennes) A. Foret(Rennes) P. Sebillot(Rennes) E. Lebret(Rennes) AdditionalReferees J. -M. Andreoli T. HollowayKing J. Marciniec P. Blackburn M. Kandulski J. -Y. Marion C. Brun F. Lamarche G. Perrier TableofContents InvitedTalks StructuralEquationsinLanguageLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 MichaelMoortgat OntheDistinctionbetweenModel-TheoreticandGenerative-Enumerative SyntacticFrameworks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Geo?reyK. Pullum,BarbaraC. Scholz ContributedPapers AFormalDe?nitionofBottom-UpEmbeddedPush-DownAutomataand TheirTabulationTechnique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 MiguelA. Alonso,EricdelaClergerie,ManuelVilares AnAlgebraicApproachtoFrenchSentenceStructure. . . . . . . . . . . . . . . . . . . 62 DanieleBargelli,JoachimLambek DeductiveParsingofVisualLanguages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 PaoloBottoni,BerndMeyer,KimMarriott,FrancescoParisiPresicce LambekGrammarsBasedonPregroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 WojciechBuszkowski AnAlgebraicAnalysisofCliticPronounsinItalian. . . . . . . . . . . . . . . . . . . . . 110 ClaudiaCasadio,JoachimLambek Consistent Identi?cation in the Limit of Any of the Classes k-Valued Is NP-hard. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 ChristopheCostaFlor encio PolarizedNon-projectiveDependencyGrammars. . . . . . . . . . . . . . . . . . . . . . . 139 AlexanderDikovsky OnMixingDeductionandSubstitutioninLambekCategorialGrammars. . 158 AnnieForet A Framework for the Hyperintensional Semantics of Natural Language withTwoImplementations. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 ChrisFox,ShalomLappin ACharacterizationofMinimalistLanguages. . . . . . . . . . . . . . . . . . . . . . . . . . . 193 HenkHarkema VIII TableofContents PartofSpeechTaggingfromaLogicalPointofView. . . . . . . . . . . . . . . . . . . 212 Torbjorn Lager,JoakimNivre TransformingLinearContext FreeRewritingSystemsintoMinimalist Grammars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228 JensMichaelis RecognizingHeadMovement. .

Includes supplementary material: sn.pub/extras

Invited Talks.- Structural Equations in Language Learning.- On the Distinction between Model-Theoretic and Generative-Enumerative Syntactic Frameworks.- Contributed Papers.- A Formal Definition of Bottom-Up Embedded Push-Down Automata and Their Tabulation Technique.- An Algebraic Approach to French Sentence Structure.- Deductive Parsing of Visual Languages.- Lambek Grammars Based on Pregroups.- An Algebraic Analysis of Clitic Pronouns in Italian.- Consistent Identification in the Limit of Any of the Classes k-Valued Is NP-hard.- Polarized Non-projective Dependency Grammars.- On Mixing Deduction and Substitution in Lambek Categorial Grammars.- A Framework for the Hyperintensional Semantics of Natural Language with Two Implementations.- A Characterization of Minimalist Languages.- of Speech Tagging from a Logical Point of View.- Transforming Linear Context-Free Rewriting Systems into Minimalist Grammars.- Recognizing Head Movement.- Combinators for Paraconsistent Attitudes.- Combining Syntax and Pragmatic Knowledge for the Understanding of Spontaneous Spoken Sentences.- Atomicity of Some Categorially Polyvalent Modifiers.