Markov Chains Approach for Regional Controllability of Deterministic Cellular Automata, via Boundary Actions
Sara Dridi, Franco Bagnoli and Samira El Yacoubi
This paper is focused on studying the problem of regional controllability via boundary actions on a target region of a deterministic Cellular Automaton (CA). This problem has already been studied for continuous systems described by partial differential equations (PDEs). The concept of controllability was first identified by R. Kalman in 1960. In linear systems analysis the Kalman rank condition is omnipresent and was used to obtain the main characterization results on controllability. The purpose of this paper is to study this concept applied to Cellular Automata models considered as the discrete counterpart of PDEs. We focus on regional controllability that considers objectives to be achieved only on a subregion of the whole domain and the controls exerted on the boundary of the target region. We prove the regional controllability of two dimensional deterministic linear cellular automata by exploring a new approach based on Markov chains. The extension to non-linear CA has also been studied.
Keywords: Regional controllability, deterministic cellular automata, Markov chains