TY - JOUR

T1 - Nonemptiness problems of Wang tiles with three colors

AU - Chen, Hung Hsun

AU - Hu, Wen Guei

AU - Lai, De Jan

AU - Lin, Song-Sun

PY - 2014/1/1

Y1 - 2014/1/1

N2 - This investigation studies nonemptiness problems of plane edge coloring with three colors. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges that have one of p colors are arranged side by side such that the touching edges of the adjacent tiles have the same colors. Given a basic set B of Wang tiles, the nonemptiness problem is to determine whether or not σ(B)≠ θ, where σ(B) is the set of all global patterns on Z2 that can be constructed from the Wang tiles in B. Wang's conjecture is that for any B of Wang tiles, σ(B)≠ θ if and only if P(B)≠θ, where P(B) is the set of all periodic patterns on Z2 that can be generated by the tiles in B. When p≥5, Wang's conjecture is known to be wrong. When p=2, the conjecture is true. This study proves that when p = 3, the conjecture is also true. If P(B)≠θ, then B has a subset B′ of minimal cycle generators such that P(B′)≠θ and P(B″)=θ for B″{subset not double equals}B′. This study demonstrates that the set C(3) of all minimal cycle generators contains 787, 605 members that can be classified into 2, 906 equivalence classes. N(3) is the set of all maximal non-cycle generators: if B∈N(3), then P(B)=θ and P(B~)≠θ for B~{superset not double equals}B. Wang's conjecture is shown to be true by proving that B∈N(3) implies σ(B)=θ.

AB - This investigation studies nonemptiness problems of plane edge coloring with three colors. In the edge coloring (or Wang tiles) of a plane, unit squares with colored edges that have one of p colors are arranged side by side such that the touching edges of the adjacent tiles have the same colors. Given a basic set B of Wang tiles, the nonemptiness problem is to determine whether or not σ(B)≠ θ, where σ(B) is the set of all global patterns on Z2 that can be constructed from the Wang tiles in B. Wang's conjecture is that for any B of Wang tiles, σ(B)≠ θ if and only if P(B)≠θ, where P(B) is the set of all periodic patterns on Z2 that can be generated by the tiles in B. When p≥5, Wang's conjecture is known to be wrong. When p=2, the conjecture is true. This study proves that when p = 3, the conjecture is also true. If P(B)≠θ, then B has a subset B′ of minimal cycle generators such that P(B′)≠θ and P(B″)=θ for B″{subset not double equals}B′. This study demonstrates that the set C(3) of all minimal cycle generators contains 787, 605 members that can be classified into 2, 906 equivalence classes. N(3) is the set of all maximal non-cycle generators: if B∈N(3), then P(B)=θ and P(B~)≠θ for B~{superset not double equals}B. Wang's conjecture is shown to be true by proving that B∈N(3) implies σ(B)=θ.

KW - Decidability

KW - Edge coloring

KW - Nonemptiness

KW - Periodic patterns

KW - Transition matrix

KW - Wang tiles

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

U2 - 10.1016/j.tcs.2014.06.015

DO - 10.1016/j.tcs.2014.06.015

M3 - Article

AN - SCOPUS:84926420042

VL - 547

SP - 34

EP - 45

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - C

ER -