Two-by-Two Substitution Systems and the Undecidability of the Domino Problem

DOI10.1007/978-3-540-69407-6_51MaRDI QIDQ3507464zbMATH OpenOpenAlexFDO

Authors Nicolas Ollinger

Publication date 19 June 2008

Published in Logic and Theory of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-69407-6_51

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Combinatorial aspects of tessellation and tiling problems (05B45)

Recommendations

• The undecidability of the domino problem
• Tilings, substitution systems and dynamical systems generated by them
• A codicity undecidable problem in the plane.
• The periodic domino problem revisited
• Fixed-point tile sets and their applications

Cites work

• An Introduction to Symbolic Dynamics and Coding
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• Fixed Point and Aperiodic Tilings
• scientific article; zbMATH DE number 45409 (Why is no real title available?)
• scientific article; zbMATH DE number 1327765 (Why is no real title available?)
• Local rules and global order, or aperiodic tilings
• The Nilpotency Problem of One-Dimensional Cellular Automata
• The Tiling Problem Revisited (Extended Abstract)
• The undecidability of the domino problem
• Tilings, substitution systems and dynamical systems generated by them

Cited in

(24)

• Tilings, substitution systems and dynamical systems generated by them
• On the domino problem of the Baumslag-Solitar groups
• Slopes of multidimensional subshifts
• A self-similar aperiodic set of 19 Wang tiles
• Substitutive structure of Jeandel-Rao aperiodic tilings
• Substitutions and strongly deterministic tilesets
• Quasiperiodicity and non-computability in tilings
• The domino problem for self-similar structures
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• Quelles tuiles ! (Pavages apériodiques du plan et automates bidimensionnels)
• Constructing new aperiodic self-simulating tile sets
• Effective closed subshifts in 1D can be implemented in 2D
• The periodic domino problem revisited
• Fixed-point tile sets and their applications
• The expressiveness of quasiperiodic and minimal shifts of finite type
• Aperiodic tilings and entropy
• The undecidability of the domino problem
• An aperiodic set of 11 Wang tiles
• Parametrization by horizontal constraints in the study of algorithmic properties of \(\mathbb{Z}^2\)-subshifts of finite type
• Undecidable translational tilings with only two tiles, or one nonabelian tile
• Deterministic coloring of a family of complexes
• Various questions around finitely positively expansive dynamical systems
• Metallic mean Wang tiles. II: The dynamics of an aperiodic computer chip
• Spectral approximation for substitution systems

This page was built for publication: Two-by-Two Substitution Systems and the Undecidability of the Domino Problem

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