Abstract | ||
---|---|---|
We consider the family of all the Cellular Automata (CA) sharing the same local rule but having different memories. This family contains also all CA with memory m@?0 (one-sided CA) which can act both on A^Z and on A^N. We study several set theoretical and topological properties for these classes. In particular, we investigate whether the properties of a given CA are preserved when considering the CA obtained by changing the memory of the original one (shifting operation). Furthermore, we focus our attention on the one-sided CA acting on A^Z, starting from the one-sided CA acting on A^N and having the same local rule (lifting operation). As a particular consequence of these investigations, we prove that the long-standing conjecture [Surjectivity @? Dense Periodic Orbits (DPO)] can be restated in several different (but equivalent) ways. Furthermore, we give some results on properties conserved under the iteration of the CA global map. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.tcs.2009.05.004 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
Cellular automata,Symbolic dynamics,memory m,CA global map,Cellular Automata,local rule,topological property,dynamical property,cellular automaton,Dense Periodic Orbits,different memory,particular consequence,long-standing conjecture,one-sided CA | Journal | 410 |
Issue | ISSN | Citations |
38-40 | Theoretical Computer Science | 25 |
PageRank | References | Authors |
1.26 | 15 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Luigi Acerbi | 1 | 43 | 2.95 |
alberto dennunzio | 2 | 318 | 38.17 |
Enrico Formenti | 3 | 400 | 45.55 |