The Domino Problem is undecidable on surface groups

-- Nathalie Aubrun (ENS lyon)

Time: 14:30 -- Location: LRI, 445

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

Category: seminars
Tags: Plateau seminar