BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Computation via Substructures - Ramanathan S. Thinniyam\, MPI-SWS
DTSTART:20200224T140000Z
DTEND:20200224T150000Z
UID:TALK139939@talks.cam.ac.uk
CONTACT:Jean Pichon-Pharabod
DESCRIPTION:Hilbert's Tenth problem asks if the existential fragment of na
 tural number arithmetic is decidable. The DPRM theorem resolved this in th
 e negative\, but in doing so established a stronger result: the definable 
 sets (i.e.\, the Diophantine Sets) are precisely the recursively enumerabl
 e sets of numbers.\n\nRecently\, a surprising result of Halfon\, Schnoebel
 en\, Zetzsche showed that arithmetic is existentially definable in the sub
 word order with constants\, implying the undecidability of the correspondi
 ng existential fragment. This raises the natural question of whether the s
 tronger result holds: is every recursively enumerable set of words existen
 tially definable in the subword order with constants?\n\nWe present some i
 nitial results towards showing that the above conjecture is true and discu
 ss the case of graphs and the induced subgraph order\, for which coarser r
 esults were obtained in the speaker's PhD thesis.
LOCATION:Computer Laboratory\, room SS03
END:VEVENT
END:VCALENDAR