Two-by-Two Substitution Systems and the Undecidability of the Domino Problem
From MaRDI portal
Publication:3507464
DOI10.1007/978-3-540-69407-6_51zbMath1142.03357OpenAlexW1512081522MaRDI QIDQ3507464
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
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