The next algorithmic seminar of the Saclay plateau will take place on Friday, September 27 at 14:30 at LRI in room 445 (patio room). Nathalie Aubrun (ENS Lyon) will talk about The Domino Problem is undecidable on surface groups.

Abstract: The domino problem for a finitely generated group asks whether there exists an algorithm which takes as input a finite alphabet and finitely many Wang tiles, and decides whether there exists a tiling of the group by this set of tiles. I will survey known results and present the domino problem conjecture: finitely generated groups with decidable domino problem are exactly virtually free groups. Then I will explain why this problem is undecidable on surface groups. Joint work with Sebastián Barbieri and Etienne Moutot.