NONEMPTINESS PROBLEMS OF PLANE SQUARE TILING WITH TWO COLORS

Abstract

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 Sigma(B) not equal theta, where Sigma(B) is the set of all global patterns on Z(2) that can be constructed from the Wang tiles in B. When p >= 5, the problem is well known to be undecidable. This work proves that when p = 2, the problem is decidable. P(B) is the set of all periodic patterns on Z(2) that can be generated by B. If P(B) not equal empty set, then s has a subset B' of minimal cycle generator such that P(B') not equal empty set and P(B '') = empty set for B '' subset of 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 B is an element of N(2), then P(B) = empty set and (B) over tilde superset of B implies P (B) over tilde) not equal empty set. N(2) has eight elements. That Sigma (B) = theta for any B is an element of N(2) is proven, implying that if Sigma(B) not equal empty set, then P(B) not equal empty set. The problem is decidable for p = 2: Sigma(B) not equal empty set if and only if B has a subset of minimal cycle generators. The approach can be applied to corner coloring with a slight modification, and similar results hold.