Automorphisms of shift spaces and the Higman - Thompson groups: the one-sided case

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)


Let 1 ≤ r < n be integers. We give a proof that the group Aut(Xnn) of automorphisms of the one-sided shift on n letters embeds naturally as a subgroup ℋn of the outer automorphism group Out(Gn,r) of the Higman-Thompson group Gn,r. From this, we can represent the elements of Aut(Xnn) by finite state non-initial transducers admitting a very strong synchronizing condition.

Let H ∈ ℋn and write |H| for the number of states of the minimal transducer representing H. We show that H can be written as a product of at most |H| torsion elements. This result strengthens a similar result of Boyle, Franks and Kitchens, where the decomposition involves more complex torsion elements and also does not support practical a priori estimates of the length of the resulting product.

We also explore the number of foldings of de Bruijn graphs and give acounting result for these for word length 2 and alphabet size n.

Finally, we offer new proofs of some known results about Aut(Xnn).
Original languageEnglish
Article number15
Number of pages35
JournalDiscrete Analysis
Publication statusPublished - 20 Sept 2021


  • Higman--Thompson groups
  • automorphisms of the shift
  • Transducers


Dive into the research topics of 'Automorphisms of shift spaces and the Higman - Thompson groups: the one-sided case'. Together they form a unique fingerprint.

Cite this