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

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

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.**J.C. Ban and S.S. Lin,*Patterns generation and transition matrices in multi-dimensional lattice models*, Discrete Contin. Dyn. Syst.**13**(2005), no. 3, 637-658. MR**2152335 (2006f:37113)****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.**J.C. Ban, S.S. Lin and Y.H. Lin,*Patterns generation and spatial entropy in two-dimensional lattice models*, Asian J. Math.**11**(2007), 497-534. 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), 245-251. 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), 259-264. 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, 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.**R.M. Robinson,*Undecidability and nonperiodicity for tilings of the plane*, Inventiones Mathematicae,**12**(1971), 177-209. MR**0297572 (45:6626)****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:
https://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.