Abstract
Invertibility is an interesting and classical control-theoretic problem. However, there has been no result for the invertibility of Boolean control networks (BCNs) so far. We first adopt the theory of symbolic dynamics to characterize it. First, it is shown that a BCN generates a continuous mapping from the space of input trajectories to the space of output trajectories. Based on it, the concepts of nonsingularity and invertibility of BCNs are first defined as the injectivity and bijectivity of the mapping, respectively. Second, combined symbolic dynamics with the semi-tensor product (STP) of matrices, an equivalent test criterion for invertibility is given; easily computable algorithms to construct the inverse BCN for an invertible BCN are presented; and it is proved that invertibility remains invariant under coordinate transformations. Third, an equivalent test criterion for nonsingularity is given via defining a novel directed graph that is called weighted pair graph. Lastly, as an application of invertibility to systems biology, we prove that the BCN model proposed in Fauré et al. (2006) is not invertible, i.e., we prove that arbitrarily controlling mammalian cell cycles is unfeasible at the theoretical level.