The decomposition theorem for two-dimensional shifts of finite type
HTML articles powered by AMS MathViewer
- by Aimee S. A. Johnson and Kathleen M. Madden PDF
- Proc. Amer. Math. Soc. 127 (1999), 1533-1543 Request permission
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
- Aso, H., Conjugacy between $Z^{2}$-subshifts and Textiles Systems, preprint.
- Robert Berger, The undecidability of the domino problem, Mem. Amer. Math. Soc. 66 (1966), 72. MR 216954
- Bruce Kitchens and Klaus Schmidt, Periodic points, decidability and Markov subgroups, Dynamical systems (College Park, MD, 1986β87) Lecture Notes in Math., vol. 1342, Springer, Berlin, 1988, pp.Β 440β454. MR 970569, DOI 10.1007/BFb0082845
- Bruce Kitchens and Klaus Schmidt, Markov subgroups of $(\textbf {Z}/2\textbf {Z})^{\textbf {Z}^2}$, Symbolic dynamics and its applications (New Haven, CT, 1991) Contemp. Math., vol. 135, Amer. Math. Soc., Providence, RI, 1992, pp.Β 265β283. MR 1185094, DOI 10.1090/conm/135/1185094
- Douglas Lind and Brian Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press, Cambridge, 1995. MR 1369092, DOI 10.1017/CBO9780511626302
- Nelson G. Markley and Michael E. Paul, Matrix subshifts for $\textbf {Z}^{\nu }$ symbolic dynamics, Proc. London Math. Soc. (3) 43 (1981), no.Β 2, 251β272. MR 628277, DOI 10.1112/plms/s3-43.2.251
- Nelson G. Markley and Michael E. Paul, Maximal measures and entropy for $\textbf {Z}^{\nu }$ subshifts of finite type, Classical mechanics and dynamical systems (Medford, Mass., 1979) Lecture Notes in Pure and Appl. Math., vol. 70, Dekker, New York, 1981, pp.Β 135β157. MR 640123
- Shahar Mozes, Tilings, substitution systems and dynamical systems generated by them, J. Analyse Math. 53 (1989), 139β186. MR 1014984, DOI 10.1007/BF02793412
- Masakazu Nasu, Topological conjugacy for sofic systems, Ergodic Theory Dynam. Systems 6 (1986), no.Β 2, 265β280. MR 857201, DOI 10.1017/S0143385700003448
- Masakazu Nasu, Textile systems for endomorphisms and automorphisms of the shift, Mem. Amer. Math. Soc. 114 (1995), no.Β 546, viii+215. MR 1234883, DOI 10.1090/memo/0546
- Raphael M. Robinson, Undecidability and nonperiodicity for tilings of the plane, Invent. Math. 12 (1971), 177β209. MR 297572, DOI 10.1007/BF01418780
- R. F. Williams, Classification of subshifts of finite type, Ann. of Math. (2) 98 (1973), 120β153; errata, ibid. (2) 99 (1974), 380β381. MR 331436, DOI 10.2307/1970908
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
- MR Author ID: 350229
- Email: kmadden@drew.edu
- 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
- © Copyright 1999 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 127 (1999), 1533-1543
- MSC (1991): Primary 58F03
- DOI: https://doi.org/10.1090/S0002-9939-99-04678-X
- MathSciNet review: 1476140