Williams’s conjecture is false for reducible subshifts

Kim, K. H.; Roush, F. W.

doi:10.1090/S0894-0347-1992-1130528-4

Williams's conjecture is false for reducible subshifts

Authors: K. H. Kim and F. W. Roush
Journal: J. Amer. Math. Soc. 5 (1992), 213-215
MSC: Primary 54H20; Secondary 15A36, 28D20
DOI: https://doi.org/10.1090/S0894-0347-1992-1130528-4
MathSciNet review: 1130528
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We show that for two subshifts of finite type having exactly two irreducible components, strong shift equivalence is not the same as shift equivalence. This refutes the Williams conjecture $[{\text{W}}]$ in the reducible case. The irreducible case remains an open problem.

[ACH] Roy L. Adler, Don Coppersmith, and Martin Hassner, Algorithms for sliding block codes. An application of symbolic dynamics to information theory, IEEE Trans. Inform. Theory 29 (1983), no. 1, 5–22. MR 711274, https://doi.org/10.1109/TIT.1983.1056597
[Ba] Kirby A. Baker, Strong shift equivalence of 2×2 matrices of nonnegative integers, Ergodic Theory Dynam. Systems 3 (1983), no. 4, 501–508. MR 753918, https://doi.org/10.1017/S0143385700002091
[Bow] Rufus Bowen, Markov partitions for Axiom 𝐴 diffeomorphisms, Amer. J. Math. 92 (1970), 725–747. MR 277003, https://doi.org/10.2307/2373370
[KR] K. H. Kim and F. W. Roush, Some results on decidability of shift equivalence, J. Combin. Inform. System Sci. 4 (1979), no. 2, 123–146. MR 564188
[KRW] K. H. Kim, F. W. Roush, and J. B. Wagoner, Automorphisms of the dimension group and gyration numbers, J. Amer. Math. Soc. 5 (1992), no. 1, 191–212. MR 1124983, https://doi.org/10.1090/S0894-0347-1992-1124983-3
[N] Masakazu Nasu, Topological conjugacy for sofic systems and extensions of automorphisms of finite subsystems of topological Markov shifts, Dynamical systems (College Park, MD, 1986–87) Lecture Notes in Math., vol. 1342, Springer, Berlin, 1988, pp. 564–607. MR 970572, https://doi.org/10.1007/BFb0082848
[W] 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, https://doi.org/10.2307/1970908