Skip to Main content Skip to Navigation

Pavages du plan : indecidabilite et periodicite.

Abstract : We study some decision problems concerning the tiling of the plane with Wang tiles. We present a proof for the undecidability of the tiling problem for the whole plane, and also for the periodic tiling. In these poofs, an aperiodic tile set is constructed. We are interested in the second part in the link between the cardinality of possible tilings of the plane with a given tile set and the existence of a periodic tiling. We are also interested in the property of quasiperiodicity and prove that all tile sets that tile the plane, may tile the plane quasiperiodically.
Document type :
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:14:10 AM
Last modification on : Saturday, September 11, 2021 - 3:19:12 AM


Files produced by the author(s)


  • HAL Id : hal-02102097, version 1



Cyril Allauzen, Bruno Durand. Pavages du plan : indecidabilite et periodicite.. [Rapport de recherche] LIP RR-1995-28, Laboratoire de l'informatique du parallélisme. 1995, 2+28p. ⟨hal-02102097⟩



Les métriques sont temporairement indisponibles