Nie jesteś zalogowany | Zaloguj się

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
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.