Regional Controllability of Cellular Automata Through Preimages

We investigate a regional controllability problem applied to elementary Cellular Automata (CA). We first examine the conditions for boundary control, showing that, at least for small lattice sizes, only peripherally linear or affine CA can be fully controllable. Exploiting linearity, it is possible to develop an algorithm to construct the tree of preimages of a given configuration, therefore explicitly finding the optimal control for any given configuration. We apply then this method to non-linear CA.