標題: NONEMPTINESS PROBLEMS OF PLANE SQUARE TILING WITH TWO COLORS
作者: Hu, Wen-Guei
Lin, Song-Sun
應用數學系
Department of Applied Mathematics
公開日期: 1-三月-2011
摘要: 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.
URI: http://dx.doi.org/10.1090/S0002-9939-2010-10518-X
http://hdl.handle.net/11536/9202
ISSN: 0002-9939
DOI: 10.1090/S0002-9939-2010-10518-X
期刊: PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY
Volume: 139
Issue: 3
起始頁: 1045
結束頁: 1059
顯示於類別:期刊論文


文件中的檔案:

  1. 000288727900027.pdf