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:Computation via Substructures - Ramanathan S. Thin
niyam\, MPI-SWS
DTSTART;TZID=Europe/London:20200224T140000
DTEND;TZID=Europe/London:20200224T150000
UID:TALK139939AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/139939
DESCRIPTION:Hilbert's Tenth problem asks if the existential fr
agment of natural number arithmetic is decidable.
The DPRM theorem resolved this in the negative\, b
ut in doing so established a stronger result: the
definable sets (i.e.\, the Diophantine Sets) are p
recisely the recursively enumerable sets of number
s.\n\nRecently\, a surprising result of Halfon\, S
chnoebelen\, Zetzsche showed that arithmetic is ex
istentially definable in the subword order with co
nstants\, implying the undecidability of the corre
sponding existential fragment. This raises the nat
ural question of whether the stronger result holds
: is every recursively enumerable set of words exi
stentially definable in the subword order with con
stants?\n\nWe present some initial results towards
showing that the above conjecture is true and dis
cuss the case of graphs and the induced subgraph o
rder\, for which coarser results were obtained in
the speaker's PhD thesis.
LOCATION:Computer Laboratory\, room SS03
CONTACT:Jean Pichon-Pharabod
END:VEVENT
END:VCALENDAR