Tiling with three polygons is undecidable

DOI10.4230/LIPICS.SOCG.2025.39MaRDI QIDQ7312685zbMATH OpenFDO

Authors Erik D. Demaine, Stefan Langerman

Publication date 11 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2025.39

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Quasicrystals and aperiodic tilings in discrete geometry (52C23)

Cites work

• A tutorial on computable analysis
• An aperiodic set of 11 Wang tiles
• Classes of Recursively Enumerable Sets and Their Decision Problems
• scientific article; zbMATH DE number 3968590 (Why is no real title available?)
• scientific article; zbMATH DE number 17705 (Why is no real title available?)
• Periodicity and decidability of tilings of \(\mathbb{Z}^2\)
• The complexity of small universal Turing machines: A survey
• The undecidability of the domino problem
• Tiling the Plane with a Fixed Number of Polyominoes
• Tiling the plane with a set of ten polyominoes
• Tiling with sets of polyominoes
• Undecidability and nonperiodicity for tilings of the plane
• Undecidable translational tilings with only two tiles, or one nonabelian tile

This page was built for publication: Tiling with three polygons is undecidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7312685)