Recent advances in regional controllability of cellular automata

The issue addressed in this thesis concerns the controllability of a class of dis- crete spatio-temporal systems named cellular automata (CA). The purpose of this study is to highlight new ways to prove the controllability of complex systems. More specifically, this thesis focuses on regional controllability which consists in restricting the study to a subregion of the domain where the system will have to achieve a given objective through targeted actions. The case of Boolean CA have been particularly examined throughout this thesis. The first part is devoted to the study of the prob- lem of the regional controllability of deterministic CAs when the actions are exerted on the boundaries of the controlled region. A first approach that we used relies on Markov chains and controllability is characterized by establishing a matrix similar to their transition matrix using the definitions of a regular and ergodic chain. This study has been extended to the case of probabilistic CAs that are widely used to model many real phenomena. The same problem has been apprehended using tools of graph theory. We propose necessary and sufficient conditions for the regional controllability of deterministic CAs using the notions of Hamiltonian circuit and strongly connected component. The control that ensures regional controllability is defined through a preimage algo- rithm. The second part is devoted to the problem of the boundary regional controllability of Boolean CAs, which consists of acting on the boundary of the domain in order to reach a desired goal in a target region. We first consider linear CAs for which we give a characterization result using the Kalman condition. We propose an algorithm to determine the control that allows to force the appearance of a desired configuration in the study area. The case of nonlinear CAs was also considered using a preimage search algorithm.