Fixed Point and Aperiodic Tilings

DOI10.1007/978-3-540-85780-8_22MaRDI QIDQ3533018zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Andrei Romashchenko, A. Shen, Bruno Durand

Publication date 30 October 2008

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0802.2432

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Cellular automata (computational aspects) (68Q80)

Abstract: An aperiodic tile set was first constructed by R.Berger while proving the undecidability of the domino problem. It turned out that aperiodic tile sets appear in many topics ranging from logic (the Entscheidungsproblem) to physics (quasicrystals) We present a new construction of an aperiodic tile set that is based on Kleene's fixed-point construction instead of geometric arguments. This construction is similar to J. von Neumann self-reproducing automata; similar ideas were also used by P. Gacs in the context of error-correcting computations. The flexibility of this construction allows us to construct a "robust" aperiodic tile set that does not have periodic (or close to periodic) tilings even if we allow some (sparse enough) tiling errors. This property was not known for any of the existing aperiodic tile sets.

Recommendations

• Fixed-point tile sets and their applications
• Constructing new aperiodic self-simulating tile sets
• High Complexity Tilings with Sparse Errors
• scientific article; zbMATH DE number 1101596
• An aperiodic set of 13 Wang tiles

Cites work

• scientific article; zbMATH DE number 3968590 (Why is no real title available?)
• A reader's guide to P. Gacs's ``positive rates paper: ``Reliable cellular automata with self-organization.
• A small aperiodic set of Wang tiles
• An aperiodic set of 13 Wang tiles
• Complex tilings
• Local rules and global order, or aperiodic tilings
• On the correlation dimension of the spectral measure for the Thue-Morse sequence
• Reliable cellular automata with self-organization
• The undecidability of the domino problem
• Tilings, substitution systems and dynamical systems generated by them

Cited in

(19)

• Aperiodicity Measure for Infinite Sequences
• Effective closed subshifts in 1D can be implemented in 2D
• The periodic domino problem revisited
• scientific article; zbMATH DE number 6730058 (Why is no real title available?)
• Fixed point constructions in tilings and cellular automata (invited talk)
• Deterministic aperiodic tile sets
• Operators, Algebras and Their Invariants for Aperiodic Tilings
• Constructing new aperiodic self-simulating tile sets
• Tilings robust to errors
• Local rules and global order, or aperiodic tilings
• Aperiodic tilings with one prototile and low complexity atlas matching rules
• scientific article; zbMATH DE number 50175 (Why is no real title available?)
• Two-by-Two Substitution Systems and the Undecidability of the Domino Problem
• Simulation of effective subshifts by two-dimensional subshifts of finite type
• An aperiodic set of 11 Wang tiles
• Fixed-point tile sets and their applications
• Aperiodic tilings and entropy
• Local rules for computable planar tilings
• The undecidability of the domino problem

This page was built for publication: Fixed Point and Aperiodic Tilings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3533018)