Operazioni dell'Associazione per la Linguistica Computazionale, 1 (2013) 13–24. Redattore di azioni: Giorgio Satta.

Submitted 11/2012; Pubblicato 3/2013. C
(cid:13)

2013 Associazione per la Linguistica Computazionale.

FindingOptimal1-Endpoint-CrossingTreesEmilyPitler,SampathKannan,MitchellMarcusComputerandInformationScienceUniversityofPennsylvaniaPhiladelphia,PA19104epitler,kannan,mitch@seas.upenn.eduAbstractDependencyparsingalgorithmscapableofproducingthetypesofcrossingdependenciesseeninnaturallanguagesentenceshavetra-ditionallybeenordersofmagnitudeslowerthanalgorithmsforprojectivetrees.For95.8-99.8%ofdependencyparsesinvariousnat-urallanguagetreebanks,wheneveranedgeiscrossed,theedgesthatcrossitallhaveacommonvertex.Theoptimaldependencytreethatsatisﬁesthis1-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)ﬁndthehighest-scoringprojectivetrees(inwhichnoedgescross),despitethefactthatalargeproportionofnat-urallanguagesentencesarenon-projective.Projec-tivetreescanbefoundinO(n3)time(Eisner,2000),butcoveronly63.6%ofsentencesinsomenaturallanguagetreebanks(Table1).TheclassofdirectedspanningtreescoversalltreebanktreesandcanbeparsedinO(n2)withedge-basedfeatures(McDonaldetal.,2005),butitisNP-hardtoﬁndthemaximumscoringsuchtreewithgrandparentorsiblingfeatures(McDonaldandPereira,2006;McDonaldandSatta,2007).Therearevariousexistingdeﬁnitionsofmildlynon-projectivetreeswithbetterempiricalcoveragethanprojectivetreesthatdonothavethehardnessofextensibilitythatspanningtreesdo.However,thesehavehadparsingalgorithmsthatareordersofmag-nitudeslowerthantheprojectivecaseortheedge-basedspanningtreecase.Forexample,well-nesteddependencytreeswithblockdegree2(Kuhlmann,2013)coveratleast95.4%ofnaturallanguagestruc-tures,buthaveaparsingtimeofO(n7)(Gómez-Rodríguezetal.,2011).Nopreviouslydeﬁnedclassoftreessimultane-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).Thisisthekeyinsightthatallowsefﬁcientparsing;theO(n4)parsingalgorithmispresentedinSection4.1-Endpoint-Crossingtreesareasubclassof2-planargraphs(Section5.1),aclassthathasbeenstudied

D
o
w
N
o
UN
D
e
D

F
R
o
M
H

T
T

:
/
/

D
io
R
e
C
T
.

io
T
.

e
D
tu

/
T

UN
C
l
/

UN
R
T
io
C
e
–
P
D

F
/

D
o

io
/

1
0
1
1
6
2

/
T

UN
C
_
UN
_
0
0
2
0
6
1
5
6
6
6
3
9

/
T

UN
C
_
UN
_
0
0
2
0
6
P
D

B
sì
G
tu
e
S
T

o
N
0
8
S
e
P
e
M
B
e
R
2
0
2
3

inNLP.1-Endpoint-Crossingtreesalsohavesomelinguisticinterpretation(pairsofcrossserialverbsproduce1-Endpoint-Crossingtrees,Section5.2).2DeﬁnitionsofNon-ProjectivityDeﬁnition1.Edgeseandfcrossifeandfhavedistinctendpointsandexactlyoneoftheendpointsoffliesbetweentheendpointsofe.Deﬁnition2.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.Thedeﬁnitionsofblockdegreeandwell-nestednessaregivenbelow:Deﬁnition3.Foreachnodeuinthetree,ablockofthenodeis“alongestsegmentconsistingofdescen-dantsofu.”(Kuhlmann,2013).Theblock-degreeofuis“thenumberofdistinctblocksofu”.Theblockdegreeofatreeisthemaximumblockdegreeofanyofitsnodes.Thegapdegreeisthenumberofgapsbetweentheseblocks,andsobydeﬁnitionisonelessthantheblockdegree.(Kuhlmann,2013)Deﬁnition4.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)O(n4)Well-nested,blockdegree21458(99.9)72321(99.5)5175(99.7)12896(96.6)8650(95.4)10955(99.2)O(n7)Gap-Minding1394(95.5)70695(97.2)4985(96.1)12068(90.4)8481(93.5)10787(97.7)O(n5)Projective1297(88.8)55872(76.8)4379(84.4)8484(63.6)7353(81.1)9963(90.2)O(n3)Sentences146072703519013349907111042Table1:Over95%ofthedependencyparsetreesintheCoNLL-Xtrainingsetsare1-Endpoint-Crossingtrees.Coveragestatisticsandparsingtimesofpreviouslyproposedpropertiesareshownforcomparison.Deﬁnition8.Withina1-Endpoint-Crossingtree,IL(crossing)pencil2ofanedgee(P(e))isdeﬁnedasthesetofedges(sharinganendpoint)thatcrosse.The(crossingpencil)pointofanedgee(Pt(e))isdeﬁnedastheendpointthatalledgesinP(e)share.Wewilluseeuvtoindicateanedgeineitherdirec-tionbetweenuandv,i.e.,eitheru→voru←v.Beforedeﬁningtheparsingalgorithm,weﬁrstgivesomeintuitionbyanalogytoparsingforpro-jectivetrees.(ThisargumentmirrorsthatofEisner(2000,pps.38-39).)Projectivetreescanbeproducedusingdynamicprogrammingoverintervals.Inter-valsaresufﬁcientforprojectivetrees:consideranyedgeeuvinaprojectivetree.Theverticesin(tu,v)mustonlyhaveedgestoverticesin[tu,v].Iftherewereanedgebetweenavertexin(tu,v)andavertexoutside[tu,v],suchanedgewouldcrosseuv,whichwouldcontradicttheassumptionofprojectivity.Thuseveryedgeinaprojectivetreecreatesoneinteriorintervalisolatedfromtherestofthetree,allowingdynamicprogram-mingoverintervals.Wecananalyzethecaseof1-Endpoint-Crossingtreesinasimilarfashion:Deﬁnition9.Anisolatedinterval[io,j]hasnoedgesbetweentheverticesin(io,j)andtheverticesout-sideof[io,j].Anintervalandoneexteriorvertex[io,j]∪{X}iscalledanisolatedcrossingregionifthefollowingtwoconditionsaresatisﬁed:1.Therearenoedgesbetweenthevertices∈(io,j)andvertices/∈[io,j]∪{X}2.Noneoftheedgesbetweenxandvertices∈(io,j)arecrossedbyanyedgeswithbothend-points∈(io,j)2Thisnotationcomesfromananalogytogeometry:“Asetofdistinct,coplanar,concurrentlinesisapenciloflines”(Rin-genberg,1967,p.221);concurrentlinesallintersectatthesamesinglepoint.uvp(UN)[tu,v]∪{P}uvp(B)[v,P]∪{tu}upv(C)[tu,P]∪{v}upv(D)[P,v]∪{tu}Figure2:AnedgeeuvandPt(euv)=pformtwosetsofisolatedcrossingregions(Lemma1).2aand2bshowp/∈(tu,v);2cand2dshowp∈(tu,v).Lemma1.ConsideranyedgeeuvandPt(euv)=pina1-Endpoint-CrossingforestF.Letl,R,andmdenotetheleftmost,rightmost,andmiddlepointoutof{tu,v,P},respectively.Thenthethreepointsu,v,andpdeﬁnetwoisolatedcrossingregions:(1)[l,M]∪{R},E(2)[M,R]∪{l}.Proof.Firstnotethatasp=Pt(euv),P(euv)isnon-empty:theremustbeatleastoneedgebetweenvertices∈(tu,v)andvertices/∈[tu,v].piseither/∈[tu,v](i.e.,p=l∨p=r)or∈(tu,v)(i.e.,p=m):Case1:p=l∨p=r:Assumewithoutlossofgeneralitythatux/∈[tu,v]∪{P}.Thensuchanedgewouldcrosseuvwithouthavinganendpointatp,whichcontradictsthe1-Endpoint-Crossingprop-ertyforeuv.Condition2:Assumethatforsomeepasuchthata∈(tu,v),epawascrossedbyanedgeintheinteriorof(tu,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]∪{tu}isanisolatedcrossingregion(Figure2b):Condition1:Assumetherewereanedgeeabwitha∈(v,P)andb/∈[v,P]∪{tu}.bcannotbein(tu,v)(byabove).Così,b/∈[tu,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)[tu,P]∪{v}isanisolatedcrossingregion(Figure2c):Condition1:Assumetherewereanedgeeabwitha∈(tu,P)andb/∈[tu,P]∪{v}(b∈(P,v)∨b/∈[tu,v]).Firstassumeb∈(P,v).TheneabcrossesalledgesinP(euv);aseabdoesnotshareanendpointwitheuv,thiscontradictsthe1-Endpoint-CrossingpropertyfortheedgesinP(euv).Nextassumeb/∈[tu,v].Theneabcrosseseuv;sincea6=p∧b6=p,thisviolatesthe1-Endpoint-Crossingpropertyforeuv.Condition2:Assumethatforsomeevawitha∈(tu,P),evawascrossedbyanedgeintheinteriorof(tu,v).evaisalsocrossedbyalltheedgesinP(euv);astheinterioredgewillnotshareanendpointwiththeedgesinP(euv),thiscontradictsthe1-Endpoint-Crossingpropertyforeva.(B)[P,v]∪{tu}isanisolatedcrossingregion(Figure2d):Symmetrictotheabove.4ParsingAlgorithmTheoptimal1-Endpoint-Crossingtreecanbefoundusingadynamicprogrammingalgorithmthatex-ploitsthefactthatedgesandtheircrossingpointsdeﬁneintervalsandisolatedcrossingregions.Thissectionassumesanarc-factoredmodel,inwhichthescoreofatreeisdeﬁnedasthesumofthescoresofitsedges;scoringfunctionsforedgesaregenerallylearnedfromdata.(UN)Onlyedgesinci-denttotheLeftpointoftheintervalmaycrosstheedgesfromtheexteriorpoint(B)Onlyedgesin-cidenttotheRightpointoftheinter-valmaycrosstheedgesfromtheexte-riorpoint(C)both(LR)(D)NeitherFigure3:Isolatedcrossingregionsub-problems.Thedynamicprogramusesﬁvetypesofsub-problems:intervalsub-problemsforeachinterval[io,j],denotedInt[io,j],andfourtypesofisolatedcrossingregionsub-problemsforeachintervalandexteriorpoint[io,j]∪{X},whichdifferinwhetheredgesfromtheexteriorpointmaybecrossedbyedgeswithanendpointattheLeftpointoftheinter-val,theRightpoint,bothLR,orNeither(Figure3).l[io,j,X],forexample,referstoanisolatedcrossingregionovertheinterval[io,j]withanexteriorpointofx,inwhichedgesincidenttoi(theleftboundarypoint)cancrossedgesbetweenxand(io,j).Thesedistinctionsallowthe1-Endpoint-Crossingpropertytobegloballyenforced;crossingedgesinoneregionmayconstrainedgesinanother.Forex-ample,considerthatFigure2aallowsedgeswithanendpointatvtocrosstheedgesfromp,whileFigure2ballowsedgesfromuinto(v,P).Bothsimultane-ouslywouldcausea1-Endpoint-CrossingviolationfortheedgesinP(euv).Figures4and5showvalidcombinationsofthesub-problemsinFigure3.ThefulldynamicprogramisshowninAppendixA.Theﬁnalanswermustbeavaliddependencytree,whichrequireseachwordtohaveexactlyoneparentandprohibitscycles.Weusebooleans(bi,bj,bx)foreachsub-problem,inwhichthebooleanissettotrueifandonlyifthesolutiontothesub-problemmustcontaintheincoming(parent)edgeforthecorre-spondingboundarypoint.WeusethesufﬁxAFromBforasub-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∈(io,k):likj(io)Ifthedashededgeexists:Alltheedgesfromlinto(io,k)mustchoosekastheirPt.TheintervaldecomposesintoS[eik]+R[io,k,l]+Int[k,l]+l[l,j,k]:kilj(ii)Ifnoedgeslikethedashededgeexist:Alledgesfromlinto(io,k)maychooseeitheriorkastheirPt.TheintervaldecomposesintoS[eik]+LR[io,k,l]+Int[k,l]+Int[l,j]:iklj(io)Ifdashededgeexists:Alltheedgesfromlinto(k,j]mustchooseiastheirPt.Theintervaldecom-posesintoS[eik]+Int[io,l]+l[l,k,io]+N[k,j,l]:likj(ii)Ifnoedgeslikethedashededgeexist:AlledgesfromlmaychoosekastheirPt.Theintervaldecom-posesintoS[eik]+R[io,l,k]+Int[l,k]+l[k,j,l]:likjFigure4:DecomposinganInt[io,j]sub-problem,withPt(eik)=lbutforsimplicityfocusthediscussiononthedecom-positionintocrossingregionsandthemaintenanceofthe1-Endpoint-Crossingproperty.Edgedirectiondoesnotaffectthesepointsoffocus,andsowewillrefersimplytoS[euv]tomeanthescoreofeithertheedgefromutovorvice-versa.Inthefollowingsubsections,weshowthattheop-timalparseforeachtypeofsub-problemcanbede-composedintosmallervalidsub-problems.Ifwetakethemaximumoverallthesepossiblecombina-tionsofsmallersolutions,wecanﬁndthemaximumscoringparseforthatsub-problem.Notethattheoveralltreeisavalidsub-problem(overtheinter-val[0,N]),sotheargumentwillalsoholdforﬁndingtheoptimaloveralltree.Eachindividualvertexandeachpairofadjacentvertices(withnoedges)triv-iallyformisolatedintervals(asthereisnointerior);thisformsthebasecaseofthedynamicprogram.TheoveralldynamicprogramtakesO(n4)time:thereareO(n2)intervalsub-problems,eachofwhichneedstwofreesplitpointstoﬁndthemax-imum,andO(n3)regionsub-problems,eachofwhichisamaximizationoveronefreesplitpoint.4.1DecomposinganIntsub-problemConsideranisolatedintervalsub-problemInt[io,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[io,j],asthatedgehasnoeffectontheinterioroftheinterval.Clearly,thisisonlyappli-cableiftheboundarypointneededaparent(asin-dicatedbythebooleans)andthebooleanmustthenbeupdatedaccordingly.Ifthefurthestedgeistosomekin(io,j),theproblemisdecomposedintoS[eik]+Int[io,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/∈(io,k)(Figure4a):ByLemma1,[io,k]∪{l}E[k,l]∪{io}formisolatedregions.(l,j]istheremain-deroftheinterval,andtheonlyvertexfrom[io,l)thatcanhaveedgesinto(l,j]isk:(io,k)E(k,l)arepartofisolatedregions,andiisruledoutbecausekwasi’sfurthestneighbor.Ifatleastoneedgefromkinto(l,j](thedashedlineinFigure4a)exists,thedecompositionisasinFigure4a,Casei;otherwise,itisasinFigure4a,Caseii.InCasei,eikandtheedge(S)betweenkand(l,j]forcealloftheedgesbetweenland(io,k)tohavekastheirPt.Thus,theregion[io,k]∪{l}mustbeasub-problemoftypeR(Figure3b),astheseedgesfromlcanonlybecrossedbyedgeswithanendpointatk(therightendpointof[io,k]).Alloftheedgesbetweenkand(l,j]havelastheirPt,astheyarecrossedbyalltheedgesinP(eik),andsothesub-problemcorrespondingtotheregion[l,j]∪{k}isoftypeL(Figure3a).InCaseii,eachoftheedgesinP(eik)maychooseeitheriorkastheirPt,sothesub-problem[io,k]∪{l}isoftypeLR(Figure3c).Notethatl=jisaspecialcaseofCaseiiinwhichtherightmostintervalInt[l,j]isempty.l∈(io,k)(Figure4b):[io,l]∪{k}E[l,k]∪{io}formisolatedcrossingregionsbyLemma1.Therecannotbothbeedgesbetweeniand(l,k)andbe-tweenkand(io,l),asthiswouldviolate1-Endpoint-CrossingfortheedgesinP(eik).Ifthereareanyedgesbetweeniand(l,k)(i.e.,CaseiinFigure4b),thenalloftheedgesinP(eik)mustchooseiastheirPt,andsotheseedgescannotbecrossedatallintheregion[k,j]∪{l},andtherecannotbeanyedgesfromkinto(io,l).Iftherearenosuchedges(Caseiiin4b),thenkmustbeavalidPtforalledgesinP(eik),andsotherecanbothbeedgesfromkinto(io,l)E[k,j]∪{l}maybeoftypeL(allowingcrossingswithanendpointatk).4.2DecomposinganLRsub-problemAnLRsub-problemisoveranisolatedcrossingre-gion[io,j]∪{X},suchthatedgesfromxinto(io,j)maybecrossedbyedgeswithanendpointateitheriorj.Thissub-problemisonlydeﬁnedwhenneitherinorjgettheirparentfromthissub-problem.Fromatop-downperspective,thiscaseisonlyusedwhentherewillbeanedgebetweeniandj(asinoneofthesub-problemsinFigure4a,Caseii).Ifnoneoftheedgesfromxarecrossedbyanyedgeswithanendpointati,thiscanbeconsideredanRproblem.Similarly,ifnonearecrossedbyanyedgeswithanendpointatj,thismaybeconsideredanLsub-problem.Theonlycasewhichneedsdis-cussioniswhenbothedgeswithanendpointatiandalsoatjcrossedgesfromx;seeFigure3cforaschematic.Inthatscenario,theremustexistasplitpointsuchthat:(1)totheleftofthepoint,alledgescrossingx-edgeshaveanendpointati,andtotherightofthepoint,allsuchedgeshaveanendpointatj,E(2)noedgesintheregioncrossthesplitpoint.Letribei’srightmostchildin(io,j);letljbej’sleftmostchildin(io,j).Everyedgefromxinto(io,ri)iscrossedbyeiri;everyedgebetweenxand(lj,j)iscrossedbyeljj.eiricannotcrosseljj,asthatwouldeitherviolate1-Endpoint-Crossing(be-causeofthex-interioredges)orcreateacycle(ifbothchildrenarealsoconnectedbyanedgetox).riandljalsocannotbeequal:asneitherinorjmaybeassignedaparent,theymustbothbeinthedirec-tionofthechild,andthechildcannothavemultipleparents.Thus,riistotheleftoflj.Anysplitpointbetweenriandljclearlysatis-ﬁes(1).Thereisatleastonepointwithin[ri,lj]thatsatisﬁes(2)aslongasthereisnotachainofcrossingedgesfromeiritoeljj.Theproofisomittedforspacereasons,butsuchachaincanberuledoutusingacountingargumentsimilartothatintheproofinSection5.1.Thedecompositionis:l[io,k,X]+R[k,j,X]forsomek∈(io,j).4.3DecomposinganNsub-problemConsiderthemaximumscoringforestoftypeNover[io,j]∪{X}(Figure3d;noedgesfromxarecrossedinthissub-problem).Iftherearenoedgesfromx,thenitisalsoavalidInt[io,j]sub-problem.Ifthereareedgesbetweenxandtheendpointsiorj,thentheforestwiththatedgeremovedisstillavalidNsub-problem(withtheancestorandparentbook-keepingupdated).Otherwise,ifthereareedgesbe-tweenxand(io,j),choosetheneighborofxclosesttoj(callitk).Sincetheedgeexkisnotcrossed,therearenoedgesfrom[io,k)into(k,j];sincekwastheneighborofxclosesttoj,therearenoedgesfromxinto(k,j].Così,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(io)Ifdashededgeexists:Alltheedgesfromiinto(k,j]mustchoosexastheirPt.Theintervaldecom-posesintoS[exk]+l[io,k,X]+N[k,j,io]:xkji(ii)Ifnoedgeslikethedashededgeexist:Edgesfromiinto(k,j]maychoosekastheirPt.Thein-tervaldecomposesintoS[exk]+Int[io,k]+l[k,j,io]:xkjiFigure5:AnLsub-problemover[io,j]∪{X},kistheneighborofxfurthestfromiintheinterval.S[eik]+Int[k,j]+N[io,k,X].Asanaside,ifbxwastrue(xneededaparentfromthissub-problem),andkwasachildofx,thenx’sparentmustcomefromthe[io,k]∪{X}sub-problem.However,itcannotbeadescendantofk,asthatwouldcauseacycle.Thusinthiscase,wecallthesub-problemaN_XFromIproblem,toin-dicatethatxneedsaparent,iandkdonot,andxmustbedescendedfromi,notk.4.4DecomposinganLorRsub-problemAnLsub-problemover[io,j]∪{X}requiresthatanyedgesinthisregionthatcrossanedgewithanend-pointatxhaveanendpointati(theleftendpoint).Iftherearenoedgesbetweenxand[io,j]inanLsub-problem,thenitisalsoavalidIntsub-problemover[io,j].Ifthereareedgesbetweenxandiorj,thenthesub-problemcanbedecomposedintothatedgeplustherestoftheforestwiththatedgeremoved.Theinterestingcaseiswhenthereareedgesbe-tweenxandtheinterior(Figure5).Letkbetheneighborofxwithin(io,j)thatisfurthestfromi.Asalledgesthatcrossexkwillhaveanendpointati,therearenoedgesbetween(io,k)E(k,j].Com-binedwiththefactthatkwastheneighborofxclos-esttoj,wehavethat[io,k]∪{X}mustformaniso-abcdefFigure6:2-planarbutnot1-Endpoint-Crossinglatedcrossingregion,asmust[k,j]∪{io}.Ifthereareadditionaledgesbetweenxandthein-terior(Caseiin5),alloftheedgesfromiinto(k,j]crossboththeedgeexkandtheotheredgesfromxinto(io,k).ThePtforalltheseedgesmustthere-forebex,andasxisnotintheregion[k,j]∪{io},thoseedgescannotbecrossedatallinthatregion(cioè.,[k,j]∪{io}mustbeoftypeN).Iftherearenoadditionaledgesfromxinto(io,k)(CaseiiinFig-ure5),thenalloftheedgesfromiinto(k,j)mustchooseeitherxorkastheirPt.Astherewillbenomoreedgesfromx,choosingkastheirPtallowsstrictlymoretrees,andso[k,j]∪{io}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).Theproblemofﬁndinganembeddingthatminimizesthenumberofpagesrequiredisanaturalformulationofmanyproblemsarisingindisparateareasofcomputerscience,forexample,sortingase-quenceusingtheminimumnumberofstacks(EvenandItai,1971),orconstructingfault-tolerantlayoutsinVLSIdesign(Chungetal.,1987).Inthissectionweprove1-Endpoint-Crossing⊆2-planar.Theseclassesarenotequal(Figure6).Weﬁrstprovesomepropertiesaboutthecrossingsgraphs(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.Leteobetheﬁrstoddedgethatcontainsb(weknowoneexistssinceencontainsb).(oisatleast3,sincee1doesnotcontainb.)eo’sothervertexmustbetheonesharedwitheo−2(eo−2doesnotcontainb,sinceeowastheﬁrstoddedgetocontainb).There-fore,bothofeo’sverticeshavealreadybeenseenalongthecycle.Similarly,leteebetheﬁrstevenedgethatcon-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,from(1)inShieber(1985):dasmeremHanseshuushälfedaastriichethatweHansDATthehouseACChelpedpaintTheedges(Quello,helped),(helped,we),E(helped,Hans)areeachonlycrossedbyanedgewithanendpointatpaint;theedge(colore,house)isonlycrossedbyedgeswithanendpointathelped.Moregenerally,withasetoftwocrossserialverbsinasubordinateclause,eachverbshouldsufﬁceasthecrossingpointforalledgesincidenttotheotherverbthatarecrossed.Cross-serialconstructionswiththreeormoreverbswouldhavedependencytreesthatviolate1-

D
o
w
N
o
UN
D
e
D

F
R
o
M
H

T
T

:
/
/

D
io
R
e
C
T
.

io
T
.

e
D
tu

/
T

UN
C
l
/

UN
R
T
io
C
e
–
P
D

F
/

D
o

io
/

1
0
1
1
6
2

/
T

UN
C
_
UN
_
0
0
2
0
6
1
5
6
6
6
3
9

/
T

UN
C
_
UN
_
0
0
2
0
6
P
D

B
sì
G
tu
e
S
T

o
N
0
8
S
e
P
e
M
B
e
R
2
0
2
3

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,withamovedelementleavingachainoftracesattheedgeofeachclauseonitswaytoitsﬁnalpronouncedloca-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(Dire,said1),(said1,said2),E(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.Threeedgeswillalwayssufﬁceasacertiﬁcateofa1-Endpoint-Crossingviolation(twovertex-disjointedgesthatbothcrossathird).Incontrast,forapropertylikeill-nestedness,twonodesmighthavealeastcommonancestorarbitrarilyfaraway,andsoonemightneedtheentiregraphtoverifywhetherthesub-treesrootedatthosenodesaredisjointandill-nested.Wehavediscussedcross-serialdepen-dencies;afurtherexplorationofwhichlinguisticphenomenawouldandwouldnothave1-Endpoint-Crossingdependencytreesmayberevealing.AcknowledgmentsWewouldliketothankJulieLegateforanin-terestingdiscussion.ThismaterialisbaseduponworksupportedunderaNationalScienceFoun-dationGraduateResearchFellowship,NSFAwardCCF1137084,andArmyResearchOfﬁceMURIgrantW911NF-07-1-0216.ADynamicProgramtoﬁndthemaximumscoring1-Endpoint-CrossingTreeInput:MatrixS:S[io,j]isthescoreofthedirectededge(io,j)Output:Maximumscoreofa1-Endpoint-Crossingtreeoververtices[0,N],rootedat0Init:∀iInt[io,io,F,F]=Int[io,i+1,F,F]=0Int[io,io,T,F]=Int[io,io,F,T]=Int[io,io,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-problemswiththesufﬁxAFromB,theboundarypointAhasitsparentedgeinthesub-problemsolution;theothertwoboundarypointsdonot.Forexample,L_XFromIwouldcor-respondtohavingbooleansbi=bj=Fandbx=T,withtherestrictionthatxmustbeadescendantofi.

D
o
w
N
o
UN
D
e
D

F
R
o
M
H

T
T

:
/
/

D
io
R
e
C
T
.

io
T
.

e
D
tu

/
T

UN
C
l
/

UN
R
T
io
C
e
–
P
D

F
/

D
o

io
/

1
0
1
1
6
2

/
T

UN
C
_
UN
_
0
0
2
0
6
1
5
6
6
6
3
9

/
T

UN
C
_
UN
_
0
0
2
0
6
P
D

B
sì
G
tu
e
S
T

o
N
0
8
S
e
P
e
M
B
e
R
2
0
2
3

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

D
o
w
N
o
UN
D
e
D

F
R
o
M
H

T
T

:
/
/

D
io
R
e
C
T
.

io
T
.

e
D
tu

/
T

UN
C
l
/

UN
R
T
io
C
e
–
P
D

F
/

D
o

io
/

1
0
1
1
6
2

/
T

UN
C
_
UN
_
0
0
2
0
6
1
5
6
6
6
3
9

/
T

UN
C
_
UN
_
0
0
2
0
6
P
D

B
sì
G
tu
e
S
T

o
N
0
8
S
e
P
e
M
B
e
R
2
0
2
3

R[io,j,X,bi,bj,F]←symmetrictoL[io,j,X,bi,bj,F]R[io,j,X,bi,F,T]←symmetrictoL[io,j,X,F,bj,T]R[io,j,X,bi,T,T]←notreachableR_XFromJ[io,j,X]←symmetrictoL_XFromI[io,j,X]R_JFromX[io,j,X]←symmetrictoL_IFromX[io,j,X]R_IFromX[io,j,X]←symmetrictoL_JFromX[io,j,X]R_IFromJ[io,j,X]←symmetrictoL_JFromI[io,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,MIT,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.Efﬁcientthird-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.Vinepruningforefﬁ-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.

D
o
w
N
o
UN
D
e
D

F
R
o
M
H

T
T

:
/
/

D
io
R
e
C
T
.

io
T
.

e
D
tu

/
T

UN
C
l
/

UN
R
T
io
C
e
–
P
D

F
/

D
o

io
/

1
0
1
1
6
2

/
T

UN
C
_
UN
_
0
0
2
0
6
1
5
6
6
6
3
9

/
T

UN
C
_
UN
_
0
0
2
0
6
P
D

B
sì
G
tu
e
S
T

o
N
0
8
S
e
P
e
M
B
e
R
2
0
2
3

24
Scarica il pdf