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:Isaac Newton Institute Seminar Series
SUMMARY:Descriptive complexity of linear algebra - Holm\,
B (University of Cambridge)
DTSTART;TZID=Europe/London:20120329T140000
DTEND;TZID=Europe/London:20120329T150000
UID:TALK37157AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/37157
DESCRIPTION:An important question that has motivated much work
in finite model theory is that of finding a logic
al characterisation of polynomial-time computabili
ty. That is to say\, to find a logic in which a cl
ass of finite structures is expressible if\, and o
nly if\, membership in the class is decidable in d
eterministic polynomial time (PTIME).\n \nMuch of
the research in this area has focused on the exten
sion of inflationary fixed-point logic by counting
terms (FPC). This logic has been shown to capture
polynomial time on many natural classes of struct
ures\, including all classes of graphs with exclud
ed minors. At the same time\, it is also known tha
t FPC is not expressive enough to capture polynomi
al time on the class of all finite graphs. Noting
that the various examples of properties in PTIME t
hat are not definable in FPC can be reduced to tes
ting the solvability of systems of linear equation
s\, Dawar et al. (2009) introduced the extension o
f fixed-point logic with operators for expressing
matrix rank over finite fields (FPR). Fixed-point
rank logic strictly extends the expressive power o
f FPC while still being contained in PTIME and it
remains an open question whether there are polynom
ial-time properties that are not definable in this
logic.\n \nIn this talk I give an overview of the
main results in the logical study of linear algeb
ra and present new developments in this area. Afte
r reviewing the background to this study\, I defin
e logics with rank operators and discuss some of t
he properties that can be expressed with such logi
cs. In order to delimit the expressive power of FP
R\, I present variations of Ehrenfeucht-Fraï\;
ssé\; games that are suitable for proving no
n-definability in finite-variable rank logics. Usi
ng the rank games\, I show that if we restrict to
rank operators of arity two\, then there are graph
properties that can be defined by first-order log
ic with rank over GF(p) that are not expressible b
y any sentence of fixed-point logic with rank over
GF(q)\, for all distinct primes p and q. Finally\
, I discuss how we can suitably restrict these ran
k games to get an algebraic game equivalence that
can be decided in polynomial time on all classes o
f finite structures. As an application\, this give
s a family of polynomial-time approximations of gr
aph isomorphism that is strictly stronger than the
well-known Weisfeiler-Lehman method.\n
LOCATION:Seminar Room 1\, Newton Institute
CONTACT:Mustapha Amrani
END:VEVENT
END:VCALENDAR