Undecidability of tiling the plane with a fixed number of Wang bars
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_ | 1866914235280261120 |
|---|---|
| author | Yang, Chao Zhang, Zhujun |
| author_facet | Yang, Chao Zhang, Zhujun |
| contents | To study the fixed parameter undecidability of tiling problem for a set of Wang tiles, Jeandel and Rolin show that the tiling problem for a set of 44 Wang bars is undecidable. In this paper, we improve their result by proving that whether a set of 29 Wang bars can tile the plane is undecidable. As a consequence, the tiling problem for a set of Wang tiles with color deficiency of 25 is also undecidable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_04504 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Undecidability of tiling the plane with a fixed number of Wang bars Yang, Chao Zhang, Zhujun Combinatorics Computational Complexity Metric Geometry To study the fixed parameter undecidability of tiling problem for a set of Wang tiles, Jeandel and Rolin show that the tiling problem for a set of 44 Wang bars is undecidable. In this paper, we improve their result by proving that whether a set of 29 Wang bars can tile the plane is undecidable. As a consequence, the tiling problem for a set of Wang tiles with color deficiency of 25 is also undecidable. |
| title | Undecidability of tiling the plane with a fixed number of Wang bars |
| topic | Combinatorics Computational Complexity Metric Geometry |
| url | https://arxiv.org/abs/2404.04504 |