A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

On the Interplay of Direct Topological Factorizations and Cellular Automata Dynamics on Beta-Shifts




TekijätKopra Johan

KustantajaWorld Scientific

Julkaisuvuosi2021

JournalInternational Journal of Foundations of Computer Science

Tietokannassa oleva lehden nimiInternational Journal of Foundations of Computer Science

Vuosikerta32

Numero6

Aloitussivu663

Lopetussivu683

eISSN1793-6373

DOIhttps://doi.org/10.1142/S012905412142003X

Verkko-osoitehttps://doi.org/10.1142/S012905412142003X

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/Publication/59148144


Tiivistelmä

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 S 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.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 12:18