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.