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

• 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
• scientific article; zbMATH DE number 3968590 (Why is no real title available?)
• 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)

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

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)