zbMATH — the first resource for mathematics

Tilings and quasiperiodicity. (English) Zbl 1062.05502
Summary: Quasiperiodic tilings are those tilings in which finite patterns appear regularly in the plane. This property is a generalization of 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 positive 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\mapsto x+c\) if and only if the considered tiling is periodic. Finally, 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.

05B45 Combinatorial aspects of tessellation and tiling problems
52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
Full Text: DOI
[1] Allauzen, C.; Durand, B., Appendix A: tiling problems, (), 407-420
[2] Berger, R., The undecidability of the domino problem, Mem. am. math. soc., 66, (1966) · Zbl 0199.30802
[3] Börger, E.; Grädel, E.; Gurevich, Y., The classical decision problem, (1996), Springer Berlin
[4] Brown, T.C., Description of the characteristic sequence of an irrational, Canad. math. bull., 36, 15-21, (1993) · Zbl 0804.11021
[5] Cˇulik, K., An aperiodic set of 13 Wang tiles, Discrete math., 160, 245-251, (1996) · Zbl 0865.05033
[6] de Luca, A., Sturmian words: structure, combinatorics, and their arithmetics, Theoret. comput. sci., 183, 1, 45-82, (1997) · Zbl 0911.68098
[7] de Luca, A.; Varricchio, S., Chapter regularity and finiteness conditions, (), 747-810
[8] Dolbilin, N., The countability of a tiling family and the periodicity of a tiling, Discrete comput. geom., 13, 405-414, (1995) · Zbl 0824.52024
[9] Durand, B., Self-similarity viewed as a local property via tile sets, (), 312-323, number 1113 in · Zbl 0886.05045
[10] Furstenberg, H., Recurrence in ergodic theory and combinatorial number theory, (1981), Princetown University Press Princeton, NJ · Zbl 0459.28023
[11] Gurevich, Y.; Koriakov, I., A remark on Berger’s paper on the domino problem, Siberian J. math., 13, 459-463, (1972), (in Russian)
[12] Ingersent, K., Matching rules for quasicrystalline tilings, (), 185-212
[13] Kari, J., A small aperiodic set of Wang tiles, Discrete math., 160, 259-264, (1996) · Zbl 0861.05017
[14] Levitov, L.S., Commun. math. phys., 119, 627, (1988)
[15] Nivat, M.; Perrin, D., Automata on infinite words, () · Zbl 0563.00019
[16] Nivat, M.; Perrin, D., Ensembles reconnaissables de mots biinfinis, Canadian J. math., 38, 513-537, (1986) · Zbl 0619.68067
[17] D. Perrin, J-E. Pin, Mots Infinis, book in preparation.
[18] Robinson, R.M., Undecidability and nonperiodicity for tilings of the plane, Invent. math., 12, 177-209, (1971) · Zbl 0197.46801
[19] Séébold, P., On the conjugation of standard morphisms, (), 506-516 · Zbl 0889.68094
[20] Wang, H., Proving theorems by pattern recognition II, Bell system tech. J., 40, 1-41, (1961)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.