Translational Tiling with 8 Polyominoes is Undecidable.
Saved in:
| Title: | Translational Tiling with 8 Polyominoes is Undecidable. |
|---|---|
| Authors: | Yang, Chao1 (AUTHOR) sokoban2007@163.com, Zhang, Zhujun2 (AUTHOR) zhangzhujun1988@163.com |
| Source: | Discrete & Computational Geometry. Jun2026, Vol. 75 Issue 4, p1048-1059. 12p. |
| Subjects: | Tiling (Mathematics), Computational complexity, Tessellations (Mathematics), Mathematics, Recursion theory |
| Abstract: | We show that translational tiling of the plane with a set of 8 polyominoes is undecidable, which answers a question posted by Ollinger. 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. [ABSTRACT FROM AUTHOR] |
| Copyright of Discrete & Computational Geometry is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
|
Full text is not displayed to guests.
Login for full access.
|
|
| Abstract: | We show that translational tiling of the plane with a set of 8 polyominoes is undecidable, which answers a question posted by Ollinger. 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. [ABSTRACT FROM AUTHOR] |
|---|---|
| ISSN: | 01795376 |
| DOI: | 10.1007/s00454-024-00706-1 |
