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

Published electronically:
January 29, 1999

MathSciNet review:
1476140

Full-text PDF Free Access

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.

**[A97]**Aso, H.,*Conjugacy between -subshifts and Textiles Systems*, preprint.**[B66]**Robert Berger,*The undecidability of the domino problem*, Mem. Amer. Math. Soc. No.**66**(1966), 72. MR**0216954****[KS88]**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**, 10.1007/BFb0082845**[KS92]**Bruce Kitchens and Klaus Schmidt,*Markov subgroups of (𝑍/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**, 10.1090/conm/135/1185094**[LM95]**Douglas Lind and Brian Marcus,*An introduction to symbolic dynamics and coding*, Cambridge University Press, Cambridge, 1995. MR**1369092****[MP81]**Nelson G. Markley and Michael E. Paul,*Matrix subshifts for 𝑍^{𝜈} symbolic dynamics*, Proc. London Math. Soc. (3)**43**(1981), no. 2, 251–272. MR**628277**, 10.1112/plms/s3-43.2.251**[MP281]**Nelson G. Markley and Michael E. Paul,*Maximal measures and entropy for 𝑍^{𝜈} 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****[M89]**Shahar Mozes,*Tilings, substitution systems and dynamical systems generated by them*, J. Analyse Math.**53**(1989), 139–186. MR**1014984**, 10.1007/BF02793412**[N86]**Masakazu Nasu,*Topological conjugacy for sofic systems*, Ergodic Theory Dynam. Systems**6**(1986), no. 2, 265–280. MR**857201**, 10.1017/S0143385700003448**[N95]**Masakazu Nasu,*Textile systems for endomorphisms and automorphisms of the shift*, Mem. Amer. Math. Soc.**114**(1995), no. 546, viii+215. MR**1234883**, 10.1090/memo/0546**[R71]**Raphael M. Robinson,*Undecidability and nonperiodicity for tilings of the plane*, Invent. Math.**12**(1971), 177–209. MR**0297572****[W73]**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**0331436**

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