A basic property of one-dimensional surjective *cellular automata* (CA) is that any preimage of a *spatially periodic configuration* (SPC) is spatially periodic as well. This paper investigates the relationship between the periods of SPC and the periods of their preimages for various classes of CA. When the CA is only surjective and $y$ is a SPC of least period $p$, the least periods of all preimages of $y$ are multiples of $p$. By leveraging on the *De Bruijn graph representation* of CA, we devise a general algorithm to compute the least periods appearing in the preimages of a SPC, along with their corresponding multiplicities (i.e. how many preimages have a particular least period). Next, we consider the case of *linear* and *bipermutive* cellular automata (LBCA) defined over a *finite field* as state alphabet. In particular, we show an equivalence between preimages of LBCA and concatenated *linear recurring sequences* (LRS) that allows us to give a complete characterization of their periods. Finally, we generalize these results to LBCA defined over a *finite ring* as alphabet.

Type

Publication

Date

September, 2017

**Note**: this publication is an extended version of this conference paper.