Computation via Substructures

Add to your list(s) Download to your calendar using vCal

• Ramanathan S. Thinniyam, MPI-SWS
• Monday 24 February 2020, 14:00-15:00
• Computer Laboratory, room SS03.

If you have a question about this talk, please contact Jean Pichon-Pharabod.

Hilbert’s Tenth problem asks if the existential fragment of natural number arithmetic is decidable. The DPRM theorem resolved this in the negative, but in doing so established a stronger result: the definable sets (i.e., the Diophantine Sets) are precisely the recursively enumerable sets of numbers.

Recently, a surprising result of Halfon, Schnoebelen, Zetzsche showed that arithmetic is existentially definable in the subword order with constants, implying the undecidability of the corresponding existential fragment. This raises the natural question of whether the stronger result holds: is every recursively enumerable set of words existentially definable in the subword order with constants?

We present some initial results towards showing that the above conjecture is true and discuss the case of graphs and the induced subgraph order, for which coarser results were obtained in the speaker’s PhD thesis.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computer Laboratory, room SS03
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.