Proceedings of the American Mathematical Society

Author(s): Aimee S. A. Johnson; Kathleen M. Madden
Journal: Proc. Amer. Math. Soc. 127 (1999), 1533-1543.
MSC (1991): Primary 58F03
Posted: January 29, 1999
Retrieve article in: PDF
This article is available free of charge

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 $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

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

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

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6826 (e) ISSN 0002-9939 (p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS