Nonemptiness problems of plane square tiling with two colors

Authors:
Wen-Guei Hu and Song-Sun Lin

Journal:
Proc. Amer. Math. Soc. **139** (2011), 1045-1059

MSC (2010):
Primary 37B10, 37B50, 52C20, 37E15, 05B45, 52C23

Published electronically:
August 6, 2010

MathSciNet review:
2745655

Full-text 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.**Jung-Chao Ban and Song-Sun Lin,*Patterns generation and transition matrices in multi-dimensional lattice models*, Discrete Contin. Dyn. Syst.**13**(2005), no. 3, 637–658. MR**2152335**, 10.3934/dcds.2005.13.637**2.**J.C. Ban, W.G. Hu, S.S. Lin and Y.H. Lin,*Zeta functions for two-dimensional shifts of finite type*, preprint (2008).**3.**Jung-Chao Ban, Song-Sun Lin, and Yin-Heng Lin,*Patterns generation and spatial entropy in two-dimensional lattice models*, Asian J. Math.**11**(2007), no. 3, 497–534. MR**2372728**, 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****5.**Karel Culik II,*An aperiodic set of 13 Wang tiles*, Discrete Math.**160**(1996), no. 1-3, 245–251. MR**1417576**, 10.1016/S0012-365X(96)00118-5**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****7.**Jarkko Kari,*A small aperiodic set of Wang tiles*, Discrete Math.**160**(1996), no. 1-3, 259–264. MR**1417578**, 10.1016/0012-365X(95)00120-L**8.**A. Lagae and P. Dutré,*An alternative for Wang tiles: Colored edges versus colored corners*, ACM Trans. Graphics,**25**(2006), no. 4, 1442-1459.**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****12.**H. Wang,*Proving theorems by pattern recognition-II*, Bell System Tech. Journal,**40**(1961), 1-41.

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

**Wen-Guei Hu**

Affiliation:
Department of Applied Mathematics, National Chiao Tung University, Hsin-Chu 30010, Taiwan

Email:
wwk.am94g@nctu.edu.tw

**Song-Sun Lin**

Affiliation:
Department of Applied Mathematics, National Chiao Tung University, Hsin-Chu 30010, Taiwan

Email:
sslin@math.nctu.edu.tw

DOI:
http://dx.doi.org/10.1090/S0002-9939-2010-10518-X

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 95-2115-M-009) 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.