A1 Refereed original research article in a scientific journal

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




AuthorsKopra Johan

PublisherWorld Scientific

Publication year2021

JournalInternational Journal of Foundations of Computer Science

Journal name in sourceInternational Journal of Foundations of Computer Science

Volume32

Issue6

First page 663

Last page683

eISSN1793-6373

DOIhttps://doi.org/10.1142/S012905412142003X

Web address https://doi.org/10.1142/S012905412142003X

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/Publication/59148144


Abstract

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.


Downloadable publication

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