TR-96-31: Compositional experimental analysis of cellular automata: attraction properties and logic disjunction

In this paper, we analyze attraction properties of elementary (i.e. Boolean, one-dimensional, bi-infinite) cellular automata (for short, CA). To overcome the well-known undecidability constraints met by these systems, in addition to the classical extensive use of computer simulations, we introduce composition: we first characterize basis CA, which we then use as building blocks to understand a whole family of CA-based systems obtained by composing them using logic disjunction. The compositional approach allows deep structured investigations, and it permits to define a new notion of dynamical complexity.

TR-96-31.pdf