A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes
- Resource Type
- Working Paper
- Authors
- Yang, Chao; Zhang, Zhujun
- Source
- Subject
- Mathematics - Combinatorics
Computer Science - Computational Complexity
Mathematics - Metric Geometry
- Language
We give a proof of Ollinger's conjecture that the problem of tiling the plane with translated copies of a set of $8$ polyominoes is undecidable. The techniques employed in our proof include a different orientation for simulating the Wang tiles in polyomino and a new method for encoding the colors of Wang tiles.