A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910731974213632 |
|---|---|
| author | Yang, Chao Zhang, Zhujun |
| author_facet | Yang, Chao Zhang, Zhujun |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_13472 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes Yang, Chao Zhang, Zhujun Combinatorics Computational Complexity Metric Geometry 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. |
| title | A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes |
| topic | Combinatorics Computational Complexity Metric Geometry |
| url | https://arxiv.org/abs/2403.13472 |