Transactions of the Association for Computational Linguistics, 1 (2013) 13–24. Action Editor: Giorgio Satta.

dans tacle sur

Transactions of the Association for Computational Linguistics, 1 (2013) 13–24. Action Editor: Giorgio Satta.

Submitted 11/2012; Published 3/2013. c
(cid:13)

2013 Association for Computational Linguistics.

FindingOptimal1-Endpoint-CrossingTreesEmilyPitler,SampathKannan,MitchellMarcusComputerandInformationScienceUniversityofPennsylvaniaPhiladelphia,PA19104epitler,kannan,mitch@seas.upenn.eduAbstractDependencyparsingalgorithmscapableofproducingthetypesofcrossingdependenciesseeninnaturallanguagesentenceshavetra-ditionallybeenordersofmagnitudeslowerthanalgorithmsforprojectivetrees.For95.8-99.8%ofdependencyparsesinvariousnat-urallanguagetreebanks,wheneveranedgeiscrossed,theedgesthatcrossitallhaveacommonvertex.Theoptimaldependencytreethatsatisfiesthis1-Endpoint-Crossingprop-ertycanbefoundwithanO(n4)parsingal-gorithmthatrecursivelycombinesforestsoverintervalswithoneexteriorpoint.1-Endpoint-CrossingtreesalsohavenaturalconnectionstolinguisticsandanotherclassofgraphsthathasbeenstudiedinNLP.1IntroductionDependencyparsingisoneofthefundamentalprob-lemsinnaturallanguageprocessingtoday,withap-plicationssuchasmachinetranslation(DingandPalmer,2005),informationextraction(CulottaandSorensen,2004),andquestionanswering(Cuietal.,2005).Mosthigh-accuracygraph-baseddepen-dencyparsers(KooandCollins,2010;RushandPetrov,2012;ZhangandMcDonald,2012)findthehighest-scoringprojectivetrees(inwhichnoedgescross),despitethefactthatalargeproportionofnat-urallanguagesentencesarenon-projective.Projec-tivetreescanbefoundinO(n3)temps(Eisner,2000),butcoveronly63.6%ofsentencesinsomenaturallanguagetreebanks(Table1).TheclassofdirectedspanningtreescoversalltreebanktreesandcanbeparsedinO(n2)withedge-basedfeatures(McDonaldetal.,2005),butitisNP-hardtofindthemaximumscoringsuchtreewithgrandparentorsiblingfeatures(McDonaldandPereira,2006;McDonaldandSatta,2007).Therearevariousexistingdefinitionsofmildlynon-projectivetreeswithbetterempiricalcoveragethanprojectivetreesthatdonothavethehardnessofextensibilitythatspanningtreesdo.However,thesehavehadparsingalgorithmsthatareordersofmag-nitudeslowerthantheprojectivecaseortheedge-basedspanningtreecase.Forexample,well-nesteddependencytreeswithblockdegree2(Kuhlmann,2013)coveratleast95.4%ofnaturallanguagestruc-tures,buthaveaparsingtimeofO(n7)(Gómez-Rodríguezetal.,2011).Nopreviouslydefinedclassoftreessimultane-ouslyhashighcoverageandlow-degreepolynomialalgorithmsforparsing,allowinggrandparentorsib-lingfeatures.Wepropose1-Endpoint-Crossingtrees,inwhichforanyedgethatiscrossed,allotheredgesthatcrossthatedgeshareanendpoint.Whilesimpletostate,thispropertycovers95.8%ormoreofde-pendencyparsesinnaturallanguagetreebanks(Ta-ble1).Theoptimal1-Endpoint-Crossingtreecanbefoundinfasterasymptotictimethananyprevi-ouslyproposedmildlynon-projectivedependencyparsingalgorithm.Weshowhowany1-Endpoint-Crossingtreecanbedecomposedintoisolatedsetsofintervalswithoneexteriorpoint(Section3).Thisisthekeyinsightthatallowsefficientparsing;theO(n4)parsingalgorithmispresentedinSection4.1-Endpoint-Crossingtreesareasubclassof2-planargraphs(Section5.1),aclassthathasbeenstudied

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

e
d
toi

/
t

un
c
je
/

je

un
r
t
je
c
e
–
p
d

F
/

d
o

je
/

.

1
0
1
1
6
2

/
t

je

un
c
_
un
_
0
0
2
0
6
1
5
6
6
6
3
9

/

/
t

je

un
c
_
un
_
0
0
2
0
6
p
d

.

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

14

inNLP.1-Endpoint-Crossingtreesalsohavesomelinguisticinterpretation(pairsofcrossserialverbsproduce1-Endpoint-Crossingtrees,Section5.2).2DefinitionsofNon-ProjectivityDefinition1.Edgeseandfcrossifeandfhavedistinctendpointsandexactlyoneoftheendpointsoffliesbetweentheendpointsofe.Definition2.Adependencytreeis1-Endpoint-Crossingifforanyedgee,alledgesthatcrosseshareanendpointp.Table1showsthepercentageofdependencyparsesintheCoNLL-Xtrainingsetsthatare1-Endpoint-Crossingtrees.Acrosssixlanguageswithvaryingamountsofnon-projectivity,95.8-99.8%ofdependencyparsesintreebanksare1-Endpoint-Crossingtrees.1Wenextreviewandcompareotherrelevantdef-initionsofnon-projectivityfrompriorwork:well-nestedwithblockdegree2,gap-minding,projective,and2-planar.Thedefinitionsofblockdegreeandwell-nestednessaregivenbelow:Definition3.Foreachnodeuinthetree,ablockofthenodeis“alongestsegmentconsistingofdescen-dantsofu.”(Kuhlmann,2013).Theblock-degreeofuis“thenumberofdistinctblocksofu”.Theblockdegreeofatreeisthemaximumblockdegreeofanyofitsnodes.Thegapdegreeisthenumberofgapsbetweentheseblocks,andsobydefinitionisonelessthantheblockdegree.(Kuhlmann,2013)Definition4.Twotrees“T1andT2interleaveifftherearenodesl1,r1∈T1andl2,r2∈T2suchthatl1l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . e d u / t a c l / l a r t i c e - p d f / d o i / . 1 0 1 1 6 2 / t l a c _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 p d . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 15 ArabicCzechDanishDutchPortugueseSwedishParsing1-Endpoint-Crossing1457(99.8)71810(98.8)5144(99.1)12785(95.8)9007(99.3)10902(98.7)Ô(n4)Well-nested,blockdegree21458(99.9)72321(99.5)5175(99.7)12896(96.6)8650(95.4)10955(99.2)Ô(n7)Gap-Minding1394(95.5)70695(97.2)4985(96.1)12068(90.4)8481(93.5)10787(97.7)Ô(n5)Projective1297(88.8)55872(76.8)4379(84.4)8484(63.6)7353(81.1)9963(90.2)Ô(n3)Sentences146072703519013349907111042Table1:Over95%ofthedependencyparsetreesintheCoNLL-Xtrainingsetsare1-Endpoint-Crossingtrees.Coveragestatisticsandparsingtimesofpreviouslyproposedpropertiesareshownforcomparison.Definition8.Withina1-Endpoint-Crossingtree,le(crossing)pencil2ofanedgee(P.(e))isdefinedasthesetofedges(sharinganendpoint)thatcrosse.The(crossingpencil)pointofanedgee(Pt(e))isdefinedastheendpointthatalledgesinP(e)share.Wewilluseeuvtoindicateanedgeineitherdirec-tionbetweenuandv,i.e.,eitheru→voru←v.Beforedefiningtheparsingalgorithm,wefirstgivesomeintuitionbyanalogytoparsingforpro-jectivetrees.(ThisargumentmirrorsthatofEisner(2000,pps.38-39).)Projectivetreescanbeproducedusingdynamicprogrammingoverintervals.Inter-valsaresufficientforprojectivetrees:consideranyedgeeuvinaprojectivetree.Theverticesin(toi,v)mustonlyhaveedgestoverticesin[toi,v].Iftherewereanedgebetweenavertexin(toi,v)andavertexoutside[toi,v],suchanedgewouldcrosseuv,whichwouldcontradicttheassumptionofprojectivity.Thuseveryedgeinaprojectivetreecreatesoneinteriorintervalisolatedfromtherestofthetree,allowingdynamicprogram-mingoverintervals.Wecananalyzethecaseof1-Endpoint-Crossingtreesinasimilarfashion:Definition9.Anisolatedinterval[je,j]hasnoedgesbetweentheverticesin(je,j)andtheverticesout-sideof[je,j].Anintervalandoneexteriorvertex[je,j]∪{X}iscalledanisolatedcrossingregionifthefollowingtwoconditionsaresatisfied:1.Therearenoedgesbetweenthevertices∈(je,j)andvertices/∈[je,j]∪{X}2.Noneoftheedgesbetweenxandvertices∈(je,j)arecrossedbyanyedgeswithbothend-points∈(je,j)2Thisnotationcomesfromananalogytogeometry:“Asetofdistinct,coplanar,concurrentlinesisapenciloflines”(Rin-genberg,1967,p.221);concurrentlinesallintersectatthesamesinglepoint.uvp(un)[toi,v]∪{p}uvp(b)[v,p]∪{toi}upv(c)[toi,p]∪{v}upv(d)[p,v]∪{toi}Figure2:AnedgeeuvandPt(euv)=pformtwosetsofisolatedcrossingregions(Lemma1).2aand2bshowp/∈(toi,v);2cand2dshowp∈(toi,v).Lemma1.ConsideranyedgeeuvandPt(euv)=pina1-Endpoint-CrossingforestF.Letl,r,andmdenotetheleftmost,rightmost,andmiddlepointoutof{toi,v,p},respectively.Thenthethreepointsu,v,andpdefinetwoisolatedcrossingregions:(1)[je,m]∪{r},et(2)[m,r]∪{je}.Proof.Firstnotethatasp=Pt(euv),P.(euv)isnon-empty:theremustbeatleastoneedgebetweenvertices∈(toi,v)andvertices/∈[toi,v].piseither/∈[toi,v](i.e.,p=l∨p=r)or∈(toi,v)(i.e.,p=m):Case1:p=l∨p=r:Assumewithoutlossofgeneralitythatux/∈[toi,v]∪{p}.Thensuchanedgewouldcrosseuvwithouthavinganendpointatp,whichcontradictsthe1-Endpoint-Crossingprop-ertyforeuv.Condition2:Assumethatforsomeepasuchthata∈(toi,v),epawascrossedbyanedgeintheinteriorof(toi,v).Theinterioredgewouldnotshareanend-pointwitheuv;sinceeuvalsocrossesepa,thiscon-tradictsthe1-Endpoint-Crossingpropertyforepa. l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . e d u / t a c l / l a r t i c e - p d f / d o i / . 1 0 1 1 6 2 / t l a c _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 p d . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 16 (b)[v,p]∪{toi}isanisolatedcrossingregion(Figure2b):Condition1:Assumetherewereanedgeeabwitha∈(v,p)andb/∈[v,p]∪{toi}.bcannotbein(toi,v)(byabove).Ainsi,b/∈[toi,p],whichimpliesthateabcrossestheedgesinP(euv);aseuvdoesnotshareavertexwitheab,thiscontra-dictsthe1-Endpoint-CrossingpropertyforalledgesinP(euv).Condition2:Assumethatforsomeeuasuchthata∈(v,p),euawascrossedbyanedgeintheinteriorof(v,p).euawouldalsobecrossedbyalltheedgesinP(euv);astheinterioredgewouldnotshareanendpointwithanyoftheedgesinP(euv),thiswouldcontradictthe1-Endpoint-Crossingpropertyforeua.Case2:p=m:(un)[toi,p]∪{v}isanisolatedcrossingregion(Figure2c):Condition1:Assumetherewereanedgeeabwitha∈(toi,p)andb/∈[toi,p]∪{v}(b∈(p,v)∨b/∈[toi,v]).Firstassumeb∈(p,v).TheneabcrossesalledgesinP(euv);aseabdoesnotshareanendpointwitheuv,thiscontradictsthe1-Endpoint-CrossingpropertyfortheedgesinP(euv).Nextassumeb/∈[toi,v].Theneabcrosseseuv;sincea6=p∧b6=p,thisviolatesthe1-Endpoint-Crossingpropertyforeuv.Condition2:Assumethatforsomeevawitha∈(toi,p),evawascrossedbyanedgeintheinteriorof(toi,v).evaisalsocrossedbyalltheedgesinP(euv);astheinterioredgewillnotshareanendpointwiththeedgesinP(euv),thiscontradictsthe1-Endpoint-Crossingpropertyforeva.(b)[p,v]∪{toi}isanisolatedcrossingregion(Figure2d):Symmetrictotheabove.4ParsingAlgorithmTheoptimal1-Endpoint-Crossingtreecanbefoundusingadynamicprogrammingalgorithmthatex-ploitsthefactthatedgesandtheircrossingpointsdefineintervalsandisolatedcrossingregions.Thissectionassumesanarc-factoredmodel,inwhichthescoreofatreeisdefinedasthesumofthescoresofitsedges;scoringfunctionsforedgesaregenerallylearnedfromdata.(un)Onlyedgesinci-denttotheLeftpointoftheintervalmaycrosstheedgesfromtheexteriorpoint(b)Onlyedgesin-cidenttotheRightpointoftheinter-valmaycrosstheedgesfromtheexte-riorpoint(c)les deux(LR)(d)NeitherFigure3:Isolatedcrossingregionsub-problems.Thedynamicprogramusesfivetypesofsub-problems:intervalsub-problemsforeachinterval[je,j],denotedInt[je,j],andfourtypesofisolatedcrossingregionsub-problemsforeachintervalandexteriorpoint[je,j]∪{X},whichdifferinwhetheredgesfromtheexteriorpointmaybecrossedbyedgeswithanendpointattheLeftpointoftheinter-val,theRightpoint,bothLR,orNeither(Figure3).L[je,j,X],forexample,referstoanisolatedcrossingregionovertheinterval[je,j]withanexteriorpointofx,inwhichedgesincidenttoi(theleftboundarypoint)cancrossedgesbetweenxand(je,j).Thesedistinctionsallowthe1-Endpoint-Crossingpropertytobegloballyenforced;crossingedgesinoneregionmayconstrainedgesinanother.Forex-ample,considerthatFigure2aallowsedgeswithanendpointatvtocrosstheedgesfromp,whileFigure2ballowsedgesfromuinto(v,p).Bothsimultane-ouslywouldcausea1-Endpoint-CrossingviolationfortheedgesinP(euv).Figures4and5showvalidcombinationsofthesub-problemsinFigure3.ThefulldynamicprogramisshowninAppendixA.Thefinalanswermustbeavaliddependencytree,whichrequireseachwordtohaveexactlyoneparentandprohibitscycles.Weusebooleans(bi,bj,bx)foreachsub-problem,inwhichthebooleanissettotrueifandonlyifthesolutiontothesub-problemmustcontaintheincoming(parent)edgeforthecorre-spondingboundarypoint.WeusethesuffixAFromBforasub-problemtoenforcethataboundarypointAmustbedescendedfromboundarypointB(toavoidcycles).Wewilloccasionallymentiontheseissues, l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . e d u / t a c l / l a r t i c e - p d f / d o i / . 1 0 1 1 6 2 / t l a c _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 p d . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 17 (un)Ifl∈(k,j]:kilj(b)Ifl∈(je,k):likj(je)Ifthedashededgeexists:Alltheedgesfromlinto(je,k)mustchoosekastheirPt.TheintervaldecomposesintoS[eik]+R.[je,k,je]+Int[k,je]+L[je,j,k]:kilj(ii)Ifnoedgeslikethedashededgeexist:Alledgesfromlinto(je,k)maychooseeitheriorkastheirPt.TheintervaldecomposesintoS[eik]+LR[je,k,je]+Int[k,je]+Int[je,j]:iklj(je)Ifdashededgeexists:Alltheedgesfromlinto(k,j]mustchooseiastheirPt.Theintervaldecom-posesintoS[eik]+Int[je,je]+L[je,k,je]+N[k,j,je]:likj(ii)Ifnoedgeslikethedashededgeexist:AlledgesfromlmaychoosekastheirPt.Theintervaldecom-posesintoS[eik]+R.[je,je,k]+Int[je,k]+L[k,j,je]:likjFigure4:DecomposinganInt[je,j]sub-problem,withPt(eik)=lbutforsimplicityfocusthediscussiononthedecom-positionintocrossingregionsandthemaintenanceofthe1-Endpoint-Crossingproperty.Edgedirectiondoesnotaffectthesepointsoffocus,andsowewillrefersimplytoS[euv]tomeanthescoreofeithertheedgefromutovorvice-versa.Inthefollowingsubsections,weshowthattheop-timalparseforeachtypeofsub-problemcanbede-composedintosmallervalidsub-problems.Ifwetakethemaximumoverallthesepossiblecombina-tionsofsmallersolutions,wecanfindthemaximumscoringparseforthatsub-problem.Notethattheoveralltreeisavalidsub-problem(overtheinter-val[0,n]),sotheargumentwillalsoholdforfindingtheoptimaloveralltree.Eachindividualvertexandeachpairofadjacentvertices(withnoedges)triv-iallyformisolatedintervals(asthereisnointerior);thisformsthebasecaseofthedynamicprogram.TheoveralldynamicprogramtakesO(n4)temps:thereareO(n2)intervalsub-problems,eachofwhichneedstwofreesplitpointstofindthemax-imum,andO(n3)regionsub-problems,eachofwhichisamaximizationoveronefreesplitpoint.4.1DecomposinganIntsub-problemConsideranisolatedintervalsub-problemInt[je,j].Therearethreecases:(1)therearenoedgesbetweeniandtherestoftheinterval,(2)thelongestedgein-cidenttoiisnotcrossed,(3)thelongestedgeinci-denttoiiscrossed.AnIntsub-problemcanbede-composedintosmallervalidsub-problemsineachofthesethreecases.FindingtheoptimalIntforestcanbedonebytakingthemaximumoverthesecases:Noedgesbetweeniand[i+1,j]:ThesamesetofedgesisalsoavalidInt[i+1,j]sub-problem.bimustbetruefortheInt[i+1,j]sub-problemtoensurei+1receivesaparent.Furthestedgefromiisnotcrossed:Ifthefurthestedgeistoj,theproblemcanbedecomposedintoS[eij]+Int[je,j],asthatedgehasnoeffectontheinterioroftheinterval.Clearly,thisisonlyappli-cableiftheboundarypointneededaparent(asin-dicatedbythebooleans)andthebooleanmustthenbeupdatedaccordingly.Ifthefurthestedgeistosomekin(je,j),theproblemisdecomposedintoS[eik]+Int[je,k]+Int[k,j].Furthestedgefromiiscrossed:Thisisthemost l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . e d u / t a c l / l a r t i c e - p d f / d o i / . 1 0 1 1 6 2 / t l a c _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 p d . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 18 interestingcase,whichusestwosplitpoints:theotherendpointoftheedge(k),andl=Pt(eik).Thedynamicprogramdependsontheorderofkandl.l/∈(je,k)(Figure4a):ByLemma1,[je,k]∪{je}et[k,je]∪{je}formisolatedregions.(je,j]istheremain-deroftheinterval,andtheonlyvertexfrom[je,je)thatcanhaveedgesinto(je,j]isk:(je,k)et(k,je)arepartofisolatedregions,andiisruledoutbecausekwasi’sfurthestneighbor.Ifatleastoneedgefromkinto(je,j](thedashedlineinFigure4a)exists,thedecompositionisasinFigure4a,Casei;otherwise,itisasinFigure4a,Caseii.InCasei,eikandtheedge(s)betweenkand(je,j]forcealloftheedgesbetweenland(je,k)tohavekastheirPt.Thus,theregion[je,k]∪{je}mustbeasub-problemoftypeR(Figure3b),astheseedgesfromlcanonlybecrossedbyedgeswithanendpointatk(therightendpointof[je,k]).Alloftheedgesbetweenkand(je,j]havelastheirPt,astheyarecrossedbyalltheedgesinP(eik),andsothesub-problemcorrespondingtotheregion[je,j]∪{k}isoftypeL(Figure3a).InCaseii,eachoftheedgesinP(eik)maychooseeitheriorkastheirPt,sothesub-problem[je,k]∪{je}isoftypeLR(Figure3c).Notethatl=jisaspecialcaseofCaseiiinwhichtherightmostintervalInt[je,j]isempty.l∈(je,k)(Figure4b):[je,je]∪{k}et[je,k]∪{je}formisolatedcrossingregionsbyLemma1.Therecannotbothbeedgesbetweeniand(je,k)andbe-tweenkand(je,je),asthiswouldviolate1-Endpoint-CrossingfortheedgesinP(eik).Ifthereareanyedgesbetweeniand(je,k)(i.e.,CaseiinFigure4b),thenalloftheedgesinP(eik)mustchooseiastheirPt,andsotheseedgescannotbecrossedatallintheregion[k,j]∪{je},andtherecannotbeanyedgesfromkinto(je,je).Iftherearenosuchedges(Caseiiin4b),thenkmustbeavalidPtforalledgesinP(eik),andsotherecanbothbeedgesfromkinto(je,je)et[k,j]∪{je}maybeoftypeL(allowingcrossingswithanendpointatk).4.2DecomposinganLRsub-problemAnLRsub-problemisoveranisolatedcrossingre-gion[je,j]∪{X},suchthatedgesfromxinto(je,j)maybecrossedbyedgeswithanendpointateitheriorj.Thissub-problemisonlydefinedwhenneitherinorjgettheirparentfromthissub-problem.Fromatop-downperspective,thiscaseisonlyusedwhentherewillbeanedgebetweeniandj(asinoneofthesub-problemsinFigure4a,Caseii).Ifnoneoftheedgesfromxarecrossedbyanyedgeswithanendpointati,thiscanbeconsideredanRproblem.Similarly,ifnonearecrossedbyanyedgeswithanendpointatj,thismaybeconsideredanLsub-problem.Theonlycasewhichneedsdis-cussioniswhenbothedgeswithanendpointatiandalsoatjcrossedgesfromx;seeFigure3cforaschematic.Inthatscenario,theremustexistasplitpointsuchthat:(1)totheleftofthepoint,alledgescrossingx-edgeshaveanendpointati,andtotherightofthepoint,allsuchedgeshaveanendpointatj,et(2)noedgesintheregioncrossthesplitpoint.Letribei’srightmostchildin(je,j);letljbej’sleftmostchildin(je,j).Everyedgefromxinto(je,ri)iscrossedbyeiri;everyedgebetweenxand(lj,j)iscrossedbyeljj.eiricannotcrosseljj,asthatwouldeitherviolate1-Endpoint-Crossing(be-causeofthex-interioredges)orcreateacycle(ifbothchildrenarealsoconnectedbyanedgetox).riandljalsocannotbeequal:asneitherinorjmaybeassignedaparent,theymustbothbeinthedirec-tionofthechild,andthechildcannothavemultipleparents.Thus,riistotheleftoflj.Anysplitpointbetweenriandljclearlysatis-fies(1).Thereisatleastonepointwithin[ri,lj]thatsatisfies(2)aslongasthereisnotachainofcrossingedgesfromeiritoeljj.Theproofisomittedforspacereasons,butsuchachaincanberuledoutusingacountingargumentsimilartothatintheproofinSection5.1.Thedecompositionis:L[je,k,X]+R.[k,j,X]forsomek∈(je,j).4.3DecomposinganNsub-problemConsiderthemaximumscoringforestoftypeNover[je,j]∪{X}(Figure3d;noedgesfromxarecrossedinthissub-problem).Iftherearenoedgesfromx,thenitisalsoavalidInt[je,j]sub-problem.Ifthereareedgesbetweenxandtheendpointsiorj,thentheforestwiththatedgeremovedisstillavalidNsub-problem(withtheancestorandparentbook-keepingupdated).Otherwise,ifthereareedgesbe-tweenxand(je,j),choosetheneighborofxclosesttoj(callitk).Sincetheedgeexkisnotcrossed,therearenoedgesfrom[je,k)into(k,j];sincekwastheneighborofxclosesttoj,therearenoedgesfromxinto(k,j].Ainsi,theregiondecomposesinto l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . e d u / t a c l / l a r t i c e - p d f / d o i / . 1 0 1 1 6 2 / t l a c _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 p d . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 19 xkji(je)Ifdashededgeexists:Alltheedgesfromiinto(k,j]mustchoosexastheirPt.Theintervaldecom-posesintoS[exk]+L[je,k,X]+N[k,j,je]:xkji(ii)Ifnoedgeslikethedashededgeexist:Edgesfromiinto(k,j]maychoosekastheirPt.Thein-tervaldecomposesintoS[exk]+Int[je,k]+L[k,j,je]:xkjiFigure5:AnLsub-problemover[je,j]∪{X},kistheneighborofxfurthestfromiintheinterval.S[eik]+Int[k,j]+N[je,k,X].Asanaside,ifbxwastrue(xneededaparentfromthissub-problem),andkwasachildofx,thenx’sparentmustcomefromthe[je,k]∪{X}sub-problem.However,itcannotbeadescendantofk,asthatwouldcauseacycle.Thusinthiscase,wecallthesub-problemaN_XFromIproblem,toin-dicatethatxneedsaparent,iandkdonot,andxmustbedescendedfromi,notk.4.4DecomposinganLorRsub-problemAnLsub-problemover[je,j]∪{X}requiresthatanyedgesinthisregionthatcrossanedgewithanend-pointatxhaveanendpointati(theleftendpoint).Iftherearenoedgesbetweenxand[je,j]inanLsub-problem,thenitisalsoavalidIntsub-problemover[je,j].Ifthereareedgesbetweenxandiorj,thenthesub-problemcanbedecomposedintothatedgeplustherestoftheforestwiththatedgeremoved.Theinterestingcaseiswhenthereareedgesbe-tweenxandtheinterior(Figure5).Letkbetheneighborofxwithin(je,j)thatisfurthestfromi.Asalledgesthatcrossexkwillhaveanendpointati,therearenoedgesbetween(je,k)et(k,j].Com-binedwiththefactthatkwastheneighborofxclos-esttoj,wehavethat[je,k]∪{X}mustformaniso-abcdefFigure6:2-planarbutnot1-Endpoint-Crossinglatedcrossingregion,asmust[k,j]∪{je}.Ifthereareadditionaledgesbetweenxandthein-terior(Caseiin5),alloftheedgesfromiinto(k,j]crossboththeedgeexkandtheotheredgesfromxinto(je,k).ThePtforalltheseedgesmustthere-forebex,andasxisnotintheregion[k,j]∪{je},thoseedgescannotbecrossedatallinthatregion(c'est à dire.,[k,j]∪{je}mustbeoftypeN).Iftherearenoadditionaledgesfromxinto(je,k)(CaseiiinFig-ure5),thenalloftheedgesfromiinto(k,j)mustchooseeitherxorkastheirPt.Astherewillbenomoreedgesfromx,choosingkastheirPtallowsstrictlymoretrees,andso[k,j]∪{je}canbeoftypeL(allowingedgesfromitobecrossedinthatregionbyedgeswithanendpointatk).AnRsub-problemisidentical,withkinsteadchosentobetheneighborofxfurthestfromj.5Connections5.1GraphTheory:All1-Endpoint-CrossingTreesare2-PlanarThe2-planarcharacterizationofdependencystruc-turesinGómez-RodríguezandNivre(2010)exactlycorrespondto2-pagebookembeddingsingraphthe-ory:anembeddingoftheverticesinagraphontoaline(byanalogy,alongthespineofabook),andtheedgesofthegraphontooneof2(moregener-ally,k)half-planes(pagesofthebook)suchthatnoedgesonthesamepagecross(BernhartandKainen,1979).Theproblemoffindinganembeddingthatminimizesthenumberofpagesrequiredisanaturalformulationofmanyproblemsarisingindisparateareasofcomputerscience,forexample,sortingase-quenceusingtheminimumnumberofstacks(EvenandItai,1971),orconstructingfault-tolerantlayoutsinVLSIdesign(Chungetal.,1987).Inthissectionweprove1-Endpoint-Crossing⊆2-planar.Theseclassesarenotequal(Figure6).Wefirstprovesomepropertiesaboutthecrossingsgraphs(Gómez-RodríguezandNivre,2010)of1-Endpoint-Crossingtrees.Thecrossingsgraphofa l D o w n o a d e d f r o m h t t p : / / d i r e c t . m i t . e d u / t a c l / l a r t i c e - p d f / d o i / . 1 0 1 1 6 2 / t l a c _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t l a c _ a _ 0 0 2 0 6 p d . f b y g u e s t t o n 0 8 S e p e m b e r 2 0 2 3 20 (un,b)(un,c)(b,d)(c,e)(d,F)(un)(un,b)(un,c)(b,e)(g,d)(h,F)(b,g)(g,h)(b)Figure7:ThecrossinggraphsforFigures1aand1b.graphhasavertexcorrespondingtoeachedgeintheoriginal,andanedgebetweentwoverticesifthetwoedgestheycorrespondtocross.ThecrossingsgraphsforthedependencytreesinFigures1aand1bareshowninFigures7aand7b,respectively.Lemma2.No1-Endpoint-Crossingtreehasacycleoflength3initscrossingsgraph.Proof.Assumethereexistedacyclee1,e2,e3.e1ande3mustshareanendpoint,astheybothcrosse2.Sincee1ande3shareanendpoint,e1ande3donotcross.Contradiction.Lemma3.Anyoddcycleofsizen(n≥4)inacrossingsgraphofa1-Endpoint-Crossingtreeusesatmostndistinctverticesintheoriginalgraph.Proof.Lete1,e2,...,enbeanoddcycleinacross-ingsgraphofa1-Endpoint-Crossingtreewithn≥4.Sincen≥4,e1,e2,en−1,andenaredistinctedges.Letabethevertexthate1anden−1share(becausetheybothcrossen)andletbbethevertexthate2andenshare(bothcrosse1).Notethate1anden−1cannotcontainbandthate2andencannotcontaina(otherwisetheywouldnotcrossanedgeadjacenttothemalongthecycle).Wewillnowconsiderhowmanyverticeseachedgecanintroducethataredistinctfromallverticespreviouslyseeninthecycle.e1ande2necessarilyintroducetwodistinctverticeseach.Leteobethefirstoddedgethatcontainsb(weknowoneexistssinceencontainsb).(oisatleast3,sincee1doesnotcontainb.)eo’sothervertexmustbetheonesharedwitheo−2(eo−2doesnotcontainb,sinceeowasthefirstoddedgetocontainb).There-fore,bothofeo’sverticeshavealreadybeenseenalongthecycle.Similarly,leteebethefirstevenedgethatcon-tainsana.Bythesamereasoning,eemustnotin-troduceanynewvertices.Allotheredgeseisuchthati>2andei6=eoandei6=eeintroduceatmostonenewvertex,sinceonemustbesharedwiththeedgeei−2.Therearen−4suchedges.Countingupallpossibilities,themaximumnum-berofdistinctverticesis4+(n−4)=n.Theorem1.1-Endpoint-Crossingtrees⊆2-planar.Proof.Assumethereexistedanoddcycleinthecrossingsgraphofa1-Endpoint-Crossingtree.Thecyclehassizeatleast5(byLemma2).Thereareatleastasmanyedgesasverticesinthesubgraphoftheforestinducedbytheverticesusedinthecycle(byLemma3).Thatimpliestheexistenceofacycleintheoriginalgraph,contradictingthattheoriginalgraphwasatree.Sincetherearenooddcyclesinthecrossingsgraph,thecrossingsgraphofedgesisbipartite.Eachsideofthebipartitegraphcanbeassignedtoapage,suchthatnotwoedgesonthesamepagecross.Therefore,theoriginalgraphwas2-planar.5.2Linguistics:Cross-serialVerbConstructionsandSuccessiveCyclicityCross-serialverbconstructionswereusedtoprovideevidenceforthe“non-context-freeness”ofnaturallanguage(Shieber,1985).Cross-serialverbcon-structionswithtwoverbsform1-Endpoint-Crossingtrees.Belowisacross-serialsentencefromSwiss-German,depuis(1)inShieber(1985):dasmeremHanseshuushälfedaastriichethatweHansDATthehouseACChelpedpaintTheedges(que,helped),(helped,nous),et(helped,Hans)areeachonlycrossedbyanedgewithanendpointatpaint;theedge(paint,maison)isonlycrossedbyedgeswithanendpointathelped.Moregenerally,withasetoftwocrossserialverbsinasubordinateclause,eachverbshouldsufficeasthecrossingpointforalledgesincidenttotheotherverbthatarecrossed.Cross-serialconstructionswiththreeormoreverbswouldhavedependencytreesthatviolate1-

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

e
d
toi

/
t

un
c
je
/

je

un
r
t
je
c
e
–
p
d

F
/

d
o

je
/

.

1
0
1
1
6
2

/
t

je

un
c
_
un
_
0
0
2
0
6
1
5
6
6
6
3
9

/

/
t

je

un
c
_
un
_
0
0
2
0
6
p
d

.

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

21

WhatdidsayBAC…Zatet?nsaid1said2t1t2Figure8:Anexampleofwh-movementoverapoten-tiallyunboundednumberofclauses.Theedgesbe-tweentheheadsofeachclausecrosstheedgesfromtracetotrace,butallobey1-Endpoint-Crossing.Endpoint-Crossing.Psycholinguistically,betweentwoandthreeverbsisexactlywherethereisalargechangeinthesentenceprocessingabilitiesofhumanlisteners(basedonbothgrammaticaljudgmentsandscoresonacomprehensiontask)(Bachetal.,1986).Morespeculatively,theremaybeaconnectionbetweentheformof1-Endpoint-Crossingtreesandphases(roughly,propositionalunitssuchasclauses)inMinimalism(Chomskyetal.,1998).Figure8showsanexampleofwh-movementoverapoten-tiallyunboundednumberofclauses.Thephase-impenetrabilitycondition(PIC)statesthatonlytheheadofthephaseandelementsthathavemovedtoitsedgeareaccessibletotherestofthesentence(Chomskyetal.,1998,p.22).Movementisthere-forerequiredtobesuccessivecyclic,withamovedelementleavingachainoftracesattheedgeofeachclauseonitswaytoitsfinalpronouncedloca-tion(Chomsky,1981).InFigure8,noticethatthecrossingedgesformarepeatedpatternthatobeysthe1-Endpoint-Crossingproperty.Moregenerally,wesuspectthattreessatisfyingthePICwilltendtoalsobe1-Endpoint-Crossing.Furthermore,ifthetraceswerenotattheedgeofeachclause,andin-steadwerepositionedbetweenaheadandoneofitsarguments,1-Endpoint-Crossingwouldbevio-lated.Forexample,ift2inFigure8werebe-tweenCandsaid2,thentheedge(t1,t2)wouldcross(say,said1),(said1,said2),et(C,said2),whichdonotallshareanendpoint.Anexplorationoftheselinguisticconnectionsmaybeaninterestingavenueforfurtherresearch.6Conclusions1-Endpoint-Crossingtreescharacterizeover95%ofstructuresfoundinnaturallanguagetreebank,andcanbeparsedinonlyafactorofnmoretimethanprojectivetrees.Thedynamicprogrammingalgo-rithmforprojectivetrees(Eisner,2000)hasbeenextendedtohandlehigherorderfactors(McDonaldandPereira,2006;Carreras,2007;KooandCollins,2010),addingatmostafactorofntotheedge-basedrunningtime;itwouldbeinterestingtoex-tendthealgorithmpresentedheretoincludehigherorderfactors.1-Endpoint-Crossingisaconditiononedges,whilepropertiessuchaswell-nestednessorblockdegreeareframedintermsofsubtrees.Threeedgeswillalwayssufficeasacertificateofa1-Endpoint-Crossingviolation(twovertex-disjointedgesthatbothcrossathird).Incontrast,forapropertylikeill-nestedness,twonodesmighthavealeastcommonancestorarbitrarilyfaraway,andsoonemightneedtheentiregraphtoverifywhetherthesub-treesrootedatthosenodesaredisjointandill-nested.Wehavediscussedcross-serialdepen-dencies;afurtherexplorationofwhichlinguisticphenomenawouldandwouldnothave1-Endpoint-Crossingdependencytreesmayberevealing.AcknowledgmentsWewouldliketothankJulieLegateforanin-terestingdiscussion.ThismaterialisbaseduponworksupportedunderaNationalScienceFoun-dationGraduateResearchFellowship,NSFAwardCCF1137084,andArmyResearchOfficeMURIgrantW911NF-07-1-0216.ADynamicProgramtofindthemaximumscoring1-Endpoint-CrossingTreeInput:MatrixS:S[je,j]isthescoreofthedirectededge(je,j)Output:Maximumscoreofa1-Endpoint-Crossingtreeoververtices[0,n],rootedat0Init:∀iInt[je,je,F,F]=Int[je,i+1,F,F]=0Int[je,je,T,F]=Int[je,je,F,T]=Int[je,je,T,T]=−∞Final:Int[0,n,F,T]Shorthandforbooleans:TF(X,S):=ifx=T,exactlyoneofthesetSistrueifx=F,allofthesetSmustbefalsebi,bj,bxaretrueiffthecorrespondingboundarypointhasitsincomingedge(parent)inthatsub-problem.FortheLRsub-problem,biandbjarealwaysfalse,andsoomitted.Forallsub-problemswiththesuffixAFromB,theboundarypointAhasitsparentedgeinthesub-problemsolution;theothertwoboundarypointsdonot.Forexample,L_XFromIwouldcor-respondtohavingbooleansbi=bj=Fandbx=T,withtherestrictionthatxmustbeadescendantofi.

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

e
d
toi

/
t

un
c
je
/

je

un
r
t
je
c
e
–
p
d

F
/

d
o

je
/

.

1
0
1
1
6
2

/
t

je

un
c
_
un
_
0
0
2
0
6
1
5
6
6
6
3
9

/

/
t

je

un
c
_
un
_
0
0
2
0
6
p
d

.

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

22

Int[je,j,F,bj]←maxInt[i+1,j,T,F]ifbj=FS[je,j]+Int[je,j,F,F]ifbj=Tmaxk∈(je,j)S[je,k]+Int[je,k,F,F]+Int[k,j,F,bj]maxTF(bj,{bl,br})LR[je,k,j,bl]+Int[k,j,F,br]maxl∈(k,j),TF(T,{bl,bm,br})(cid:26)R.[je,k,je,F,F,bl]+Int[k,je,F,bm]+L[je,j,k,br,bj,F]LR[je,k,je,bl]+Int[k,je,F,bm]+Int[je,j,br,bj]maxl∈(je,k),TF(T,{bl,bm,br})(cid:26)Int[je,je,F,bl]+L[je,k,je,bm,F,F]+N[k,j,je,F,bj,br]R.[je,je,k,F,bl,F]+Int[je,k,bm,F]+L[k,j,je,F,bj,br]Int[je,j,T,F]←symmetrictoInt[je,j,F,T]Int[je,j,T,T]←−∞LR[je,j,X,bx]←maxL[je,j,X,F,F,bx]R.[je,j,X,F,F,bx]maxk∈(je,j),TF(bx,{bxl,bxr}),TF(T,{bkl,bkr})L[je,k,X,F,bkl,bxl]+R.[k,j,X,bkr,F,bxr]N[je,j,X,bi,bj,F]←maxInt[je,j,bi,bj]S[X,je]+N[je,j,X,F,bj,F]ifbi=TS[X,j]+N[je,j,X,bi,F,F]ifbj=Tmaxk∈(je,j)S[X,k]+N[je,k,X,bi,F,F]+Int[k,j,F,bj]N[je,j,X,F,bj,T]←maxS[je,X]+N[je,j,X,F,bj,F]S[X,j]+N_XFromI[je,j,X]ifbj=TS[j,X]+N[je,j,X,F,F,F]ifbj=FS[j,X]+Int[je,j,F,T]ifbj=Tmaxk∈(je,j)S[X,k]+N_XFromI[je,k,X]+Int[k,j,F,bj]maxk∈(je,j)S[k,X]+(cid:26)Int[je,k,F,T]+Int[k,j,F,bj]N[je,k,X,F,F,F]+Int[k,j,T,bj]N[je,j,X,T,F,T]←symmetrictoN[je,j,X,F,T,T]N[je,j,X,T,T,T]←−∞N_XFromI[je,j,X]←maxS[je,X]+N[je,j,X,F,F,F]maxk∈(je,j)(cid:26)S[X,k]+N_XFromI[je,k,X]+Int[k,j,F,F]S[k,X]+Int[je,k,F,T]+Int[k,j,F,F]N_IFromX[je,j,X]←max(S[X,je]+N[je,j,X,F,F,F]maxk∈(je,j)S[X,k]+N[je,k,X,T,F,F]+Int[k,j,F,F]N_XFromJ[je,j,X]←symmetrictoN_XFromI[je,j,X]N_JFromX[je,j,X]←symmetrictoN_IFromX[je,j,X]L[je,j,X,bi,bj,F]←maxInt[je,j,bi,bj]S[X,je]+L[je,j,X,F,bj,F]ifbi=TS[X,j]+L[je,j,X,bi,F,F]ifbj=Tmaxk∈(je,j),TF(bi,{bl,br})S[X,k]+(cid:26)L[je,k,X,bl,F,F]+N[k,j,je,F,bj,br]Int[je,k,bl,F]+L[k,j,je,F,bj,br]L[je,j,X,F,bj,T]←maxS[je,X]+L[je,j,X,F,bj,F]S[X,j]+L_XFromI[je,j,X]ifbj=TS[j,X]+L[je,j,X,F,F,F]ifbj=FS[j,X]+L_JFromI[je,j,X]ifbj=Tmaxk∈(je,j)S[X,k]+L_XFromI[je,k,X]+N[k,j,je,F,bj,F]maxk∈(je,j)S[k,X]+L_JFromI[je,k,X]+N[k,j,je,F,bj,F]L[je,k,X,F,F,F]+N[k,j,je,T,bj,F]maxTF(T,{bl,br})Int[je,k,F,bl]+L[k,j,je,br,bj,F]L[je,j,X,T,bj,T]←notreachableL_XFromI[je,j,X]←maxS[je,X]+L[je,j,X,F,F,F]maxk∈(je,j)S[X,k]+L_XFromI[je,k,X]+N[k,j,je,F,F,F]maxk∈(je,j)S[k,X]+L_JFromI[je,k,X]+N[k,j,je,F,F,F]L[je,k,X,F,F,F]+N_IFromX[k,j,je]Int[je,k,F,T]+L[k,j,je,F,F,F]Int[je,k,F,F]+L_IFromX[k,j,je]L_IFromX[je,j,X]←maxS[X,je]+L[je,j,X,F,F,F]maxk∈(je,j)S[X,k]+L[je,k,X,T,F,F]+N[k,j,je,F,F,F]L[je,k,X,F,F,F]+N_XFromI[k,j,je]Int[je,k,T,F]+L[k,j,je,F,F,F]Int[je,k,F,F]+L_XFromI[k,j,je]L_JFromX[je,j,X]←maxS[X,j]+L[je,j,X,F,F,F]maxk∈(je,j)S[X,k]+(cid:26)L[je,k,X,F,F,F]+Int[k,j,F,T]Int[je,k,F,F]+L_JFromI[k,j,je]L_JFromI[je,j,X]←maxInt[je,j,F,T]maxk∈(je,j)S[X,k]+(cid:26)L[je,k,X,F,F,F]+N_JFromX[k,j,je]Int[je,k,F,F]+L_JFromX[k,j,je]

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

e
d
toi

/
t

un
c
je
/

je

un
r
t
je
c
e
–
p
d

F
/

d
o

je
/

.

1
0
1
1
6
2

/
t

je

un
c
_
un
_
0
0
2
0
6
1
5
6
6
6
3
9

/

/
t

je

un
c
_
un
_
0
0
2
0
6
p
d

.

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

23

R.[je,j,X,bi,bj,F]←symmetrictoL[je,j,X,bi,bj,F]R.[je,j,X,bi,F,T]←symmetrictoL[je,j,X,F,bj,T]R.[je,j,X,bi,T,T]←notreachableR_XFromJ[je,j,X]←symmetrictoL_XFromI[je,j,X]R_JFromX[je,j,X]←symmetrictoL_IFromX[je,j,X]R_IFromX[je,j,X]←symmetrictoL_JFromX[je,j,X]R_IFromJ[je,j,X]←symmetrictoL_JFromI[je,j,X]ReferencesE.Bach,C.Brown,andW.Marslen-Wilson.1986.Crossedandnesteddependenciesingermananddutch:Apsycholinguisticstudy.LanguageandCognitiveProcesses,1(4):249–262.F.BernhartandP.C.Kainen.1979.Thebookthicknessofagraph.JournalofCombinatorialTheory,SeriesB,27(3):320–331.M.Bodirsky,M.Kuhlmann,andM.Möhl.2005.Well-nesteddrawingsasmodelsofsyntacticstructure.InInTenthConferenceonFormalGrammarandNinthMeetingonMathematicsofLanguage,pages88–1.UniversityPress.X.Carreras.2007.Experimentswithahigher-orderprojectivedependencyparser.InProceedingsoftheCoNLLSharedTaskSessionofEMNLP-CoNLL,vol-ume7,pages957–961.N.Chomsky,MassachusettsInstituteofTechnology.Dept.ofLinguistics,andPhilosophy.1998.Minimal-istinquiries:theframework.MIToccasionalpapersinlinguistics.DistributedbyMITWorkingPapersinLinguistics,AVEC,Dept.ofLinguistics.N.Chomsky.1981.LecturesonGovernmentandBind-ing.Dordrecht:Foris.F.Chung,F.Leighton,andA.Rosenberg.1987.Em-beddinggraphsinbooks:Alayoutproblemwithap-plicationstoVLSIdesign.SIAMJournalonAlgebraicDiscreteMethods,8(1):33–58.H.Cui,R.Sun,K.Li,M.Y.Kan,andT.S.Chua.2005.Questionansweringpassageretrievalusingdepen-dencyrelations.InProceedingsofthe28thannualinternationalACMSIGIRconferenceonResearchanddevelopmentininformationretrieval,pages400–407.ACM.A.CulottaandJ.Sorensen.2004.Dependencytreekernelsforrelationextraction.InProceedingsofthe42ndAnnualMeetingonAssociationforComputa-tionalLinguistics,page423.AssociationforCompu-tationalLinguistics.Y.DingandM.Palmer.2005.Machinetranslationusingprobabilisticsynchronousdependencyinsertiongram-mars.InProceedingsofthe43rdAnnualMeetingonAssociationforComputationalLinguistics,pages541–548.AssociationforComputationalLinguistics.J.Eisner.2000.Bilexicalgrammarsandtheircubic-timeparsingalgorithms.InHarryBuntandAntonNijholt,editors,AdvancesinProbabilisticandOtherParsingTechnologies,pages29–62.KluwerAcademicPublishers,October.S.EvenandA.Itai.1971.Queues,stacks,andgraphs.InProc.InternationalSymp.onTheoryofMachinesandComputations,pages71–86.C.Gómez-RodríguezandJ.Nivre.2010.Atransition-basedparserfor2-planardependencystructures.InProceedingsofACL,pages1492–1501.C.Gómez-Rodríguez,J.Carroll,andD.Weir.2011.De-pendencyparsingschemataandmildlynon-projectivedependencyparsing.ComputationalLinguistics,37(3):541–586.T.KooandM.Collins.2010.Efficientthird-orderde-pendencyparsers.InProceedingsofACL,pages1–11.M.Kuhlmann.2013.Mildlynon-projectivedependencygrammar.ComputationalLinguistics,39(2).R.McDonaldandF.Pereira.2006.Onlinelearningofapproximatedependencyparsingalgorithms.InPro-ceedingsofEACL,pages81–88.R.McDonaldandG.Satta.2007.Onthecomplexityofnon-projectivedata-drivendependencyparsing.InProceedingsofthe10thInternationalConferenceonParsingTechnologies,pages121–132.R.McDonald,F.Pereira,K.Ribarov,andJ.Hajiˇc.2005.Non-projectivedependencyparsingusingspanningtreealgorithms.InProceedingsoftheconferenceonHumanLanguageTechnologyandEmpiricalMethodsinNaturalLanguageProcessing,pages523–530.As-sociationforComputationalLinguistics.E.Pitler,S.Kannan,andM.Marcus.2012.Dynamicprogrammingforhigherorderparsingofgap-mindingtrees.InProceedingsofEMNLP,pages478–488.L.A.Ringenberg.1967.Collegegeometry.Wiley.A.RushandS.Petrov.2012.Vinepruningforeffi-cientmulti-passdependencyparsing.InProceedingsofNAACL,pages498–507.S.M.Shieber.1985.Evidenceagainstthecontext-freenessofnaturallanguage.LinguisticsandPhiloso-phy,8(3):333–343.H.ZhangandR.McDonald.2012.Generalizedhigher-orderdependencyparsingwithcubepruning.InPro-ceedingsofEMNLP,pages320–331.

je

D
o
w
n
o
un
d
e
d

F
r
o
m
h

t
t

p

:
/
/

d
je
r
e
c
t
.

m

je
t
.

e
d
toi

/
t

un
c
je
/

je

un
r
t
je
c
e
–
p
d

F
/

d
o

je
/

.

1
0
1
1
6
2

/
t

je

un
c
_
un
_
0
0
2
0
6
1
5
6
6
6
3
9

/

/
t

je

un
c
_
un
_
0
0
2
0
6
p
d

.

F

b
oui
g
toi
e
s
t

t

o
n
0
8
S
e
p
e
m
b
e
r
2
0
2
3

24
Télécharger le PDF