Inducing an order on cellular automata by a grouping operation.

Abstract : A grouped instance of a cellular automaton (CA) is another one obtained by grouping several states into blocks and by letting interact neighbor blocks. Based on this operation (and on the subautomaton notion), a preorder $\leq$ on the set of one dimensional CA is introduced. It is shown that (CA, leq) admits a global minimum and that on the bottom of (CA, leq) very natural equivalence classes are located. These classes remind us the first two well-known Wolfram ones because they capture global (or dynamical) properties as nilpotency or periodicity. Non trivial properties as the undecidability of leq and the existence of bounded infinite chains are also proved. Finally, it is shown that (CA, leq) admits no maximum. This result allows us to conclude that, in a ``grouping sense'', there is no universal CA.
Document type :
Reports
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101944
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:26 AM
Last modification on : Wednesday, November 20, 2019 - 3:13:39 AM

File

RR1997-33.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101944, version 1

Collections

Citation

Jacques Mazoyer, Ivan Rapaport. Inducing an order on cellular automata by a grouping operation.. [Research Report] LIP RR-1997-33, Laboratoire de l'informatique du parallélisme. 1997, 2+16p. ⟨hal-02101944⟩

Share

Metrics

Record views

10

Files downloads

38