A1 Refereed original research article in a scientific journal
Glider automata on all transitive sofic shifts
Authors: Kopra Johan
Publisher: Cambridge University Press
Publication year: 2022
Journal: Ergodic Theory and Dynamical Systems
Journal name in source: Ergodic Theory and Dynamical Systems
Volume: 42
Issue: 12
First page : 3716
Last page: 3744
eISSN: 1469-4417
DOI: https://doi.org/10.1017/etds.2021.107
Web address : https://doi.org/10.1017/etds.2021.107
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/67745009
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.
Downloadable publication This is an electronic reprint of the original article. |