A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On the trace subshifts of fractional multiplication automata
Tekijät: Kopra Johan
Kustantaja: ELSEVIER
Julkaisuvuosi: 2021
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 851
Aloitussivu: 92
Lopetussivu: 110
Sivujen määrä: 19
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2020.11.010
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/51286958
Tiivistelmä
We address the dynamics of the cellular automaton (CA) that multiplies by p/q in base pq (for coprime p > q > 1) by studying its trace subshift. We present a conjugacy of the trace to a previously studied base-p/q numeration system. We also show that the trace subshift is not synchronizing and in particular not sofic. As a byproduct we compute its complexity function and we conclude by presenting an example of a sofic shift with the same complexity function.
We address the dynamics of the cellular automaton (CA) that multiplies by p/q in base pq (for coprime p > q > 1) by studying its trace subshift. We present a conjugacy of the trace to a previously studied base-p/q numeration system. We also show that the trace subshift is not synchronizing and in particular not sofic. As a byproduct we compute its complexity function and we conclude by presenting an example of a sofic shift with the same complexity function.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali