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 :
Reports
Complete list of metadatas

Cited literature [7 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02102097
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:14:10 AM
Last modification on : Wednesday, November 20, 2019 - 3:13:31 AM

File

RR1995-28.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02102097, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

10

Files downloads

10