Homomorphism problems for first-order definable structures

Prelegent(ci)

Bartek Klin

Afiliacja

Uniwersytet Warszawski

Termin

27 stycznia 2016 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with S. Lasota, J. Ochremiak and S. Toruńczyk

Seminarium

Seminarium „Teoria automatów”

---

Consider infinite relational structures where both the universe and the relations are definable by first-order formulas over natural numbers with equality. An example of such a structure is the countable clique graph, or a graph where nodes are 2-element sets of numbers and two nodes are adjacent iff they have interesection of size 1.

Consider the decidability of the homomorphism problem for such structures: given (the finite definitions of) structures A and B over the same signature, is there a homomorphism from A to B? I will explain a few variants of this problem; their landscape of decidability would make Lewis Carroll scratch his head in confusion.

---