# Talk by Nathalie Aubrun (at LRI): «The Domino Problem is undecidable on surface groups»

**Speaker:**Nathalie Aubrun (ENS Lyon)

**Location:**Room 445, LRI

**Date:**Fri, 27 Sep 2019, 14:30-15:30

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.