• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

The 4-way Deterministic Tiling Problem is Undecidable

Ville Lukkarila, The 4-way Deterministic Tiling Problem is Undecidable. Theoretical Computer Science 410(16), 1516–1533, 2009.

Abstract:

It is shown that the (infinite) tiling problem by Wang tiles is undecidable even if the given tile
set is deterministic by all four corners, i.e. a tile is uniquely determined by the colors of any
two adjacent edges. The reduction is done from the Turing machine halting problem and uses
the aperiodic tile set of Kari and Papasoglu.

BibTeX entry:

@ARTICLE{jLukkarila09a,
  title = {The 4-way Deterministic Tiling Problem is Undecidable},
  author = {Lukkarila, Ville},
  journal = {Theoretical Computer Science},
  volume = {410},
  number = {16},
  pages = {1516–1533},
  year = {2009},
  keywords = {Deterministic tiles, Domino problem, Tiling problem, Undecidability, Wang tiles},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 2

Edit publication