A1 Journal article – refereed

On the trace subshifts of fractional multiplication automata




List of Authors: Kopra Johan

Publisher: ELSEVIER

Publication year: 2021

Journal: Theoretical Computer Science

Journal name in source: THEORETICAL COMPUTER SCIENCE

Journal acronym: THEOR COMPUT SCI

Volume number: 851

Number of pages: 19

ISSN: 0304-3975

eISSN: 1879-2294

DOI: http://dx.doi.org/10.1016/j.tcs.2020.11.010


Abstract
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.


Last updated on 2021-24-06 at 09:10