Computing automorphism groups of shifts using atypical equivalence classes

Abstract

We study the automorphism group of an infinite minimal shift \((X,\sigma)\) such that the complexity difference function, \(p(n+1)-p(n)\), is bounded. We give some new bounds on \(\mbox{Aut}(X,\sigma)/\langle \sigma \rangle\) and also study the one-sided case. For a class of Toeplitz shifts, including the class of shifts defined by constant length primitive substitutions with a coincidence and with height one, we show that the two-sided automorphism group is a cyclic group. We next focus on shifts generated by primitive constant length substitutions. For these shifts, we give an algorithm that computes their two-sided automorphism group, As a corollary we describe how to compute the set of conjugacies between two such shifts.