Skip to Main content Skip to Navigation

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 :
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:26 AM
Last modification on : Wednesday, November 20, 2019 - 3:13:39 AM


Files produced by the author(s)


  • HAL Id : hal-02101944, version 1



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⟩



Record views


Files downloads