Nonemptiness problems of plane square tiling with two colors

Wen Guei Hu*, Song-Sun Lin

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


This investigation studies nonemptiness problems of plane square tiling. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges of p colors are arranged side by side such that adjacent tiles have the same colors. Given a set of Wang tiles B, the nonemptiness problem is to determine whether or not ∑(ß) ≠ Φ, where ∑(ß) is the set of all global patterns on ℤ2 that can be constructed from the Wang tiles in ß. When p ≥ 5, the problem is well known to be undecidable. This work proves that when p = 2, the problem is decidable. P(ß) is the set of all periodic patterns on ℤ2 that can be generated by B. If P(ß) ≠ Φ, then ßhas a subset B' of minimal cycle generator such that P(B') ≠ Φ and P(B") = Φ for B" ≠ B'. This study demonstrates that the set of all minimal cycle generators C(2) contains 38 elements. N(2) is the set of all maximal noncycle generators: if ßε N(2), then P(ß) = Φ and ß̃≠ ßimplies P(ß̃) ≠ Φ. N(2) has eight elements. That ∑(ß) = Φ for any ßεN(2) is proven, implying that if ∑(ß) ≠ Φ, then P(ß) ≠ Φ. The problem is decidable for p = 2: ∑(ß) ≠ Φ if and only if ßhas a subset of minimal cycle generators. The approach can be applied to corner coloring with a slight modification, and similar results hold.

Original languageEnglish
Pages (from-to)1045-1059
Number of pages15
JournalProceedings of the American Mathematical Society
Issue number3
StatePublished - 1 Mar 2011

Fingerprint Dive into the research topics of 'Nonemptiness problems of plane square tiling with two colors'. Together they form a unique fingerprint.

Cite this