REVIEW 3 cited by
Undecidability of translational monotilings
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
abstract
In the 60's, Berger famously showed that translational tilings of $\mathbb{Z}^2$ with multiple tiles are algorithmically undecidable. Recently, Bhattacharya proved the decidability of translational monotilings (tilings by translations of a single tile) in $\mathbb{Z}^2$. The decidability of translational monotilings in higher dimensions remained unsolved. In this paper, by combining our recently developed techniques with ideas introduced by Aanderaa and Lewis, we finally settle this problem, achieving the undecidability of translational monotilings of (periodic subsets of) virtually $\mathbb{Z}^2$ spaces, namely, spaces of the form $\mathbb{Z}^2\times G_0$, where $G_0$ is a finite Abelian group. This also implies the undecidability of translational monotilings in $\mathbb{Z}^d$, $d\geq 3$.
Forward citations
Cited by 3 Pith papers
-
Undecidability of Translational Tiling with 2 Polycubes
The translational tiling problem for Z^3 is undecidable even for a set of two connected polycubes.
-
Undecidability of Translational Tiling of the Plane with Orthogonally Convex Polyominoes
Translational tiling of the plane with a set of seven orthogonally convex polyominoes is undecidable.
-
Undecidability of Translational Tiling with Three Tiles
Deciding translational tiling of Z^4 by three connected polyhypercubes is undecidable, shown by reduction from Wang's domino problem.
Discussion (0). Continue with ORCID to comment.