In this paper, we investigate the periods of preimages of spatially periodic configurations in linear bipermutive cellular automata (LBCA). We first show that when the CA is only bipermutive and $y$ is a spatially periodic configuration of period $p$, the periods of all preimages of $y$ are multiples of $p$. We then present a connection between preimages of spatially periodic configurations of LBCA and concatenated linear recurring sequences, finding a characteristic polynomial for the latter which depends on the local rule and on the configurations. We finally devise a procedure to compute the period of a single preimage of a spatially periodic configuration $y$ of a given LBCA, and characterise the periods of all preimages of $y$ when the corresponding characteristic polynomial is the product of two distinct irreducible polynomials.

Date

Jun 10, 2015

4:00 PM
— 4:30 PM

Event

Location

Room EDU 1, Department of Mathematics and Statistics, University of Turku, Finland

Links

See the related conference paper