A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On the Interplay of Direct Topological Factorizations and Cellular Automata Dynamics on Beta-Shifts
Tekijät: Kopra Johan
Kustantaja: World Scientific
Julkaisuvuosi: 2021
Journal: International Journal of Foundations of Computer Science
Tietokannassa oleva lehden nimi: International Journal of Foundations of Computer Science
Vuosikerta: 32
Numero: 6
Aloitussivu: 663
Lopetussivu: 683
eISSN: 1793-6373
DOI: https://doi.org/10.1142/S012905412142003X
Verkko-osoite: https://doi.org/10.1142/S012905412142003X
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/Publication/59148144
We consider the range of possible dynamics of cellular automata (CA) on two-sided beta-shifts Sβ and its relation to direct topological factorizations. We show that any reversible CA F:Sβ→Sβ has an almost equicontinuous direction whenever Sβ is not sofic. This has the corollary that non-sofic beta-shifts are topologically direct prime, i.e. they are not conjugate to direct topological factorizations X×Y of two nontrivial subshifts X and Y. We also give a simple criterion to determine whether Snγ is conjugate to Sn×Sγ for a given integer n≥1 and a given real γ>1 when Sγ is a subshift of finite type. When Sγ is strictly sofic, we show that such a conjugacy is not possible at least when γ is a quadratic Pisot number of degree 2. We conclude by using direct factorizations to give a new proof for the classification of reversible multiplication automata on beta-shifts with integral base and ask whether nontrivial multiplication automata exist when the base is not an integer.
Ladattava julkaisu This is an electronic reprint of the original article. |