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 Verein für Computerlinguistik.

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)Zeit(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
Ö
w
N
Ö
A
D
e
D

F
R
Ö
M
H

T
T

:
/
/

D
ich
R
e
C
T
.

ich
T
.

e
D
u

/
T

A
C
l
/

A
R
T
ich
C
e
–
P
D

F
/

D
Ö

ich
/

1
0
1
1
6
2

/
T

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

/
T

A
C
_
A
_
0
0
2
0
6
P
D

B
j
G
u
e
S
T

Ö
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∈T2suchthatl1e d u / t a c l / l A R T ich 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 j 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.Deﬁnition8.Withina1-Endpoint-Crossingtree,Die(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(u,v)mustonlyhaveedgestoverticesin[u,v].Iftherewereanedgebetweenavertexin(u,v)andavertexoutside[u,v],suchanedgewouldcrosseuv,whichwouldcontradicttheassumptionofprojectivity.Thuseveryedgeinaprojectivetreecreatesoneinteriorintervalisolatedfromtherestofthetree,allowingdynamicprogram-mingoverintervals.Wecananalyzethecaseof1-Endpoint-Crossingtreesinasimilarfashion:Deﬁnition9.Anisolatedinterval[ich,J]hasnoedgesbetweentheverticesin(ich,J)andtheverticesout-sideof[ich,J].Anintervalandoneexteriorvertex[ich,J]∪{X}iscalledanisolatedcrossingregionifthefollowingtwoconditionsaresatisﬁed:1.Therearenoedgesbetweenthevertices∈(ich,J)andvertices/∈[ich,J]∪{X}2.Noneoftheedgesbetweenxandvertices∈(ich,J)arecrossedbyanyedgeswithbothend-points∈(ich,J)2Thisnotationcomesfromananalogytogeometry:“Asetofdistinct,coplanar,concurrentlinesisapenciloflines”(Rin-genberg,1967,p.221);concurrentlinesallintersectatthesamesinglepoint.uvp(A)[u,v]∪{P}uvp(B)[v,P]∪{u}upv(C)[u,P]∪{v}upv(D)[P,v]∪{u}Figure2:AnedgeeuvandPt(euv)=pformtwosetsofisolatedcrossingregions(Lemma1).2aand2bshowp/∈(u,v);2cand2dshowp∈(u,v).Lemma1.ConsideranyedgeeuvandPt(euv)=pina1-Endpoint-CrossingforestF.Letl,R,andmdenotetheleftmost,rightmost,andmiddlepointoutof{u,v,P},respectively.Thenthethreepointsu,v,andpdeﬁnetwoisolatedcrossingregions:(1)[l,M]∪{R},Und(2)[M,R]∪{l}.Proof.Firstnotethatasp=Pt(euv),P(euv)isnon-empty:theremustbeatleastoneedgebetweenvertices∈(u,v)andvertices/∈[u,v].piseither/∈[u,v](i.e.,p=l∨p=r)or∈(u,v)(i.e.,p=m):Case1:p=l∨p=r:Assumewithoutlossofgeneralitythatux/∈[u,v]∪{P}.Thensuchanedgewouldcrosseuvwithouthavinganendpointatp,whichcontradictsthe1-Endpoint-Crossingprop-ertyforeuv.Condition2:Assumethatforsomeepasuchthata∈(u,v),epawascrossedbyanedgeintheinteriorof(u,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 ich R e C T . M ich T . e d u / t a c l / l A R T ich 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 j 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]∪{u}isanisolatedcrossingregion(Figure2b):Condition1:Assumetherewereanedgeeabwitha∈(v,P)andb/∈[v,P]∪{u}.bcannotbein(u,v)(byabove).Daher,b/∈[u,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:(A)[u,P]∪{v}isanisolatedcrossingregion(Figure2c):Condition1:Assumetherewereanedgeeabwitha∈(u,P)andb/∈[u,P]∪{v}(b∈(P,v)∨b/∈[u,v]).Firstassumeb∈(P,v).TheneabcrossesalledgesinP(euv);aseabdoesnotshareanendpointwitheuv,thiscontradictsthe1-Endpoint-CrossingpropertyfortheedgesinP(euv).Nextassumeb/∈[u,v].Theneabcrosseseuv;sincea6=p∧b6=p,thisviolatesthe1-Endpoint-Crossingpropertyforeuv.Condition2:Assumethatforsomeevawitha∈(u,P),evawascrossedbyanedgeintheinteriorof(u,v).evaisalsocrossedbyalltheedgesinP(euv);astheinterioredgewillnotshareanendpointwiththeedgesinP(euv),thiscontradictsthe1-Endpoint-Crossingpropertyforeva.(B)[P,v]∪{u}isanisolatedcrossingregion(Figure2d):Symmetrictotheabove.4ParsingAlgorithmTheoptimal1-Endpoint-Crossingtreecanbefoundusingadynamicprogrammingalgorithmthatex-ploitsthefactthatedgesandtheircrossingpointsdeﬁneintervalsandisolatedcrossingregions.Thissectionassumesanarc-factoredmodel,inwhichthescoreofatreeisdeﬁnedasthesumofthescoresofitsedges;scoringfunctionsforedgesaregenerallylearnedfromdata.(A)Onlyedgesinci-denttotheLeftpointoftheintervalmaycrosstheedgesfromtheexteriorpoint(B)Onlyedgesin-cidenttotheRightpointoftheinter-valmaycrosstheedgesfromtheexte-riorpoint(C)beide(LR)(D)NeitherFigure3:Isolatedcrossingregionsub-problems.Thedynamicprogramusesﬁvetypesofsub-problems:intervalsub-problemsforeachinterval[ich,J],denotedInt[ich,J],andfourtypesofisolatedcrossingregionsub-problemsforeachintervalandexteriorpoint[ich,J]∪{X},whichdifferinwhetheredgesfromtheexteriorpointmaybecrossedbyedgeswithanendpointattheLeftpointoftheinter-val,theRightpoint,bothLR,orNeither(Figure3).L[ich,J,X],forexample,referstoanisolatedcrossingregionovertheinterval[ich,J]withanexteriorpointofx,inwhichedgesincidenttoi(theleftboundarypoint)cancrossedgesbetweenxand(ich,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 ich R e C T . M ich T . e d u / t a c l / l A R T ich 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 j G u e S T T O N 0 8 S e P e M B e R 2 0 2 3 17 (A)Ifl∈(k,J]:kilj(B)Ifl∈(ich,k):likj(ich)Ifthedashededgeexists:Alltheedgesfromlinto(ich,k)mustchoosekastheirPt.TheintervaldecomposesintoS[eik]+R[ich,k,l]+Int[k,l]+L[l,J,k]:kilj(ii)Ifnoedgeslikethedashededgeexist:Alledgesfromlinto(ich,k)maychooseeitheriorkastheirPt.TheintervaldecomposesintoS[eik]+LR[ich,k,l]+Int[k,l]+Int[l,J]:iklj(ich)Ifdashededgeexists:Alltheedgesfromlinto(k,J]mustchooseiastheirPt.Theintervaldecom-posesintoS[eik]+Int[ich,l]+L[l,k,ich]+N[k,J,l]:likj(ii)Ifnoedgeslikethedashededgeexist:AlledgesfromlmaychoosekastheirPt.Theintervaldecom-posesintoS[eik]+R[ich,l,k]+Int[l,k]+L[k,J,l]:likjFigure4:DecomposinganInt[ich,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)Zeit:thereareO(n2)intervalsub-problems,eachofwhichneedstwofreesplitpointstoﬁndthemax-imum,andO(n3)regionsub-problems,eachofwhichisamaximizationoveronefreesplitpoint.4.1DecomposinganIntsub-problemConsideranisolatedintervalsub-problemInt[ich,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[ich,J],asthatedgehasnoeffectontheinterioroftheinterval.Clearly,thisisonlyappli-cableiftheboundarypointneededaparent(asin-dicatedbythebooleans)andthebooleanmustthenbeupdatedaccordingly.Ifthefurthestedgeistosomekin(ich,J),theproblemisdecomposedintoS[eik]+Int[ich,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 ich R e C T . M ich T . e d u / t a c l / l A R T ich 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 j 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/∈(ich,k)(Figure4a):ByLemma1,[ich,k]∪{l}Und[k,l]∪{ich}formisolatedregions.(l,J]istheremain-deroftheinterval,andtheonlyvertexfrom[ich,l)thatcanhaveedgesinto(l,J]isk:(ich,k)Und(k,l)arepartofisolatedregions,andiisruledoutbecausekwasi’sfurthestneighbor.Ifatleastoneedgefromkinto(l,J](thedashedlineinFigure4a)exists,thedecompositionisasinFigure4a,Casei;ansonsten,itisasinFigure4a,Caseii.InCasei,eikandtheedge(S)betweenkand(l,J]forcealloftheedgesbetweenland(ich,k)tohavekastheirPt.Thus,theregion[ich,k]∪{l}mustbeasub-problemoftypeR(Figure3b),astheseedgesfromlcanonlybecrossedbyedgeswithanendpointatk(therightendpointof[ich,k]).Alloftheedgesbetweenkand(l,J]havelastheirPt,astheyarecrossedbyalltheedgesinP(eik),andsothesub-problemcorrespondingtotheregion[l,J]∪{k}isoftypeL(Figure3a).InCaseii,eachoftheedgesinP(eik)maychooseeitheriorkastheirPt,sothesub-problem[ich,k]∪{l}isoftypeLR(Figure3c).Notethatl=jisaspecialcaseofCaseiiinwhichtherightmostintervalInt[l,J]isempty.l∈(ich,k)(Figure4b):[ich,l]∪{k}Und[l,k]∪{ich}formisolatedcrossingregionsbyLemma1.Therecannotbothbeedgesbetweeniand(l,k)andbe-tweenkand(ich,l),asthiswouldviolate1-Endpoint-CrossingfortheedgesinP(eik).Ifthereareanyedgesbetweeniand(l,k)(i.e.,CaseiinFigure4b),thenalloftheedgesinP(eik)mustchooseiastheirPt,andsotheseedgescannotbecrossedatallintheregion[k,J]∪{l},andtherecannotbeanyedgesfromkinto(ich,l).Iftherearenosuchedges(Caseiiin4b),thenkmustbeavalidPtforalledgesinP(eik),andsotherecanbothbeedgesfromkinto(ich,l)Und[k,J]∪{l}maybeoftypeL(allowingcrossingswithanendpointatk).4.2DecomposinganLRsub-problemAnLRsub-problemisoveranisolatedcrossingre-gion[ich,J]∪{X},suchthatedgesfromxinto(ich,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,Und(2)noedgesintheregioncrossthesplitpoint.Letribei’srightmostchildin(ich,J);letljbej’sleftmostchildin(ich,J).Everyedgefromxinto(ich,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[ich,k,X]+R[k,J,X]forsomek∈(ich,J).4.3DecomposinganNsub-problemConsiderthemaximumscoringforestoftypeNover[ich,J]∪{X}(Figure3d;noedgesfromxarecrossedinthissub-problem).Iftherearenoedgesfromx,thenitisalsoavalidInt[ich,J]sub-problem.Ifthereareedgesbetweenxandtheendpointsiorj,thentheforestwiththatedgeremovedisstillavalidNsub-problem(withtheancestorandparentbook-keepingupdated).Ansonsten,ifthereareedgesbe-tweenxand(ich,J),choosetheneighborofxclosesttoj(callitk).Sincetheedgeexkisnotcrossed,therearenoedgesfrom[ich,k)into(k,J];sincekwastheneighborofxclosesttoj,therearenoedgesfromxinto(k,J].Daher,theregiondecomposesinto l D o w n o a d e d f r o m h t t p : / / D ich R e C T . M ich T . e d u / t a c l / l A R T ich 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 j G u e S T T O N 0 8 S e P e M B e R 2 0 2 3 19 xkji(ich)Ifdashededgeexists:Alltheedgesfromiinto(k,J]mustchoosexastheirPt.Theintervaldecom-posesintoS[exk]+L[ich,k,X]+N[k,J,ich]:xkji(ii)Ifnoedgeslikethedashededgeexist:Edgesfromiinto(k,J]maychoosekastheirPt.Thein-tervaldecomposesintoS[exk]+Int[ich,k]+L[k,J,ich]:xkjiFigure5:AnLsub-problemover[ich,J]∪{X},kistheneighborofxfurthestfromiintheinterval.S[eik]+Int[k,J]+N[ich,k,X].Asanaside,ifbxwastrue(xneededaparentfromthissub-problem),andkwasachildofx,thenx’sparentmustcomefromthe[ich,k]∪{X}sub-problem.However,itcannotbeadescendantofk,asthatwouldcauseacycle.Thusinthiscase,wecallthesub-problemaN_XFromIproblem,toin-dicatethatxneedsaparent,iandkdonot,andxmustbedescendedfromi,notk.4.4DecomposinganLorRsub-problemAnLsub-problemover[ich,J]∪{X}requiresthatanyedgesinthisregionthatcrossanedgewithanend-pointatxhaveanendpointati(theleftendpoint).Iftherearenoedgesbetweenxand[ich,J]inanLsub-problem,thenitisalsoavalidIntsub-problemover[ich,J].Ifthereareedgesbetweenxandiorj,thenthesub-problemcanbedecomposedintothatedgeplustherestoftheforestwiththatedgeremoved.Theinterestingcaseiswhenthereareedgesbe-tweenxandtheinterior(Figure5).Letkbetheneighborofxwithin(ich,J)thatisfurthestfromi.Asalledgesthatcrossexkwillhaveanendpointati,therearenoedgesbetween(ich,k)Und(k,J].Com-binedwiththefactthatkwastheneighborofxclos-esttoj,wehavethat[ich,k]∪{X}mustformaniso-abcdefFigure6:2-planarbutnot1-Endpoint-Crossinglatedcrossingregion,asmust[k,J]∪{ich}.Ifthereareadditionaledgesbetweenxandthein-terior(Caseiin5),alloftheedgesfromiinto(k,J]crossboththeedgeexkandtheotheredgesfromxinto(ich,k).ThePtforalltheseedgesmustthere-forebex,andasxisnotintheregion[k,J]∪{ich},thoseedgescannotbecrossedatallinthatregion(d.h.,[k,J]∪{ich}mustbeoftypeN).Iftherearenoadditionaledgesfromxinto(ich,k)(CaseiiinFig-ure5),thenalloftheedgesfromiinto(k,J)mustchooseeitherxorkastheirPt.Astherewillbenomoreedgesfromx,choosingkastheirPtallowsstrictlymoretrees,andso[k,J]∪{ich}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 ich R e C T . M ich T . e d u / t a c l / l A R T ich 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 j G u e S T T O N 0 8 S e P e M B e R 2 0 2 3 20 (A,B)(A,C)(B,D)(C,e)(D,F)(A)(A,B)(A,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,aus(1)inShieber(1985):dasmeremHanseshuushälfedaastriichethatweHansDATthehouseACChelpedpaintTheedges(Das,helped),(helped,Wir),Und(helped,Hans)areeachonlycrossedbyanedgewithanendpointatpaint;theedge(paint,house)isonlycrossedbyedgeswithanendpointathelped.Moregenerally,withasetoftwocrossserialverbsinasubordinateclause,eachverbshouldsufﬁceasthecrossingpointforalledgesincidenttotheotherverbthatarecrossed.Cross-serialconstructionswiththreeormoreverbswouldhavedependencytreesthatviolate1-

D
Ö
w
N
Ö
A
D
e
D

F
R
Ö
M
H

T
T

:
/
/

D
ich
R
e
C
T
.

ich
T
.

e
D
u

/
T

A
C
l
/

A
R
T
ich
C
e
–
P
D

F
/

D
Ö

ich
/

1
0
1
1
6
2

/
T

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

/
T

A
C
_
A
_
0
0
2
0
6
P
D

B
j
G
u
e
S
T

Ö
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(grob,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(sagen,said1),(said1,said2),Und(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[ich,J]isthescoreofthedirectededge(ich,J)Output:Maximumscoreofa1-Endpoint-Crossingtreeoververtices[0,N],rootedat0Init:∀iInt[ich,ich,F,F]=Int[ich,i+1,F,F]=0Int[ich,ich,T,F]=Int[ich,ich,F,T]=Int[ich,ich,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
Ö
w
N
Ö
A
D
e
D

F
R
Ö
M
H

T
T

:
/
/

D
ich
R
e
C
T
.

ich
T
.

e
D
u

/
T

A
C
l
/

A
R
T
ich
C
e
–
P
D

F
/

D
Ö

ich
/

1
0
1
1
6
2

/
T

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

/
T

A
C
_
A
_
0
0
2
0
6
P
D

B
j
G
u
e
S
T

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

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

D
Ö
w
N
Ö
A
D
e
D

F
R
Ö
M
H

T
T

:
/
/

D
ich
R
e
C
T
.

ich
T
.

e
D
u

/
T

A
C
l
/

A
R
T
ich
C
e
–
P
D

F
/

D
Ö

ich
/

1
0
1
1
6
2

/
T

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

/
T

A
C
_
A
_
0
0
2
0
6
P
D

B
j
G
u
e
S
T

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

R[ich,J,X,bi,bj,F]←symmetrictoL[ich,J,X,bi,bj,F]R[ich,J,X,bi,F,T]←symmetrictoL[ich,J,X,F,bj,T]R[ich,J,X,bi,T,T]←notreachableR_XFromJ[ich,J,X]←symmetrictoL_XFromI[ich,J,X]R_JFromX[ich,J,X]←symmetrictoL_IFromX[ich,J,X]R_IFromX[ich,J,X]←symmetrictoL_JFromX[ich,J,X]R_IFromJ[ich,J,X]←symmetrictoL_JFromI[ich,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
Ö
w
N
Ö
A
D
e
D

F
R
Ö
M
H

T
T

:
/
/

D
ich
R
e
C
T
.

ich
T
.

e
D
u

/
T

A
C
l
/

A
R
T
ich
C
e
–
P
D

F
/

D
Ö

ich
/

1
0
1
1
6
2

/
T

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

/
T

A
C
_
A
_
0
0
2
0
6
P
D

B
j
G
u
e
S
T

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

24
PDF Herunterladen