### 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 ∑(ß) ≠ Φ, 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 language | English |
---|---|

Pages (from-to) | 1045-1059 |

Number of pages | 15 |

Journal | Proceedings of the American Mathematical Society |

Volume | 139 |

Issue number | 3 |

DOIs | |

State | Published - 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

*Proceedings of the American Mathematical Society*,

*139*(3), 1045-1059. https://doi.org/10.1090/S0002-9939-2010-10518-X