Tilings, substitution systems and dynamical systems generated by them.

*(English)*Zbl 0745.52013The 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.

Reviewer: J.-P.Allouche (Bordeaux)

##### MSC:

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 |

##### Keywords:

tiling system; dynamical system; substitution systems; undecidability of the tiling problem
Full Text:
DOI

##### References:

[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.