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.

Mariot, L., Leporati, A. (2015). On the periods of spatially periodic preimages in linear bipermutive cellular automata. Intervento presentato a: IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA) June 8-10, Turku, Finland [10.1007/978-3-662-47221-7_14].

On the periods of spatially periodic preimages in linear bipermutive cellular automata

MARIOT, LUCA
Primo
;
LEPORATI, ALBERTO OTTAVIO
2015

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.
paper
Linear bipermutive cellular automata; Linear feedback shift registers; Linear recurring sequences; Preimages; Spatially periodic configurations; Surjectivity; Computer Science (all); Theoretical Computer Science
English
IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA) June 8-10
2015
Cellular Automata and Discrete Complex Systems - 21st IFIP WG 1.5 International Workshop, AUTOMATA 2015 (Turku, Finland, June 8-10, 2015). Proceedings
Kari, J
9783662472200
2015
9099
181
195
http://springerlink.com/content/0302-9743/copyright/2005/
none
Mariot, L., Leporati, A. (2015). On the periods of spatially periodic preimages in linear bipermutive cellular automata. Intervento presentato a: IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA) June 8-10, Turku, Finland [10.1007/978-3-662-47221-7_14].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/90037
Citazioni
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
Social impact