Paper Info
Title
On The Periods Of Spatially Periodic Preimages In Linear Bipermutive Cellular Automata
Abstract
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.
Year
DOI
Venue
2015
10.1007/978-3-662-47221-7_14
CELLULAR AUTOMATA AND DISCRETE COMPLEX SYSTEMS, AUTOMATA 2015
Keywords
Field
DocType
Linear bipermutive cellular automata, Spatially periodic configurations, Preimages, Surjectivity, Linear recurring sequences, Linear feedback shift registers
Characteristic polynomial,Cellular automaton,Discrete mathematics,Polynomial,Concatenation,Image (mathematics),Periodic graph (geometry),Mathematics
Conference
Volume
ISSN
Citations 
9099
0302-9743
3
PageRank 
References 
Authors
0.51
7
2
Name
Order
Citations
PageRank
Luca Mariot14711.35
Alberto Leporati249451.97