BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:NLIP Seminar Series
SUMMARY: Mildly non-projective dependency parsing: algorit
hms and applications - Carlos Gómez - University o
f Corunna
DTSTART;TZID=Europe/London:20090529T120000
DTEND;TZID=Europe/London:20090529T130000
UID:TALK18479AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/18479
DESCRIPTION:Although non-projective syntactic constructions oc
cur in natural languages\, many practical implemen
tations of dependency parsing are restricted to pr
ojective structures for efficiency reasons\, since
the problem of unrestricted non-projective depend
ency parsing is intractable in the general case. H
owever\, it has been observed that most non-projec
tive structures appearing in practice are close to
being projective. This has led researchers to stu
dy sets of mildly non-projective dependency struct
ures\, i.e.\, classes of dependency structures tha
t lie between projective and unrestricted non-proj
ective structures\, in the search for a balance be
tween coverage and efficiency. \n\n\nIn the first
part of this talk\, I will define a deductive for
malism to describe dependency parsers\, based on S
ikkel's parsing schemata for constituency parsers\
; and show examples of how it can be used to descr
ibe\, analyse and compare well-known projective an
d non-projective parsers. I will then use this for
malism to define polynomial-time parsing algorithm
s for several classes of mildly non-projective dep
endency structures\, including that of well-nested
structures with gap degree bounded by a constant
k\, and a new class of structures with gap degree
up to k (including some ill-nested structures) whi
ch contains all the structures in a number of depe
ndency treebanks. Finally\, I will show how a vari
ant of the latter algorithm can be employed to sol
ve a non-parsing problem: binarising linear contex
t-free rewriting systems without increasing their
fan-out in all the cases where this is possible.\n
\n\nThe research presented in this talk is joint w
ork with David Weir\, John Carroll\, Marco Kuhlman
n and Giorgio Satta.\n\n
LOCATION:SW01\, Computer Laboratory
CONTACT:Johanna Geiss
END:VEVENT
END:VCALENDAR