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

DOI10.1007/978-3-540-69407-6_51zbMath1142.03357OpenAlexW1512081522MaRDI QIDQ3507464

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)

Related Items

Substitutive structure of Jeandel-Rao aperiodic tilings ⋮ Quasiperiodicity and Non-computability in Tilings ⋮ The periodic domino problem revisited ⋮ Undecidable translational tilings with only two tiles, or one nonabelian tile ⋮ Fixed-point tile sets and their applications ⋮ The Undecidability of the Domino Problem ⋮ Aperiodic tilings and entropy ⋮ An aperiodic set of 11 Wang tiles ⋮ Constructing New Aperiodic Self-simulating Tile Sets ⋮ The expressiveness of quasiperiodic and minimal shifts of finite type ⋮ Slopes of multidimensional subshifts ⋮ A self-similar aperiodic set of 19 Wang tiles

Cites Work

• Unnamed Item
• Unnamed Item
• Local rules and global order, or aperiodic tilings
• Tilings, substitution systems and dynamical systems generated by them
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• Fixed Point and Aperiodic Tilings
• The Tiling Problem Revisited (Extended Abstract)
• The Nilpotency Problem of One-Dimensional Cellular Automata
• An Introduction to Symbolic Dynamics and Coding
• The undecidability of the domino problem