2015/05/11 by Ethan M. Coven, Coven, Ethan M., Anthony Quas +3
Computer Science · Mathematics · #Cellular Automata and Applications #Coding theory and cryptography #math.DS #msc:37B05 #msc:37B10 #msc:37B15 #msc:54H20 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1505.02482
This new version of the article has been reformatted for Discrete Analysis but is otherwise identical to the previous version
arxiv created 2017/02/01 · arxiv updated 2017/02/02
We study the automorphism group of an infinite minimal shift (X,σ) such that the complexity difference function, p(n+1)-p(n), is bounded. We give some new bounds on Aut(X,σ)/⟨ σ⟩ 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.