標題: Nonemptiness problems of Wang tiles with three colors
作者: Chen, Hung-Hsun
Hu, Wen-Guei
Lai, De-Jan
Lin, Song-Sun
應用數學系
Department of Applied Mathematics
關鍵字: Nonemptiness;Wang tiles;Decidability;Edge coloring;Periodic patterns;Transition matrix
公開日期: 28-八月-2014
摘要: 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 Sigma(B) not equal empty set , where Sigma(B) is the set of all global patterns on Z(2) that can be constructed from the Wang tiles in B. Wang's conjecture is that for any B of Wang tiles, Sigma (B) not equal empty set if and only if P(B) not equal empty set, where P(B) is the set of all periodic patterns on Z(2) 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) not equal empty set, then B has a subset B' of minimal cycle generators such that P(B') not equal empty set and P(B '') not equal empty set for B '' 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 is an element of N(3), then P(B) not equal empty set and P((B) over tilde) not equal empty set for (B) over tilde B. Wang's conjecture is shown to be true by proving that B is an element of N(3) implies Sigma(B) = empty set. (C) 2014 Elsevier B.V. All rights reserved.
URI: http://dx.doi.org/10.1016/j.tcs.2014.06.015
http://hdl.handle.net/11536/147797
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2014.06.015
期刊: THEORETICAL COMPUTER SCIENCE
Volume: 547
起始頁: 34
結束頁: 45
顯示於類別:期刊論文