00:00:00 / 00:00:00

Appears in collection : GAGTA, Geometric and Asymptotic Group Theory with Applications / Théorie des Groupes Géométrique et Asymptotique - Week 2

Wang's tiles were introduced in the 1960s and have been an inexhaustible source of undecidable problems ever since. They are unit square tiles with colored edges and fixed orientation, which can be placed together provided they share the same color on their common edge. Many decision problems involving Wang tiles follow the same global structure: given a finite set of Wang tiles, is there an algorithm to determine if they tile a particular shape or subset of the infinite grid? If we look for a tiling of the whole grid, this is the domino problem which is known to be undecidable for Z2 and many other groups. In this talk we focus on infinite snake tilings. Originally the infinite snake problem asks is there exists a tiling of a self-avoiding bi-infinite path on the grid Z2. In this talk I present how to expand the scope of domino snake problems to finitely generated groups to understand how the underlying structure affects computability. This is joint work with Nicolás Bitar.

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.20137703
  • Cite this video Aubrun, Nathalie (08/02/2024). Domino snake problems on groups. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.20137703
  • URL https://dx.doi.org/10.24350/CIRM.V.20137703

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow


  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
  • Get notification updates
    for your favorite subjects
Give feedback