TY - JOUR

T1 - Nonemptiness problems of plane square tiling with two colors

AU - Hu, Wen Guei

AU - Lin, Song-Sun

PY - 2011/3/1

Y1 - 2011/3/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79951821326&partnerID=8YFLogxK

U2 - 10.1090/S0002-9939-2010-10518-X

DO - 10.1090/S0002-9939-2010-10518-X

M3 - Article

AN - SCOPUS:79951821326

VL - 139

SP - 1045

EP - 1059

JO - Proceedings of the American Mathematical Society

JF - Proceedings of the American Mathematical Society

SN - 0002-9939

IS - 3

ER -