Glider automata on all transitive sofic shifts
Kopra Johan
Glider automata on all transitive sofic shifts
Kopra Johan
Cambridge University Press
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2021120158429
https://urn.fi/URN:NBN:fi-fe2021120158429
Tiivistelmä
For any infinite transitive sofic shift X we construct a reversible cellular automaton (that is, an automorphism of the shift X) which breaks any given finite point of the subshift into a finite collection of gliders traveling into opposing directions. This shows in addition that every infinite transitive sofic shift has a reversible cellular automaton which is sensitive with respect to all directions. As another application we prove a finitary version of Ryan’s theorem: the automorphism group Aut(X) contains a two-element subset whose centralizer consists only of shift maps. We also show that in the class of S-gap shifts these results do not extend beyond the sofic case.
Kokoelmat
- Rinnakkaistallenteet [19207]