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:Semantics Lunch (Computer Laboratory)
SUMMARY:Logics with Rank Operators - Bjarki Holm (Universi
ty of Cambridge)
DTSTART;TZID=Europe/London:20090223T124500
DTEND;TZID=Europe/London:20090223T140000
UID:TALK17164AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/17164
DESCRIPTION:We consider extensions of first-order logic (FO) a
nd fixed-point logic \n(FP) with operators that co
mpute the rank of a definable matrix over a \nfini
te field. These operators can be seen as generali
sations of more \ntraditional counting operators:
instead of counting the cardinality of a \ndefinab
le set\, they count the dimension of a definable v
ector space.\n\nWe show that all known examples of
polynomial time queries that are not \ndefinable
in FP with counting operators are definable in the
extension \nof FP with rank. The rank operators t
urn out to be surprisingly \nexpressive\, even in
the absence of fixed-point operators. We show tha
t \nFO with rank operators over the prime field of
characteristic p \n(FO+rk(p)) can define determin
istic and symmetric transitive closure. \nThis all
ows us to show that\, on ordered structures and fo
r all prime \nvalues of p\, FO+rk(p) captures the
complexity class MOD(p)-L\, whose \ndescriptive co
mplexity had been previously unknown.\n\nThis is j
oint work with Anuj Dawar as well as Martin Grohe
and Bastian \nLaubner (Berlin Humboldt).\n\n
LOCATION:Room FW26\, Computer Laboratory\, William Gates Bu
ilding
CONTACT:Sam Staton
END:VEVENT
END:VCALENDAR