Transacciones de la Asociación de Lingüística Computacional, 1 (2013) 13–24. Editor de acciones: Giorgio Satta.

in tacl on

Transacciones de la Asociación de Lingüística Computacional, 1 (2013) 13–24. Editor de acciones: Giorgio Satta.

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

2013 Asociación de Lingüística Computacional.

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)tiempo(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

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

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

/

/
t

yo

a
C
_
a
_
0
0
2
0
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
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∈T2suchthatl1ArabicCzechDanishDutchPortugueseSwedishParsing1-Endpoint-Crossing1457(99.8)71810(98.8)5144(99.1)12785(95.8)9007(99.3)10902(98.7)oh(n4)Well-nested,blockdegree21458(99.9)72321(99.5)5175(99.7)12896(96.6)8650(95.4)10955(99.2)oh(n7)Gap-Minding1394(95.5)70695(97.2)4985(96.1)12068(90.4)8481(93.5)10787(97.7)oh(n5)Projective1297(88.8)55872(76.8)4379(84.4)8484(63.6)7353(81.1)9963(90.2)oh(n3)Sentences146072703519013349907111042Table1:Over95%ofthedependencyparsetreesintheCoNLL-Xtrainingsetsare1-Endpoint-Crossingtrees.Coveragestatisticsandparsingtimesofpreviouslyproposedpropertiesareshownforcomparison.Definition8.Withina1-Endpoint-Crossingtree,el(crossing)pencil2ofanedgee(PAG(mi))isdefinedasthesetofedges(sharinganendpoint)thatcrosse.The(crossingpencil)pointofanedgee(punto(mi))isdefinedastheendpointthatalledgesinP(mi)share.Wewilluseeuvtoindicateanedgeineitherdirec-tionbetweenuandv,i.e.,eitheru→voru←v.Beforedefiningtheparsingalgorithm,wefirstgivesomeintuitionbyanalogytoparsingforpro-jectivetrees.(ThisargumentmirrorsthatofEisner(2000,pps.38-39).)Projectivetreescanbeproducedusingdynamicprogrammingoverintervals.Inter-valsaresufficientforprojectivetrees:consideranyedgeeuvinaprojectivetree.Theverticesin(tu,v)mustonlyhaveedgestoverticesin[tu,v].Iftherewereanedgebetweenavertexin(tu,v)andavertexoutside[tu,v],suchanedgewouldcrosseuv,whichwouldcontradicttheassumptionofprojectivity.Thuseveryedgeinaprojectivetreecreatesoneinteriorintervalisolatedfromtherestofthetree,allowingdynamicprogram-mingoverintervals.Wecananalyzethecaseof1-Endpoint-Crossingtreesinasimilarfashion:Definition9.Anisolatedinterval[i,j]hasnoedgesbetweentheverticesin(i,j)andtheverticesout-sideof[i,j].Anintervalandoneexteriorvertex[i,j]∪{X}iscalledanisolatedcrossingregionifthefollowingtwoconditionsaresatisfied:1.Therearenoedgesbetweenthevertices∈(i,j)andvertices/∈[i,j]∪{X}2.Noneoftheedgesbetweenxandvertices∈(i,j)arecrossedbyanyedgeswithbothend-points∈(i,j)2Thisnotationcomesfromananalogytogeometry:“Asetofdistinct,coplanar,concurrentlinesisapenciloflines”(Rin-genberg,1967,p.221);concurrentlinesallintersectatthesamesinglepoint.uvp(a)[tu,v]∪{pag}uvp(b)[v,pag]∪{tu}upv(C)[tu,pag]∪{v}upv(d)[pag,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,pag},respectively.Thenthethreepointsu,v,andpdefinetwoisolatedcrossingregions:(1)[yo,metro]∪{r},y(2)[metro,r]∪{yo}.Proof.Firstnotethatasp=Pt(euv),PAG(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]∪{pag}.Thensuchanedgewouldcrosseuvwithouthavinganendpointatp,whichcontradictsthe1-Endpoint-Crossingprop-ertyforeuv.Condition2:Assumethatforsomeepasuchthata∈(tu,v),epawascrossedbyanedgeintheinteriorof(tu,v).Theinterioredgewouldnotshareanend-pointwitheuv;sinceeuvalsocrossesepa,thiscon-tradictsthe1-Endpoint-Crossingpropertyforepa. yo D oh w norte oh a d mi d F r oh metro h t t pag : / / d i r mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t yo a C _ a _ 0 0 2 0 6 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 16 (b)[v,pag]∪{tu}isanisolatedcrossingregion(Figure2b):Condition1:Assumetherewereanedgeeabwitha∈(v,pag)andb/∈[v,pag]∪{tu}.bcannotbein(tu,v)(byabove).De este modo,b/∈[tu,pag],whichimpliesthateabcrossestheedgesinP(euv);aseuvdoesnotshareavertexwitheab,thiscontra-dictsthe1-Endpoint-CrossingpropertyforalledgesinP(euv).Condition2:Assumethatforsomeeuasuchthata∈(v,pag),euawascrossedbyanedgeintheinteriorof(v,pag).euawouldalsobecrossedbyalltheedgesinP(euv);astheinterioredgewouldnotshareanendpointwithanyoftheedgesinP(euv),thiswouldcontradictthe1-Endpoint-Crossingpropertyforeua.Case2:p=m:(a)[tu,pag]∪{v}isanisolatedcrossingregion(Figure2c):Condition1:Assumetherewereanedgeeabwitha∈(tu,pag)andb/∈[tu,pag]∪{v}(b∈(pag,v)∨b/∈[tu,v]).Firstassumeb∈(pag,v).TheneabcrossesalledgesinP(euv);aseabdoesnotshareanendpointwitheuv,thiscontradictsthe1-Endpoint-CrossingpropertyfortheedgesinP(euv).Nextassumeb/∈[tu,v].Theneabcrosseseuv;sincea6=p∧b6=p,thisviolatesthe1-Endpoint-Crossingpropertyforeuv.Condition2:Assumethatforsomeevawitha∈(tu,pag),evawascrossedbyanedgeintheinteriorof(tu,v).evaisalsocrossedbyalltheedgesinP(euv);astheinterioredgewillnotshareanendpointwiththeedgesinP(euv),thiscontradictsthe1-Endpoint-Crossingpropertyforeva.(b)[pag,v]∪{tu}isanisolatedcrossingregion(Figure2d):Symmetrictotheabove.4ParsingAlgorithmTheoptimal1-Endpoint-Crossingtreecanbefoundusingadynamicprogrammingalgorithmthatex-ploitsthefactthatedgesandtheircrossingpointsdefineintervalsandisolatedcrossingregions.Thissectionassumesanarc-factoredmodel,inwhichthescoreofatreeisdefinedasthesumofthescoresofitsedges;scoringfunctionsforedgesaregenerallylearnedfromdata.(a)Onlyedgesinci-denttotheLeftpointoftheintervalmaycrosstheedgesfromtheexteriorpoint(b)Onlyedgesin-cidenttotheRightpointoftheinter-valmaycrosstheedgesfromtheexte-riorpoint(C)ambos(LR)(d)NeitherFigure3:Isolatedcrossingregionsub-problems.Thedynamicprogramusesfivetypesofsub-problems:intervalsub-problemsforeachinterval[i,j],denotedInt[i,j],andfourtypesofisolatedcrossingregionsub-problemsforeachintervalandexteriorpoint[i,j]∪{X},whichdifferinwhetheredgesfromtheexteriorpointmaybecrossedbyedgeswithanendpointattheLeftpointoftheinter-val,theRightpoint,bothLR,orNeither(Figure3).l[i,j,X],forexample,referstoanisolatedcrossingregionovertheinterval[i,j]withanexteriorpointofx,inwhichedgesincidenttoi(theleftboundarypoint)cancrossedgesbetweenxand(i,j).Thesedistinctionsallowthe1-Endpoint-Crossingpropertytobegloballyenforced;crossingedgesinoneregionmayconstrainedgesinanother.Forex-ample,considerthatFigure2aallowsedgeswithanendpointatvtocrosstheedgesfromp,whileFigure2ballowsedgesfromuinto(v,pag).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, yo D oh w norte oh a d mi d F r oh metro h t t pag : / / d i r mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t yo a C _ a _ 0 0 2 0 6 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 17 (a)Ifl∈(k,j]:kilj(b)Ifl∈(i,k):likj(i)Ifthedashededgeexists:Alltheedgesfromlinto(i,k)mustchoosekastheirPt.TheintervaldecomposesintoS[eik]+R[i,k,yo]+Int[k,yo]+l[yo,j,k]:kilj(ii)Ifnoedgeslikethedashededgeexist:Alledgesfromlinto(i,k)maychooseeitheriorkastheirPt.TheintervaldecomposesintoS[eik]+LR[i,k,yo]+Int[k,yo]+Int[yo,j]:iklj(i)Ifdashededgeexists:Alltheedgesfromlinto(k,j]mustchooseiastheirPt.Theintervaldecom-posesintoS[eik]+Int[i,yo]+l[yo,k,i]+norte[k,j,yo]:likj(ii)Ifnoedgeslikethedashededgeexist:AlledgesfromlmaychoosekastheirPt.Theintervaldecom-posesintoS[eik]+R[i,yo,k]+Int[yo,k]+l[k,j,yo]:likjFigure4:DecomposinganInt[i,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,norte]),sotheargumentwillalsoholdforfindingtheoptimaloveralltree.Eachindividualvertexandeachpairofadjacentvertices(withnoedges)triv-iallyformisolatedintervals(asthereisnointerior);thisformsthebasecaseofthedynamicprogram.TheoveralldynamicprogramtakesO(n4)tiempo:thereareO(n2)intervalsub-problems,eachofwhichneedstwofreesplitpointstofindthemax-imum,andO(n3)regionsub-problems,eachofwhichisamaximizationoveronefreesplitpoint.4.1DecomposinganIntsub-problemConsideranisolatedintervalsub-problemInt[i,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[i,j],asthatedgehasnoeffectontheinterioroftheinterval.Clearly,thisisonlyappli-cableiftheboundarypointneededaparent(asin-dicatedbythebooleans)andthebooleanmustthenbeupdatedaccordingly.Ifthefurthestedgeistosomekin(i,j),theproblemisdecomposedintoS[eik]+Int[i,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 mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t yo a C _ a _ 0 0 2 0 6 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 18 interestingcase,whichusestwosplitpoints:theotherendpointoftheedge(k),andl=Pt(eik).Thedynamicprogramdependsontheorderofkandl.l/∈(i,k)(Figure4a):ByLemma1,[i,k]∪{yo}y[k,yo]∪{i}formisolatedregions.(yo,j]istheremain-deroftheinterval,andtheonlyvertexfrom[i,yo)thatcanhaveedgesinto(yo,j]isk:(i,k)y(k,yo)arepartofisolatedregions,andiisruledoutbecausekwasi’sfurthestneighbor.Ifatleastoneedgefromkinto(yo,j](thedashedlineinFigure4a)exists,thedecompositionisasinFigure4a,Casei;de lo contrario,itisasinFigure4a,Caseii.InCasei,eikandtheedge(s)betweenkand(yo,j]forcealloftheedgesbetweenland(i,k)tohavekastheirPt.Thus,theregion[i,k]∪{yo}mustbeasub-problemoftypeR(Figure3b),astheseedgesfromlcanonlybecrossedbyedgeswithanendpointatk(therightendpointof[i,k]).Alloftheedgesbetweenkand(yo,j]havelastheirPt,astheyarecrossedbyalltheedgesinP(eik),andsothesub-problemcorrespondingtotheregion[yo,j]∪{k}isoftypeL(Figure3a).InCaseii,eachoftheedgesinP(eik)maychooseeitheriorkastheirPt,sothesub-problem[i,k]∪{yo}isoftypeLR(Figure3c).Notethatl=jisaspecialcaseofCaseiiinwhichtherightmostintervalInt[yo,j]isempty.l∈(i,k)(Figure4b):[i,yo]∪{k}y[yo,k]∪{i}formisolatedcrossingregionsbyLemma1.Therecannotbothbeedgesbetweeniand(yo,k)andbe-tweenkand(i,yo),asthiswouldviolate1-Endpoint-CrossingfortheedgesinP(eik).Ifthereareanyedgesbetweeniand(yo,k)(i.e.,CaseiinFigure4b),thenalloftheedgesinP(eik)mustchooseiastheirPt,andsotheseedgescannotbecrossedatallintheregion[k,j]∪{yo},andtherecannotbeanyedgesfromkinto(i,yo).Iftherearenosuchedges(Caseiiin4b),thenkmustbeavalidPtforalledgesinP(eik),andsotherecanbothbeedgesfromkinto(i,yo)y[k,j]∪{yo}maybeoftypeL(allowingcrossingswithanendpointatk).4.2DecomposinganLRsub-problemAnLRsub-problemisoveranisolatedcrossingre-gion[i,j]∪{X},suchthatedgesfromxinto(i,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,y(2)noedgesintheregioncrossthesplitpoint.Letribei’srightmostchildin(i,j);letljbej’sleftmostchildin(i,j).Everyedgefromxinto(i,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[i,k,X]+R[k,j,X]forsomek∈(i,j).4.3DecomposinganNsub-problemConsiderthemaximumscoringforestoftypeNover[i,j]∪{X}(Figure3d;noedgesfromxarecrossedinthissub-problem).Iftherearenoedgesfromx,thenitisalsoavalidInt[i,j]sub-problem.Ifthereareedgesbetweenxandtheendpointsiorj,thentheforestwiththatedgeremovedisstillavalidNsub-problem(withtheancestorandparentbook-keepingupdated).De lo contrario,ifthereareedgesbe-tweenxand(i,j),choosetheneighborofxclosesttoj(callitk).Sincetheedgeexkisnotcrossed,therearenoedgesfrom[i,k)en(k,j];sincekwastheneighborofxclosesttoj,therearenoedgesfromxinto(k,j].De este modo,theregiondecomposesinto l D o w n o a d e d f r o m h t t p : / / d i r mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t yo a C _ a _ 0 0 2 0 6 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 19 xkji(i)Ifdashededgeexists:Alltheedgesfromiinto(k,j]mustchoosexastheirPt.Theintervaldecom-posesintoS[exk]+l[i,k,X]+norte[k,j,i]:xkji(ii)Ifnoedgeslikethedashededgeexist:Edgesfromiinto(k,j]maychoosekastheirPt.Thein-tervaldecomposesintoS[exk]+Int[i,k]+l[k,j,i]:xkjiFigure5:AnLsub-problemover[i,j]∪{X},kistheneighborofxfurthestfromiintheinterval.S[eik]+Int[k,j]+norte[i,k,X].Asanaside,ifbxwastrue(xneededaparentfromthissub-problem),andkwasachildofx,thenx’sparentmustcomefromthe[i,k]∪{X}sub-problem.However,itcannotbeadescendantofk,asthatwouldcauseacycle.Thusinthiscase,wecallthesub-problemaN_XFromIproblem,toin-dicatethatxneedsaparent,iandkdonot,andxmustbedescendedfromi,notk.4.4DecomposinganLorRsub-problemAnLsub-problemover[i,j]∪{X}requiresthatanyedgesinthisregionthatcrossanedgewithanend-pointatxhaveanendpointati(theleftendpoint).Iftherearenoedgesbetweenxand[i,j]inanLsub-problem,thenitisalsoavalidIntsub-problemover[i,j].Ifthereareedgesbetweenxandiorj,thenthesub-problemcanbedecomposedintothatedgeplustherestoftheforestwiththatedgeremoved.Theinterestingcaseiswhenthereareedgesbe-tweenxandtheinterior(Figura 5).Letkbetheneighborofxwithin(i,j)thatisfurthestfromi.Asalledgesthatcrossexkwillhaveanendpointati,therearenoedgesbetween(i,k)y(k,j].Com-binedwiththefactthatkwastheneighborofxclos-esttoj,wehavethat[i,k]∪{X}mustformaniso-abcdefFigure6:2-planarbutnot1-Endpoint-Crossinglatedcrossingregion,asmust[k,j]∪{i}.Ifthereareadditionaledgesbetweenxandthein-terior(Caseiin5),alloftheedgesfromiinto(k,j]crossboththeedgeexkandtheotheredgesfromxinto(i,k).ThePtforalltheseedgesmustthere-forebex,andasxisnotintheregion[k,j]∪{i},thoseedgescannotbecrossedatallinthatregion(es decir.,[k,j]∪{i}mustbeoftypeN).Iftherearenoadditionaledgesfromxinto(i,k)(CaseiiinFig-ure5),thenalloftheedgesfromiinto(k,j)mustchooseeitherxorkastheirPt.Astherewillbenomoreedgesfromx,choosingkastheirPtallowsstrictlymoretrees,andso[k,j]∪{i}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 mi C t . metro i t . mi d tu / t a C yo / yo a r t i C mi - pag d F / d oh i / . 1 0 1 1 6 2 / t yo a C _ a _ 0 0 2 0 6 1 5 6 6 6 3 9 / / t yo a C _ a _ 0 0 2 0 6 pag d . F b y gramo tu mi s t t oh norte 0 8 S mi pag mi metro b mi r 2 0 2 3 20 (a,b)(a,C)(b,d)(C,mi)(d,F)(a)(a,b)(a,C)(b,mi)(gramo,d)(h,F)(b,gramo)(gramo,h)(b)Figura 7: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,de(1)inShieber(1985):dasmeremHanseshuushälfedaastriichethatweHansDATthehouseACChelpedpaintTheedges(eso,helped),(helped,nosotros),y(helped,Hans)areeachonlycrossedbyanedgewithanendpointatpaint;theedge(paint,house)isonlycrossedbyedgeswithanendpointathelped.Moregenerally,withasetoftwocrossserialverbsinasubordinateclause,eachverbshouldsufficeasthecrossingpointforalledgesincidenttotheotherverbthatarecrossed.Cross-serialconstructionswiththreeormoreverbswouldhavedependencytreesthatviolate1-

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

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

/

/
t

yo

a
C
_
a
_
0
0
2
0
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
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(apenas,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(decir,said1),(said1,said2),y(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[i,j]isthescoreofthedirectededge(i,j)Output:Maximumscoreofa1-Endpoint-Crossingtreeoververtices[0,norte],rootedat0Init:∀iInt[i,i,F,F]=Int[i,i+1,F,F]=0Int[i,i,t,F]=Int[i,i,F,t]=Int[i,i,t,t]=−∞Final:Int[0,norte,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.

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

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

/

/
t

yo

a
C
_
a
_
0
0
2
0
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

22

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

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

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

/

/
t

yo

a
C
_
a
_
0
0
2
0
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

23

R[i,j,X,bi,bj,F]←symmetrictoL[i,j,X,bi,bj,F]R[i,j,X,bi,F,t]←symmetrictoL[i,j,X,F,bj,t]R[i,j,X,bi,t,t]←notreachableR_XFromJ[i,j,X]←symmetrictoL_XFromI[i,j,X]R_JFromX[i,j,X]←symmetrictoL_IFromX[i,j,X]R_IFromX[i,j,X]←symmetrictoL_JFromX[i,j,X]R_IFromJ[i,j,X]←symmetrictoL_JFromI[i,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,CON,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,editores,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.

yo

D
oh
w
norte
oh
a
d
mi
d

F
r
oh
metro
h

t
t

pag

:
/
/

d
i
r
mi
C
t
.

metro

i
t
.

mi
d
tu

/
t

a
C
yo
/

yo

a
r
t
i
C
mi
–
pag
d

F
/

d
oh

i
/

.

1
0
1
1
6
2

/
t

yo

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

/

/
t

yo

a
C
_
a
_
0
0
2
0
6
pag
d

.

F

b
y
gramo
tu
mi
s
t

t

oh
norte
0
8
S
mi
pag
mi
metro
b
mi
r
2
0
2
3

24
Descargar PDF