Homomorphism problems for first-order definable structures

Prelegent(ci)

Szymon Toruńczyk

Afiliacja

Uniwersytet Warszawski

Termin

2 marca 2016 14:15

Pokój

p. 5870

Tytuł w języku angielskim

joint work with B.Klin, S. Lasota, J. Ochremiak

Seminarium

Seminarium „Teoria automatów”

---

We prove decidability of the existence of a homomorphism between two given infinite structures with finite signatures which are definable, or interpret, in the natural numbers with equality. The result uses Pestov's theorem from topological dynamics. This completes the landscape of decidability for homomorphism problems for first-order definable structures, studied previously in the talk of Bartek Klin. My talk will be self-contained.

---