Le problème du domino sur les pavages par losanges

Un pavage est un recouvrement du plan par des tuiles qui ne se chevauchent pas. On appelle sous-shift un ensemble de pavages qui est invariant par translation et fermé (pour la topologie habituelle sur les pavages). Ici on s’intéresse au cas où il y a un nombre fini de tuiles à translation près, les tuiles sont des losanges, et, à chaque fois que deux tuiles sont adjacentes, elles partagent soit un unique sommet en commun soit une arête entière en commun. Sur ces pavages, on peut imposer des règles locales (à la manière des tuiles de Wang) en ajoutant des couleurs sur les arêtes des tuiles avec la règle que deux tuiles qui partagent une arête doivent avoir la même couleur pour cette arête. Dans ce cas, pour une même tuile géométrique, on peut avoir plusieurs copies avec des couleurs différentes sur les arêtes.

Étant donné un sous-shift \(X\) de pavages par losanges, le problème du domino sur \(X\) prend en entrée un ensemble fini de règles locales \(F\) et renvoie Vrai si il existe un pavage de \(X\) qui respecte les règles locales \(F\) et Faux dans le cas contraire. Ce problème est \(\Pi_1^0\)-difficile et nous allons présenter une réduction many-one depuis le problème du domino classique sur les tuiles de Wang.