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:Logic and Semantics Seminar (Computer Laboratory)
SUMMARY:Locally Finite Constraint Satisfaction Problems -
Joanna Ochremiak\, University of Warsaw
DTSTART;TZID=Europe/London:20150515T140000
DTEND;TZID=Europe/London:20150515T150000
UID:TALK58292AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/58292
DESCRIPTION:Many natural computational problems\, such as sati
sfiability and\nsystems of equations\, can be expr
essed in a unified way as constraint\nsatisfaction
problems (CSPs). They can be understood as asking
whether\nthere is a homomorphism between two rela
tional structures over the\nsame signature. We con
sider structures whose elements are built of\nso-c
alled atoms\, and defined using finitely many FO f
ormulas. Both the\ndomain and the number of relati
ons of such structures are usually\ninfinite\, but
thanks to the finite presentation they can be tre
ated as\nan input for algorithms.\n\nA relational
structure T is locally finite is every relation of
T is\nfinite. We use recent results in topologica
l dynamics to prove that it\nis decidable whether
there exists a homomorphism from a relational\nstr
ucture A to a locally finite relational structure
T. As a\ncorollary\, we effectively characterize c
ertain subclasses of CSPs\nsolvable in polynomial
time\, with applications to descriptive complexity
\n.\n\nJoint work with Bartek Klin\, Eryk Kopczyńs
ki and Szymon Toruńczyk.
LOCATION:Computer Laboratory\, William Gates Building\, Roo
m FW11
CONTACT:Jonathan Hayman
END:VEVENT
END:VCALENDAR