BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY: Mildly non-projective dependency parsing: algorithms and applicat
 ions - Carlos Gómez - University of Corunna
DTSTART:20090529T110000Z
DTEND:20090529T120000Z
UID:TALK18479@talks.cam.ac.uk
CONTACT:Johanna Geiss
DESCRIPTION:Although non-projective syntactic constructions occur in natur
 al languages\, many practical implementations of dependency parsing are re
 stricted to projective structures for efficiency reasons\, since the probl
 em of unrestricted non-projective dependency parsing is intractable in the
  general case. However\, it has been observed that most non-projective str
 uctures appearing in practice are close to being projective. This has led 
 researchers to study sets of mildly non-projective dependency structures\,
  i.e.\, classes of dependency structures that lie between projective and u
 nrestricted non-projective structures\, in the search for a balance betwee
 n coverage and efficiency.  \n\n\nIn the first part of this talk\, I will 
 define a deductive formalism to describe dependency parsers\, based on Sik
 kel's parsing schemata for constituency parsers\; and show examples of how
  it can be used to describe\, analyse and compare well-known projective an
 d non-projective parsers. I will then use this formalism to define polynom
 ial-time parsing algorithms for several classes of mildly non-projective d
 ependency structures\, including that of well-nested structures with gap d
 egree bounded by a constant k\, and a new class of structures with gap deg
 ree up to k (including some ill-nested structures) which contains all the 
 structures in a number of dependency treebanks. Finally\, I will show how 
 a variant of the latter algorithm can be employed to solve a non-parsing p
 roblem: binarising linear context-free rewriting systems without increasin
 g their fan-out in all the cases where this is possible.\n\n\nThe research
  presented in this talk is joint work with David Weir\, John Carroll\, Mar
 co Kuhlmann and Giorgio Satta.\n\n
LOCATION:SW01\, Computer Laboratory
END:VEVENT
END:VCALENDAR