The 4-way deterministic tiling problem is undecidable

DOI10.1016/j.tcs.2008.12.006zbMath1162.03024OpenAlexW2030138929MaRDI QIDQ1013128

Ville Lukkarila

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

zbMATH Keywords

undecidabilityWang tilesdeterministic tilesdomino problemtiling problem

Mathematics Subject Classification ID

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