Fixed Parameter Undecidability for Wang Tilesets

Emmanuel Jeandel, Nicolas Rolin

Type: Article

Publication Date: 2012-08-13

Citations: 3

DOI: https://doi.org/10.4204/eptcs.90.6

Abstract

Deciding if a given set of Wang tiles admits a tiling of the plane is decidable if the number of Wang tiles (or the number of colors) is bounded, for a trivial reason, as there are only finitely many such tilesets. We prove however that the tiling problem remains undecidable if the difference between the number of tiles and the number of colors is bounded by 43. One of the main new tool is the concept of Wang bars, which are equivalently inflated Wang tiles or thin polyominoes.

Locations

arXiv (Cornell University) - View - PDF
DOAJ (DOAJ: Directory of Open Access Journals) - View
HAL (Le Centre pour la Communication Scientifique Directe) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Undecidability of tiling the plane with a fixed number of Wang bars	2024	Chao Yang Zhujun Zhang
+ PDF Chat	The domino problem is decidable for robust tilesets	2024	Nathalie Aubrun Manon Blanc Olivier Bournez
+	Rectangular tileability and complementary tileability are undecidable	2014	Jed Yang
+	Rectangular tileability and complementary tileability are undecidable	2012	Jed Yang
+	A linear algorithm for Brick Wang tiling	2016	Alexandre Derouet‐Jourdan Shizuo Kaji Yoshihiro Mizoguchi
+	Undecidable tiling problems in the hyperbolic plane	1978	Raphael M. Robinson
+ PDF Chat	A New Algorithm Based on Colouring Arguments for Identifying Impossible Polyomino Tiling Problems	2022	Marcus R. Garvie John Burkardt
+ PDF Chat	A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes	2024	Chao Yang Zhujun Zhang
+ PDF Chat	NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles	2024	Chao Yang Zhujun Zhang
+	About the domino problem in the hyperbolic plane, a new solution	2007	Maurice Margenstern
+	The Domino Problem of the Hyperbolic Plane Is Undecidable	2007	Maurice Margenstern
+ PDF Chat	The domino problem of the hyperbolic plane is undecidable	2008	Maurice Margenstern
+	The domino problem of the hyperbolic plane is undecidable, new proof	2022	Maurice Margenstern
+	Low-Complexity Tilings of the Plane	2019	Jarkko Kari
+	Undecidability and nonperiodicity for tilings of the plane	1971	Raphael M. Robinson
+	On the behavior of tile assembly system at high temperatures	2012	Shinnosuke Seki Yasushi Okuno
+	Tiling with arbitrary tiles	2015	Vytautas Gruslys Imre Leader Ta Sheng Tan
+	Tiling the Plane with a Set of Ten Polyominoes	2023	Chao Yang
+	Computability and Tiling Problems	2023	Mark Carney
+	Binary pattern tile set synthesis is NP-hard	2014	Lila Kari Steffen Kopecki Pierre-Étienne Meunier Matthew J. Patitz Shinnosuke Seki

Works That Cite This (2)

Action	Title	Year	Authors
+	Parametrization by Horizontal Constraints in the Study of Algorithmic Properties of $\mathbb{Z}^2$-Subshift of Finite Type	2022	Solène Esnay Mathieu Sablik
+ PDF Chat	An aperiodic set of 11 Wang tiles	2021	Emmanuel Jeandel Michaël Rao

Works Cited by This (1)

Action	Title	Year	Authors
+	The undecidability of the domino problem	1966	Robert E. Berger