The Domino Snake Problem

-- Nicolás Bitar (LISN, Galac)

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

summary: Deep within the swamp of undecidability lies the elusive domino snake. This species, first discovered in the 1970s by Myers, was originally introduced as an a priori simpler problem than the now celebrated Domino Problem. In this talk we will take a tour through what is known about this species, looking at its different variants: the infinite snake problem, the snake rechability problem and the ouroboros problem. We will also see how the infinite snake problem can be reduced to a problem in one-dimensional symbolic dynamics.

Category: seminars
Tags: Team seminar combinatorics