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 ChristopheCostaFlorencio 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...245 EdwardP. Stabler CombinatorsforParaconsistentAttitudes...261 JorgenVilladsen Combining Syntax and Pragmatic Knowledge for the Understanding of SpontaneousSpokenSentences ...279 JeanneVillaneau,Jean-YvesAntoine,OlivierRidoux AtomicityofSomeCategoriallyPolyvalentModi?ers ...296 R. Zuber AuthorIndex ...311 Structural Equations in Language Learning Michael Moortgat UtrechtInstituteofLinguistics-OTS Trans10,3512JKUtrecht,TheNetherlands Michael. Moortgat@let. uu. nl Abstract. Incategorialsystemswitha?xedstructuralcomponent,the learningproblemcomesdownto?ndingthesolutionforasetofty- assignmentequations. Ahard-wiredstructuralcomponentisproblematic ifonewanttoaddressissuesofstructuralvariation. Ourstartingpointis atype-logicalarchitecturewithseparatemodulesforthelogicalandthe structural components of the computational system.