Nonemptiness problems of plane square tiling with two colors
Authors:
WenGuei Hu and SongSun Lin
Journal:
Proc. Amer. Math. Soc. 139 (2011), 10451059
MSC (2010):
Primary 37B10, 37B50, 52C20, 37E15, 05B45, 52C23
Published electronically:
August 6, 2010
MathSciNet review:
2745655
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
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 colors are arranged side by side such that adjacent tiles have the same colors. Given a set of Wang tiles , the nonemptiness problem is to determine whether or not , where is the set of all global patterns on that can be constructed from the Wang tiles in . When , the problem is well known to be undecidable. This work proves that when , the problem is decidable. is the set of all periodic patterns on that can be generated by . If , then has a subset of minimal cycle generator such that and for . This study demonstrates that the set of all minimal cycle generators contains elements. is the set of all maximal noncycle generators: if , then and implies . has eight elements. That for any is proven, implying that if , then . The problem is decidable for : 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.
 1.
JungChao
Ban and SongSun
Lin, Patterns generation and transition matrices in
multidimensional lattice models, Discrete Contin. Dyn. Syst.
13 (2005), no. 3, 637–658. MR 2152335
(2006f:37113), 10.3934/dcds.2005.13.637
 2.
J.C. Ban, W.G. Hu, S.S. Lin and Y.H. Lin, Zeta functions for twodimensional shifts of finite type, preprint (2008).
 3.
JungChao
Ban, SongSun
Lin, and YinHeng
Lin, Patterns generation and spatial entropy in twodimensional
lattice models, Asian J. Math. 11 (2007), no. 3,
497–534. MR 2372728
(2010d:37030), 10.4310/AJM.2007.v11.n3.a7
 4.
Robert
Berger, The undecidability of the domino problem, Mem. Amer.
Math. Soc. No. 66 (1966), 72. MR 0216954
(36 #49)
 5.
Karel
Culik II, An aperiodic set of 13 Wang tiles, Discrete Math.
160 (1996), no. 13, 245–251. MR 1417576
(97f:05045), 10.1016/S0012365X(96)001185
 6.
Branko
Grünbaum and G.
C. Shephard, Tilings and patterns, A Series of Books in the
Mathematical Sciences, W. H. Freeman and Company, New York, 1989. An
introduction. MR
992195 (90a:52027)
 7.
Jarkko
Kari, A small aperiodic set of Wang tiles, Discrete Math.
160 (1996), no. 13, 259–264. MR 1417578
(97f:05046), 10.1016/0012365X(95)00120L
 8.
A. Lagae and P. Dutré, An alternative for Wang tiles: Colored edges versus colored corners, ACM Trans. Graphics, 25 (2006), no. 4, 14421459.
 9.
A. Lagae, J. Kari and P. Dutré, Aperiodic sets of square tiles with colored corners, Report CW 460, Department of Computer Science, K.U. Leuven, Leuven, Belgium. Aug 2006.
 10.
R. Penrose, Bull. Inst. Math. Appl. 10 (1974), 266.
 11.
Raphael
M. Robinson, Undecidability and nonperiodicity for tilings of the
plane, Invent. Math. 12 (1971), 177–209. MR 0297572
(45 #6626)
 12.
H. Wang, Proving theorems by pattern recognitionII, Bell System Tech. Journal, 40 (1961), 141.
 1.
 J.C. Ban and S.S. Lin, Patterns generation and transition matrices in multidimensional lattice models, Discrete Contin. Dyn. Syst. 13 (2005), no. 3, 637658. MR 2152335 (2006f:37113)
 2.
 J.C. Ban, W.G. Hu, S.S. Lin and Y.H. Lin, Zeta functions for twodimensional shifts of finite type, preprint (2008).
 3.
 J.C. Ban, S.S. Lin and Y.H. Lin, Patterns generation and spatial entropy in twodimensional lattice models, Asian J. Math. 11 (2007), 497534. MR 2372728 (2010d:37030)
 4.
 R. Berger, The undecidability of the domino problem, Memoirs Amer. Math. Soc., 66 (1966). MR 0216954 (36:49)
 5.
 K. Culik II, An aperiodic set of Wang tiles, Discrete Mathematics, 160 (1996), 245251. MR 1417576 (97f:05045)
 6.
 B. Grünbaum and G. C. Shephard, Tilings and Patterns, New York: W. H. Freeman, 1986. MR 992195 (90a:52027)
 7.
 J. Kari, A small aperiodic set of Wang tiles, Discrete Mathematics, 160 (1996), 259264. MR 1417578 (97f:05046)
 8.
 A. Lagae and P. Dutré, An alternative for Wang tiles: Colored edges versus colored corners, ACM Trans. Graphics, 25 (2006), no. 4, 14421459.
 9.
 A. Lagae, J. Kari and P. Dutré, Aperiodic sets of square tiles with colored corners, Report CW 460, Department of Computer Science, K.U. Leuven, Leuven, Belgium. Aug 2006.
 10.
 R. Penrose, Bull. Inst. Math. Appl. 10 (1974), 266.
 11.
 R.M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Inventiones Mathematicae, 12 (1971), 177209. MR 0297572 (45:6626)
 12.
 H. Wang, Proving theorems by pattern recognitionII, Bell System Tech. Journal, 40 (1961), 141.
Similar Articles
Retrieve articles in Proceedings of the American Mathematical Society
with MSC (2010):
37B10,
37B50,
52C20,
37E15,
05B45,
52C23
Retrieve articles in all journals
with MSC (2010):
37B10,
37B50,
52C20,
37E15,
05B45,
52C23
Additional Information
WenGuei Hu
Affiliation:
Department of Applied Mathematics, National Chiao Tung University, HsinChu 30010, Taiwan
Email:
wwk.am94g@nctu.edu.tw
SongSun Lin
Affiliation:
Department of Applied Mathematics, National Chiao Tung University, HsinChu 30010, Taiwan
Email:
sslin@math.nctu.edu.tw
DOI:
http://dx.doi.org/10.1090/S00029939201010518X
Received by editor(s):
July 15, 2009
Received by editor(s) in revised form:
March 29, 2010
Published electronically:
August 6, 2010
Additional Notes:
The authors would like to thank the National Science Council, R.O.C. (Contract No. NSC 952115M009) and the National Center for Theoretical Sciences for partially supporting this research.
Communicated by:
Yingfei Yi
Article copyright:
© Copyright 2010
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
