2012/10/25 by Hung‐Hsun Chen, Chen, Hung-Hsun, Wen-Guei Hu +5
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1210.6712
openalex publication_date 2012/10/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This investigation studies the decidability problem of plane edge coloring with three symbols. 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 decision problem is to find an algorithm to determine whether or not Σ(B)≠∅, where Σ(B) is the set of all global patterns on ℤ2 that can be constructed from the Wang tiles in B. When p≥ 5, the problem is known to be undecidable. When p=2, the problem is decidable. This study proves that when p=3, the problem is also decidable. P(B) is the set of all periodic patterns on ℤ2 that can be generated by the tiles in B. If P(B)≠∅, then B has a subset B' of minimal cycle generators such that P(B')≠∅ and P(B")=∅ for B"\subsetneqq 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\supsetneqq B. The problem is shown to be decidable by proving that B∈ N(3) implies Σ(B)=∅. Consequently, Σ(B)≠∅ if and only if P(B)≠∅.