BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Logics with Rank Operators - Bjarki Holm (University of Cambridge)
DTSTART:20090223T124500Z
DTEND:20090223T140000Z
UID:TALK17164@talks.cam.ac.uk
CONTACT:Sam Staton
DESCRIPTION:We consider extensions of first-order logic (FO) and fixed-poi
 nt logic \n(FP) with operators that compute the rank of a definable matrix
  over a \nfinite field.  These operators can be seen as generalisations of
  more \ntraditional counting operators: instead of counting the cardinalit
 y of a \ndefinable set\, they count the dimension of a definable vector sp
 ace.\n\nWe show that all known examples of polynomial time queries that ar
 e not \ndefinable in FP with counting operators are definable in the exten
 sion \nof FP with rank. The rank operators turn out to be surprisingly \ne
 xpressive\, even in the absence of fixed-point operators.  We show that \n
 FO with rank operators over the prime field of characteristic p \n(FO+rk(p
 )) can define deterministic and symmetric transitive closure. \nThis allow
 s us to show that\, on ordered structures and for 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 joint work with Anuj Dawa
 r as well as Martin Grohe and Bastian \nLaubner (Berlin Humboldt).\n\n
LOCATION:Room FW26\, Computer Laboratory\, William Gates Building
END:VEVENT
END:VCALENDAR