EUVIMEDEUVIMED entdecken
Crossref

An aperiodic set of 11 Wang tiles

Emmanuel Jeandel, Michaël Rao

Advances in Combinatorics · 11.01.2021

DOI: 10.19086/aic.18614 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Advances in Combinatorics, online erschienen am 11.01.2021. Verfasst von Emmanuel Jeandel und 1 weiteren Autor:innen. Die Arbeit wurde bisher 25-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A [Wang tile](https://en.wikipedia.org/wiki/Wang_tile) is a square tile such that each of its edges is colored. The plane can be _tiled_ with a set of Wang tiles if tiles contained in the set can be placed in the plane without rotations and reflections such that the whole plane is covered and the colors of their edges match at adjacent tiles. Wang tiles were introduced by [Wang](https://en.wikipedia.org/wiki/Hao_Wang_(academic)) in 1961 to study decidability in mathematical logic, and they are also of relevance to other areas of theoretical computer science. Wang conjectured that if the plane can be tiled with a set of Wang tiles, then it can be tiled in a periodic way. This was refuted by [Berger](https://en.wikipedia.org/wiki/Robert_Berger_(mathematician)) in 1966 who described how a Turing machine computation can be emulated by Wang tilings and constructed a set of 104 Wang tiles for which the plane can be tiled with the set but only aperiodically. In the first volume of [The Art of Computer Programming](https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming), Knuth presented a simplified version of Berger's set with 92 Wang tiles. Smaller sets of Wang tiles that tile the plane only aperiodically were subsequently constructed with the smallest set containing 13 Wang tiles, found by Culik II in 1996. The authors construct a set of 11 Wang tiles with edges colored with four colors such that the plane can be tiled with the set but each tiling is aperiodic. Moreover, they establish that there is no set of at most 10 Wang tiles with this property. The number of colors is also the best possible as it is known that every set of Wang tiles with edges colored with at most three colors either can tile the plane periodically or cannot tile the plane at all.

Zitieren

APA

Jeandel, E., & Rao, M. (2021). An aperiodic set of 11 Wang tiles. Advances in Combinatorics. https://doi.org/10.19086/aic.18614

Vancouver

Jeandel E, Rao M. An aperiodic set of 11 Wang tiles. Advances in Combinatorics. 2021. doi:10.19086/aic.18614

BibTeX
@article{Jeandel2021,
  author = {Jeandel, Emmanuel and Rao, Michaël},
  title = {An aperiodic set of 11 Wang tiles},
  journal = {Advances in Combinatorics},
  year = {2021},
  doi = {10.19086/aic.18614}
}
Kostenlos starten →