Nonemptiness problems of plane square tiling with two colors

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 $\mathcal{B}$, the nonemptiness problem is to determine whether or not $\Sigma(\mathcal{B})\neq\emptyset$, where $\Sigma(\mathcal{B})$ is the set of all global patterns on $\mathbb{Z}^{2}$ that can be constructed from the Wang tiles in $\mathcal{B}$.

When $p\geq 5$, the problem is well known to be undecidable. This work proves that when $p=2$, the problem is decidable. $\mathcal{P}(\mathcal{B})$ is the set of all periodic patterns on $\mathbb{Z}^{2}$ that can be generated by $\mathcal{B}$. If $\mathcal{P}(\mathcal{B})\neq\emptyset$, then $\mathcal{B}$ has a subset $\mathcal{B}'$ of minimal cycle generator such that $\mathcal{P}(\mathcal{B}')\neq\emptyset$ and $\mathcal{P}(\mathcal{B}'')=\emptyset$ for $\mathcal{B}''\subsetneqq \mathcal{B}'$. This study demonstrates that the set of all minimal cycle generators $\mathcal{C}(2)$ contains $38$ elements. $\mathcal{N}(2)$ is the set of all maximal noncycle generators: if $\mathcal{B}\in\mathcal{N}(2)$, then $\mathcal{P}(\mathcal{B})=\emptyset$ and $\widetilde{\mathcal{B}}\supsetneqq \mathcal{B}$ implies $\mathcal{P}(\widetilde{\mathcal{B}})\neq\emptyset$. $\mathcal{N}(2)$ has eight elements. That $\Sigma(\mathcal{B})=\emptyset$ for any $\mathcal{B}\in\mathcal{N}(2)$ is proven, implying that if $\Sigma(\mathcal{B})\neq\emptyset$, then $\mathcal{P}(\mathcal{B})\neq\emptyset$. The problem is decidable for $p=2$: $\Sigma(\mathcal{B})\neq\emptyset$ if and only if $\mathcal{B}$ has a subset of minimal cycle generators. The approach can be applied to corner coloring with a slight modification, and similar results hold.