D &243;&242; &243; &242; &236;&24(5)

5.5ParsingComplexity

Chart-parsingwithedgesthathaveattachedLC-graphsviolatesaveryimportantinvariantofcontext-freechart-parsing,namelythatanytwoedgescoveringthesamesubsequencecanbetreatedasequalsregard-lessofhowtheywerederived.Here,eitherthroughtwodifferentadjunc-tionsorthroughanadjunctionandabracketing,itispossibletoobtaintwoedgescoveringthesamesubsequencewithdifferentLC-graphs.Nomethodisknownfortreatingtheseedgesasequals,althoughseeSection7forfurtherdiscussionofthispoint.Thismeansthatbeforeaddinganewedge,wemustcheckforanexistingedgecoveringthesameintervalandcombinetheirLC-graphsintoaset.

A graph-theoretic construction for representing the derivational side-conditions in the construction of axiomatic linkages for Lambek proof nets is presented, along with a naive algorithm that applies it to the sequent derivability problem for the Lambek C

Whilethenumberofedgesthatcanbeaddedtothechartisstillqua-draticinthelengthofthesequenceofaxiomaticformulae(whichinturngrowswiththelengthofaninitialsequent),combiningtwoexistingedgesbyAdjunctioninvolvescombiningallpossiblepairsofLC-graphsintheirrespectivesets,withtheresultthatthesizeofthesesetsmaygrowexpo-nentiallyasafunctionoftheintervalcoveredbyanedge.Sothisalgorithmisnotpolynomial-timeintheworstcase.

5.6IncrementalEnforcementofIntegrityCriteria

Inspiteofitsexponentialworst-casecomplexity,thisalgorithmdoesper-mitsomedegreeofincrementalityintheenforcementoftheintegritycri-teriaforLC-graphs.

Amongthethreeintegritycriteria,I(2)standsoutbecauseitdemandsthataparticularkindofpath,namelyacycle,doesnotexist,whereasI(3)andI(CT)demandthataparticularkindofpathdoesexist.ThismakesI(2)easytoenforceincrementally.Beforeassertinganedge,wesimplydiscardthetheLC-graphswithcyclesfromitsset.IfnoLC-graphsremain,thentheedgeitselfcanbediscarded.

I(3)andI(CT)canbeenforcedincrementallytoalesserextentwithLC-graphs,althoughseeSectionforfurtherdiscussionofthispoint.Ifnoterminalplus-nodeispath-accessiblefromtheplus-daughterofalambda-node,andthatplus-daughterdoesyethavethepathsrequiredbyI(3)andI(CT),thenitwillneverhavethem,andtheLC-graphcanbediscarded.Iftherequiredpathsalreadyexist,thentheywillneverdisappear,sothisplus-daughterdoesnotneedtobecheckedagain.

I(1)cannotbecheckedincrementally,but:

Proposition5.1Ifaspanninglinkagesatis esI(2)andPN(1),thenitsat-is esI(1).

Proof.GivenPN(1),thereisonlyonenodewithin-degree0.Sincetherearenocycles,everynodemustbepath-accessiblefromthatnode.

PN(1)canbeenforcedattheoutsetbyensuringthatthesequenceofter-minalformulaehasonlyonepositiveformula.ThismeansthatprovidedwearecheckingI(2),wecanignoreI(1).

6RelatedParsingProblems

ItisimportanttorealisethatthesequentderivabilitydecisionproblemisonlyoneaspectofparsingwithLCGs.Thereareothersourcesofcomplex-ity,andotherrestrictionsthatcanbemade,whichcanaffectthecomplex-ityoftheoverallproblem.

A graph-theoretic construction for representing the derivational side-conditions in the construction of axiomatic linkages for Lambek proof nets is presented, along with a naive algorithm that applies it to the sequent derivability problem for the Lambek C

6.1FixingtheGrammar

Pentus[11]provedthatLCGsareweaklyequivalenttoCFGsbyshowinghowtoconstructanequivalentCFGfromanyLCG.Thesizeoftheresult-ingCFGisexponentiallylargerthantheoriginalLCGintheworstcase,sothisconstructioncannotbeusedtoestablishapolynomial-timebijectionbetweenthetwoclassesofparsingproblems.

Ontheotherhand,ifwe xaparticularLCG,,applyPentus’scon-structionoff-line,andthenask“Givenastringofwords,doesbelongto?,”thenthis xedLCGrecognitionproblemispolynomial-timebe-causeCFGrecognitioncanalsobeperformedinpolynomial-time.ThisisdescribedindetailbyFinkelandTellier[2].

6.2LexicalAmbiguity

Givenastringofwords,,andagrammar,(un xed),ifwewanttoknowwhetherbelongsto,wemust rst ndthecategoriesassociatedwitheachwordofbythelexiconofbeforeaskingthesequentderiv-abilityquestion.Itisoftenthecase,however,thatthereismorethanonecategoryassociatedwiththewordsof.Evenifthesequentderivabil-ityproblemshouldturnouttobesolvableinpolynomialtime,iterativelychoosingcategoriesandperformingasequentderivabilitycheckcouldleadtopossiblecategoryselectionsgivenastringofwords.Atpresent,nomethodisknownforsomehowcombiningmultiplelexicalcategoriesinthecourseofasingleproofsearch,althoughitislikelythatoneexists.

6.3Parsingvs.Recognition

Sequentderivability,justascontext-freechartparsing,asksayes-or-noquestion.InthecontextofCFGparsing,thisisknownasthestringrecog-nitionproblem.TrueCFGparsinginvolvesnotjustdeterminingwhetherastringisparseable,butprovidingtheparsetreesforthestringifitis.Intheworstcase,thistakesexponentialtime,becausealthoughaparsingchartcanbebuiltinpolynomialtime,unpackingthechartandenumer-atingeachtreecontainedinitcantakeexponentiallylong.

Theanalogueinthecaseofsequentderivabilityistoprovideanac-tualsemantictermforaderivationratherthanjust’yes’or’no.’Thistermistheoneobtainedaftervariablesubstitutionisperformedonthelabelannotatingtherightmost(positive)terminalformula.Justastherearein-herentlyambiguousstringsinsomeCFGs,therearealsosequentswithinherentlymorethanonesemanticreadingintheLambekCalculus.Infact,thenumberofreadingscangrowexponentiallyasafunctionofthelengthofthecandidatesequent.

De netobethefollowingfamilyofsequents,parametrisedby:

A graph-theoretic construction for representing the derivational side-conditions in the construction of axiomatic linkages for Lambek proof nets is presented, along with a naive algorithm that applies it to the sequent derivability problem for the Lambek C

Forexample,isthesequent:

Proposition6.1Forallnaturalnumbers,thesequentisderivableintheLambekCalculus,withsemanticreadingsgivenbystrings:

whereforall

Proof.Let,either(and),or(and).bethegraph:

and

bethegraph:

andlettailandtail.ItcanbeseenthatandinternallypossessthepathsrequiredbyI(3)andI(CT)fo …… 此处隐藏：5898字，全部文档内容请下载后查看。喜欢就下载吧 ……