Fixed Point and Aperiodic Tilings

DOI10.1007/978-3-540-85780-8_22zbMATH Open1161.68033DBLPconf/dlt/DurandRS08arXiv0802.2432OpenAlexW3104027675WikidataQ57349711 ScholiaQ57349711MaRDI QIDQ3533018FDOQ3533018

Authors: Andrei Romashchenko, A. Shen, Bruno Durand 

Publication date: 30 October 2008

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (19)

• Effective closed subshifts in 1D can be implemented in 2D
• The periodic domino problem revisited
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Two-by-Two Substitution Systems and the Undecidability of the Domino Problem
• An aperiodic set of 11 Wang tiles
• Simulation of effective subshifts by two-dimensional subshifts of finite type
• Fixed-point tile sets and their applications
• Aperiodic tilings and entropy
• Local rules for computable planar tilings
• The undecidability of the domino problem
• Aperiodicity Measure for Infinite Sequences

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)