2015/05/11 by Ethan M. Coven, Coven, Ethan M., Anthony Quas +3
Computer Science · #semigroups and automata theory #Coding theory and cryptography #Cellular Automata and Applications
paper · pdf · doi:10.48550/arxiv.1505.02482
We study the automorphism group of an infinite minimal shift (X,\σ)\nsuch that the complexity difference function, p(n+1)-p(n), is bounded. We\ngive some new bounds on \Aut(X,\σ)/\⟨ \σ \⟩ and also\nstudy the one-sided case. For a class of Toeplitz shifts, including the class\nof shifts defined by constant length primitive substitutions with a coincidence\nand with height one, we show that the two-sided automorphism group is a cyclic\ngroup. We next focus on shifts generated by primitive constant length\nsubstitutions. For these shifts, we give an algorithm that computes their\ntwo-sided automorphism group, As a corollary we describe how to compute the set\nof conjugacies between two such shifts.\n