University of Cambridge > > Logic and Semantics Seminar (Computer Laboratory) > Computation via Substructures

Computation via Substructures

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity