Nonconstructible blocks in 1D cellular automata: minimal generators and natural systems

The paper concerns minimal nonconstructible blocks of cellular automata, i. e. minimal combinations of cell states that never appear in the evolution o f an automaton. Using our previous work on the construction of predecessors of given configurations, we analyse with numerical experiments the sets of nonconstructible blocks for one-dimensional (1D) cellular automata with bi nary and ternary neighbourhoods and binary cell states, and compare our res ults with the classification made by Voorhees; we also analyse the relation ship of the Voorhees classes to the static parameter lambda. On applying ou r algorithm to cellular-automata models of natural systems, we provide comm on sense interpretations of unreachable states of some biological distribut ed processes. (C) 1999 Elsevier Science Inc. All rights reserved.