Abstract
Quasiperiodic tilings are those tilings in which finite patterns appear regularly in the plane. This property is a generalization of the periodicity; it was introduced for representing quasicrystals and it is also motivated by the study of quasiperiodic words. We prove that if a tile set can tile the plane, then it can tile the plane quasiperiodically — a surprising result that does not hold for periodicity. In order to compare the regularity of quasiperiodic tilings, we introduce and study a quasiperiodicity function and prove that it is bounded by x↦x+c if and only if the considered tiling is periodic. At last, we prove that if a tile set can be used to form a quasiperiodic tiling which is not periodic, then it can form an uncountable number of tilings.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Berger. The undecidability of the domino problem. Memoirs of the American Mathematical Society, 66, 1966.
E. Borger, E. Grädel, and Y. Gurevich. The classical decision problem. Springer-Verlag, 1996.
K. Čulik. An aperiodic set of 13 Wang tiles. Discrete Mathematics, 160:245–251, 1996.
N. Dolbilin. The countability of a tiling family and the periodicity of a tiling. Discrete and Computational Geometry, 13:405–414, 1995.
B. Durand. Self-similarity viewed as a local property via tile sets. In MFCS'96, number 1113 in Lecture Notes in Computer Science, pages 312–323. Springer Verlag, 1996.
Y. Gurevich and I. Koriakov. A remark on Berger's paper on the domino problem. Siberian Journal of Mathematics, 13:459–463, 1972. (in Russian).
K. Ingersent. Matching rules for quasicrystalline tilings, pages 185–212. World Scientific, 1991.
J. Kari. A small aperiodic set of Wang tiles. Discrete Mathematics, 160:259–264, 1996.
L. S. Levitov. Commun. Math. Phys., 119(627), 1988.
M. Nivat and D. Perrin. Automata on infinite words. volume 192 of Lecture Notes in Computer Science. Springer, 1985.
M. Nivat and D. Perrin. Ensembles reconnaissables de mots biinfinis. Canadian Journal of Mathematics, 38:513–537, 1986.
J-E. Pin and D. Perrin. Mots infinis. (to appear) LITP repport 9340, 1993.
R.M. Robinson. Undecidability and nonperiodicity for tilings of the plane. Inventiones Mathematicae, 12:177–209, 1971.
P. Séébold. On the conjugation of standard morphisms. In MFCS'96, volume 113 of Lecture Notes in Computer Science, pages 506–516, 1996.
H. Wang. Proving theorems by pattern recognition II. Bell System Technical Journal, 40:1–41, 1961.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Durand, B. (1997). Tilings and quasiperiodicity. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds) Automata, Languages and Programming. ICALP 1997. Lecture Notes in Computer Science, vol 1256. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-63165-8_165
Download citation
DOI: https://doi.org/10.1007/3-540-63165-8_165
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63165-1
Online ISBN: 978-3-540-69194-5
eBook Packages: Springer Book Archive