The 4-way deterministic tiling problem is undecidable
From MaRDI portal
Publication:1013128
DOI10.1016/j.tcs.2008.12.006zbMath1162.03024OpenAlexW2030138929MaRDI QIDQ1013128
Publication date: 16 April 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.006
Undecidability and degrees of sets of sentences (03D35) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)
Related Items
Self-stabilisation of Cellular Automata on Tilings ⋮ On dynamical complexity of surjective ultimately right-expansive cellular automata ⋮ A counterexample to Thiagarajan's conjecture on regular event structures ⋮ Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness ⋮ Undecidable translational tilings with only two tiles, or one nonabelian tile ⋮ An aperiodic set of 11 Wang tiles ⋮ The word and order problems for self-similar and automata groups ⋮ Decidability and undecidability in cellular automata
Cites Work
- Unnamed Item
- Unnamed Item
- Deterministic aperiodic tile sets
- Reversibility and surjectivity problems of cellular automata
- Theory of cellular automata: a survey
- Undecidability and nonperiodicity for tilings of the plane
- Combinatorial optimization problems in self-assembly
- The Nilpotency Problem of One-Dimensional Cellular Automata
- Complexities for Generalized Models of Self-Assembly
- The undecidability of the domino problem