%0 Conference Proceedings
%T On the Periods of Spatially Periodic Preimages in Linear Bipermutive Cellular Automata
%+ Dipartimento di Informatica Sistemistica e Comunicazione (DISCo)
%+ Laboratoire d'Informatique, Signaux, et Systèmes de Sophia-Antipolis (I3S) / Equipe MC3
%A Mariot, Luca
%A Leporati, Alberto
%Z Part 2: Regular Papers
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 21st Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Turku, Finland
%Y Jarkko Kari
%I Springer
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-9099
%P 181-195
%8 2015-06-08
%D 2015
%R 10.1007/978-3-662-47221-7_14
%K Linear bipermutive cellular automata
%K Spatially periodic configurations
%K Preimages
%K Surjectivity
%K Linear recurring sequences
%K Linear feedback shift registers
%Z Computer Science [cs]/Discrete Mathematics [cs.DM]
%Z Computer Science [cs]/Computational Complexity [cs.CC]
%Z Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.5
%2 https://hal.science/hal-01313895/document
%2 https://hal.science/hal-01313895/file/338243_1_En_14_Chapter.pdf
%L hal-01313895
%U https://hal.science/hal-01313895
%~ UNICE
%~ CNRS
%~ I3S
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ TDS-MACS
%~ IFIP-LNCS-9099
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA
%~ UNIV-COTEDAZUR