Laboratoire d'informatique de l'École polytechnique

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.