The 4-way deterministic tiling problem is undecidable

DOI10.1016/J.TCS.2008.12.006MaRDI QIDQ1013128zbMATH OpenOpenAlexFDO

Authors 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

Wang tilesundecidabilitydeterministic tilesdomino problemtiling problem

Mathematics Subject Classification ID

Tilings in (2) dimensions (aspects of discrete geometry) (52C20) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Fixed parameter undecidability for Wang tilesets
• On the Undecidability of the Tiling Problem
• The undecidability of the domino problem
• The Tiling Problem Revisited (Extended Abstract)
• Tiling the Plane with a Fixed Number of Polyominoes

Cites work

• scientific article; zbMATH DE number 3550181 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Combinatorial optimization problems in self-assembly
• Complexities for Generalized Models of Self-Assembly
• Deterministic aperiodic tile sets
• Reversibility and surjectivity problems of cellular automata
• The Nilpotency Problem of One-Dimensional Cellular Automata
• The undecidability of the domino problem
• Theory of cellular automata: a survey
• Undecidability and nonperiodicity for tilings of the plane

Cited in

(14)

• Decidability and undecidability in cellular automata
• Undecidable translational tilings with only two tiles, or one nonabelian tile
• Piecewise affine functions, Sturmian sequences and Wang tiles
• Tiling problems and undecidability in the cluster variation method.
• Self-stabilisation of Cellular Automata on Tilings
• Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness
• On dynamical complexity of surjective ultimately right-expansive cellular automata
• Fixed parameter undecidability for Wang tilesets
• The word and order problems for self-similar and automata groups
• A counterexample to Thiagarajan's conjecture on regular event structures
• An aperiodic set of 11 Wang tiles
• On the Undecidability of the Tiling Problem
• Tetris and decidability
• Knight tiles: particles and collisions in the realm of 4-way deterministic tilings

This page was built for publication: The 4-way deterministic tiling problem is undecidable

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