joint work with B.Klin, S. Lasota, J. Ochremiak
- Speaker(s)
- Szymon Toruńczyk
- Affiliation
- Uniwersytet Warszawski
- Date
- March 2, 2016, 2:15 p.m.
- Room
- room 5870
- Seminar
- Seminar Automata Theory
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.