Name
Abstract | ||
|---|---|---|
A basic property of one-dimensional surjective (CA) is that any preimage of a (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 is a SPC of least period , the least periods of all preimages of are multiples of . By leveraging on the 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 and cellular automata (LBCA) defined over a as state alphabet. In particular, we show an equivalence between preimages of LBCA and concatenated (LRS) that allows us to give a complete characterization of their periods. Finally, we generalize these results to LBCA defined over a as alphabet. |
Year | DOI | Venue |
|---|---|---|
2017 | https://doi.org/10.1007/s11047-016-9586-x | Natural Computing |
Keywords | Field | DocType |
Cellular automata,Surjectivity,De Bruijn graph,Bipermutivity,Linear recurring sequences,Linear feedback shift registers,37B15,68Q80,94A55 | Finite ring,Cellular automaton,Discrete mathematics,Combinatorics,Finite field,Equivalence (measure theory),De Bruijn graph,Image (mathematics),Periodic graph (geometry),Mathematics,Surjective function | Journal |
Volume | Issue | ISSN |
16 | 3 | 1567-7818 |
Citations | PageRank | References |
1 | 0.36 | 8 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Luca Mariot | 1 | 47 | 11.35 |
| Alberto Leporati | 2 | 494 | 51.97 |
| alberto dennunzio | 3 | 318 | 38.17 |
| Enrico Formenti | 4 | 23 | 6.47 |