A1 Refereed original research article in a scientific journal
On the Interplay of Direct Topological Factorizations and Cellular Automata Dynamics on Beta-Shifts
Authors: Kopra Johan
Publisher: World Scientific
Publication year: 2021
Journal: International Journal of Foundations of Computer Science
Journal name in source: International Journal of Foundations of Computer Science
Volume: 32
Issue: 6
First page : 663
Last page: 683
eISSN: 1793-6373
DOI: https://doi.org/10.1142/S012905412142003X
Web address : https://doi.org/10.1142/S012905412142003X
Self-archived copy’s web address: 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.
Downloadable publication This is an electronic reprint of the original article. |