zbMATH — the first resource for mathematics

Tilings, substitution systems and dynamical systems generated by them. (English) Zbl 0745.52013
The tiling problem is the question whether, given a finite set of unit square domain tiles with certain adjacency rules (“tiling system”), there exists a tiling of the entire plane using copies of these tiles: this problem has been proved undecidable by Berger. The author of the paper under review associates to a tiling system a dynamical system consisting of all tilings of the planes using this tiling system with the natural action of \(\mathbb{Z}^ 2\) by translations. He addresses the question of checking what classes of dynamical systems can be realized this way. He studies in particular relations between \(2-D\) substitution systems and tiling systems from the point of view of dynamical systems, giving several nice examples. Finally he sketches a new proof of the undecidability of the tiling problem.

52C20 Tilings in \(2\) dimensions (aspects of discrete geometry)
54H20 Topological dynamics (MSC2010)
05B45 Combinatorial aspects of tessellation and tiling problems
11B85 Automata sequences
03D05 Automata and formal grammars in connection with logical questions
28D99 Measure-theoretic ergodic theory
37-XX Dynamical systems and ergodic theory
Full Text: DOI
[1] R. Berger,The undecidability of the Domino Problem, Mem. Am. Math. Soc. No. 66 (1966). · Zbl 0199.30802
[2] W. H. Gottschalk and G. A. Hedlund,Topological Dynamics, Am. Math. Soc. Colloq. Publ., 1955.
[3] J. C. Martin,Substitutional minimal flows, Am. J. Math.93 (1971).
[4] J. C. Martin,Minimal flows arising from substitutions of non-constant length, Math. Systems. Theory7 (1973). · Zbl 0256.54026
[5] K. Petersen,Ergodic theory, Cambridge University Press, 1983. · Zbl 0507.28010
[6] R. Robinson,Undecidability and nonperidocity for tilings of the plane, Invent. Math.12 (1971). · Zbl 0197.46801
[7] H. Wang,Proving theorems by pattern recognition–II, Bell System Tech. J.40 (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.