Decidability and Periodicity of Low Complexity Tilings
share
We investigate the tiling problem, also known as the domino problem, that asks whether the two-dimensional grid Z^2 can be colored in a way that avoids a given finite collection of forbidden local patterns. The problem is well-known to be undecidable in its full generality. We consider the low complexity setup where the number of allowed local patterns is small. More precisely, suppose we are given at most nm legal rectangular patterns of size n x m, and we want to know whether there exists a coloring of Z^2 containing only legal n x m patterns. We prove that if such a coloring exists then also a periodic coloring exists. This further implies, using standard arguments, that in this setup there is an algorithm to determine if the given patterns admit at least one coloring of the grid. The results also extend to other convex shapes in place of the rectangle.
READ FULL TEXT