Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

The decomposition theorem
for two-dimensional shifts of finite type


Authors: Aimee S. A. Johnson and Kathleen M. Madden
Journal: Proc. Amer. Math. Soc. 127 (1999), 1533-1543
MSC (1991): Primary 58F03
DOI: https://doi.org/10.1090/S0002-9939-99-04678-X
Published electronically: January 29, 1999
MathSciNet review: 1476140
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: A one-dimensional shift of finite type can be described as the collection of bi-infinite ``walks" along an edge graph. The Decomposition Theorem states that every conjugacy between two shifts of finite type can be broken down into a finite sequence of splittings and amalgamations of their edge graphs. When dealing with two-dimensional shifts of finite type, the appropriate edge graph description is not as clear; we turn to Nasu's notion of a ``textile system" for such a description and show that all two-dimensional shifts of finite type can be so described. We then define textile splittings and amalgamations and prove that every conjugacy between two-dimensional shifts of finite type can be broken down into a finite sequence of textile splittings, textile amalgamations, and a third operation called an inversion.


References [Enhancements On Off] (What's this?)

  • [A97] Aso, H., Conjugacy between $Z^{2}$-subshifts and Textiles Systems, preprint.
  • [B66] Berger, R., The Undecidability of the Domino Problem, Mem. AMS 66, 1966. MR 36:49
  • [KS88] Kitchens, B. and Schmidt, K., Periodic Points, Decidability, and Markov Subgroups, Proceedings of the special year (ed. J. C. Alexander), Springer Lecture Notes in Math. 1342, (1988), 440-454. MR 89m:28027
  • [KS92] Kitchens, B. and Schmidt, K., Markov Subgroups of $(Z/2Z)^{Z^2}$, Symbolic Dynamics and Its Applications, Contemporary Math. 135 (ed P. Walters), (1992), 265-283. MR 93k:58136
  • [LM95] Lind, D. and Marcus, B., An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, 1995. MR 97a:58050
  • [MP81] Markley, N. G. and Paul, M., Matrix Subshifts for $Z^{\nu}$ Symbolic Dynamics, Proc. London Math. Soc. 43 (1981), 251-272. MR 82i:54073
  • [MP281] Markley, N. G. and Paul, M., Maximal Measures and Entropy for $Z^{\nu}$ Subshifts of Finite Type, Classical Mechanics and Dynamical Systems (ed. R. Devaney and Z. Nitecki), Dekkar Notes 70, 135-157. MR 83c:54059
  • [M89] Mozes, S., Tilings, substitution systems and the dynamical systems generated by them, J. Anal. Math. 53 (1989), 139-186. MR 91h:58038
  • [N86] Nasu, M., Topological Conjugacy for Sofic Systems, Ergod. Th. and Dynam. Sys. 6 (1986), 265-280. MR 88f:28018
  • [N95] Nasu, M., Textile Systems for Endomorphisms and Automorphisms of the Shift, Memoirs of the AMS 546, Vol. 114, 1995. MR 95i:54051
  • [R71] Robinson, R., Undecidability and Nonperiodicity of Tilings of the Plane, Inventiones Math., Vol. 12, (1971), 177-209. MR 45:6626
  • [W73] Williams, R. F., Classifications of Shifts of Finite Type, Annals of Math. 98 (1973), 120-153. Errata, Annals of Math. 99, (1974), 380-381. MR 48:9769

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (1991): 58F03

Retrieve articles in all journals with MSC (1991): 58F03


Additional Information

Aimee S. A. Johnson
Affiliation: Department of Mathematics and Statistics, Swarthmore College, Swarthmore, Pennsylvania 19081
Email: aimee@swarthmore.edu

Kathleen M. Madden
Affiliation: Department of Mathematics and Computer Science, Drew University, Madison, New Jersey 07940
Email: kmadden@drew.edu

DOI: https://doi.org/10.1090/S0002-9939-99-04678-X
Keywords: Decomposition Theorem, two-dimensional shifts of finite type, textile systems
Received by editor(s): June 24, 1997
Received by editor(s) in revised form: September 2, 1997
Published electronically: January 29, 1999
Communicated by: Mary Rees
Article copyright: © Copyright 1999 American Mathematical Society

American Mathematical Society