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.

**[A97]**Aso, H.,*Conjugacy between -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*, 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 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 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**

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