Periodicity and decidability of tilings of ℤ2
Siddhartha Bhattacharya
Abstract
We prove that any finite set $F\subset{\Bbb Z}^2$ that tiles ${\Bbb Z}^2$ by translations also admits a periodic tiling. As a consequence, the problem whether a given finite set $F$ tiles ${\Bbb Z}^2$ is decidable.
Topics & Concepts
DecidabilityMathematicsCombinatoricsSet (abstract data type)Finite setDiscrete mathematicsPure mathematicsMathematical analysisComputer scienceProgramming languageQuasicrystal Structures and PropertiesMathematical Analysis and Transform MethodsCellular Automata and Applications