Analysis and control of Boolean networks. A semi-tensor product approach. (Q992742)

The aim of the book is to provide a new framework for the study of Boolean control networks. The main device is the left semi-tensor product, which allows the transformation of a logical relation into an algebraic equation. This approach is then applied to logical dynamical systems and to Boolean control networks, which are converted into discrete-time linear and bilinear systems respectively. These representations give the possibility to apply the concepts and techniques of the control theory to the analysis and synthesis of Boolean control networks. The main topics of the control theory are studied in this approach, such as controllability, observability, stability, realization theory, disturbance decoupling and optimal control. The book is structured in 19 Chapters and 2 Appendices. The introductory Chapter 1 presents some elements of the propositional logic, from two-valued (Boolean) logic to multivalued logic. Chapter 2 is devoted to the properties of the (left) Semi-Tensor Product (STP) of matrices, defined for \(A\in{\mathcal M}_{m\times r}\) and \(B\in{\mathcal M}_{p\times q}\) by \[ A\ltimes B=A(B\otimes I_n)\;\text{ if }\;r=np\quad \text{and}\quad A\ltimes B=(A\otimes I_n)B\;\text{ if }\;p=nr. \] STP is a generalization of the usual matrix product (when \(r=p\)). The right STP and the general STP (for matrices of arbitrary dimensions) are also defined, but the left STP reveals to be more useful. Chapter 3 introduces the structure matrix \(M_f\) of a logical function \(f\). The finite set \({\mathcal D}=\{T,F\}\) is considered, with the identification of \(T\) (true) and \(F\) (false) with the vectors \([1\;0]^T\) and \([0\;1]^T\) respectively. It is shown that for any logical function \(f:{\mathcal D}^r\rightarrow{\mathcal D}\), there exists a unique \(2\times 2^r\) matrix \(M_f\) such that \[ f(p_1,p_2,\dots,p_r)=M_f\ltimes p_1\ltimes p_2\ltimes \cdots\ltimes p_r, \] for any logical variables \(p_i\), \(i=1,2,\dots,r\) (i.e. variables taking values in \({\mathcal D})\). This result is extended to \(k\)-valued logical functions with \(k\)-valued logical variables. In Chapter 4 systems of logical equations are studied, which have the form \[ f_i(p_1,p_2,\dots,p_n)=C_i, \quad i=1,2,\dots,m,\tag{1} \] where \(p_i\) are logical unknowns, \(C_i\in{\mathcal D}\) are logical constants and \(f_i\), \(i=1,2,\dots,m\) are logical functions \(f_i:{\mathcal D}^n\rightarrow{\mathcal D}\). The system (1) is converted into an equivalent algebraic equation \[ Lx=b,\tag{2} \] where \(L\) is a \(2^m\times2^n\) logical matrix, \(x=\ltimes_{i=1}^np_i\) and \(b=\ltimes_{i=1}^mC_i\). The solution of (2) is provided and these results are extended to general logical equations having the form \(f(p_1,p_2,\dots,p_n)=g(q_1,q_2,\dots,q_m)\) and to \(k\)-valued logical equations. Chapter 5 deals with the topological structure of Boolean networks. A network is described by a system of discrete-time equations \[ x_i(t+1)=f_i(x_1(t),x_2(t),\dots,x_n(t)), \quad i=1,2,\dots,n,\tag{3} \] where \(f_i\) are \(n\)-ary logical functions. Using (2) the system is represented as \[ x(t+1)=Lx(t)\tag{4} \] and \(L\) is called the transition matrix of the system. It is shown that the dynamics of the Boolean network (3) is uniquely determined by the linear discrete-time dynamical system (4). The topological structures of the Boolean networks are investigated via their transition matrices and some algorithms are developed to obtain all the fixed points, cycles, transient periods and basins of attractors. Some examples from the literature are revisited and it is emphasized that this approach is universal and precise. Serial and higher-order Boolean networks are also studied. In Chapter 6 a Boolean Control Network (BCN) is defined by the state and output equations \[ \begin{aligned} x_i(t+1)=f_i(x_1(t),x_2(t),\dots,x_n(t),u_1(t),u_2(t),\dots,u_m(t)), &\quad i=1,2,\dots,n, \\ y_j(t)=h_j(x_1(t),x_2(t),\dots,x_n(t)), &\quad j=1,2,\dots,p,\end{aligned} \] where \(f_i\in{\mathcal D}^{n+m}\rightarrow{\mathcal D}\) and \(h_j\in{\mathcal D}^{n}\rightarrow{\mathcal D}\) are logical functions, \(x_i\in{\mathcal D}\), \(y_j\in{\mathcal D}\) and \(u_l\in{\mathcal D}\) are respectively the states, the outputs and the inputs (controls). It is asumed that the controls are logical variables satisfying a system \[ u_l(t+1)=g_l(u_1(t),u_2(t),\dots,u_m(t)), \quad l=1,2,\dots,m, \] called the input network. By using the STP, the Boolean control network is expressed in algebraic form as \[ x(t+1)=Lu(t)x(t),\quad y(t)=Hx(t), \quad u(t+1)=Gu(t), \] where \(x(t)=\ltimes_{i=1}^nx_i(t)\), \(u(t)=\ltimes_{i=1}^mu_i(t)\), \(y(t)=\ltimes_{i=1}^py_i(t)\) and \(Lu(t)\) is the control dependent network transition matrix. An input-state STP space is defined. The cycles in this space are characterized and the Boolean networks with cascading structure are analysed. In Chapter 7 a rigorous definition for the model construction is provided, as well as a general technique to construct a dynamic model of a Boolean network. Some special cases are examined, including the known network graph case, the uniform model and modeling via data with errors. In Chapter 8 the state-space of a Boolean control network and its subspaces are defined as sets of logical functions and coordinate transformations are studied. Chapter 9 covers the problems of controllability and observability of BCNs. Controllability via two types of controls is considered, namely controls generated by an input Boolean network and controls of free Boolean sequences. Reachable sets are constructed and necessary and sufficient conditions of reachability/observability are obtained. In Chapter 10 the realization problem of BCNs is considered. Controllable/observable normal forms are investigated and a Kalman decomposition is derived. This decomposition is used to construct a minimal realization. Global stability is investigated in Chapter 11 and the global stabilization problem is solved by open-loop controls or by state feedback controls. Chapter 12 solves the disturbance decoupling problem by constructing a feedback which uses an ``output-friendly'' subspace. A constant stabilizing control is provided on the basis of the notion of canalizing mapping. In Chapter 13 the feedback decomposition of BCNs is presented, including the cascading and the parallel state-space decomposition, as well as the input-output decomposition. In Chapter 14 it is shown that the results concerning BCNs can be extended to \(k\)-valued (control) networks. Chapter 15 is devoted to the optimal control of BCNs. The topological structure of logical control networks is studied, as well as the optimal control of higher-order logical control networks. Using the matrix expression of logical functions, a method of finding the optimal trajectory is proposed. Chapter 16 studies the input-state incidence matrix which is used to develop new results concerning controllability, observability, trajectory tracking, control design and the case of mix-valued logical dynamical systems. Chapter 17 deals with the identification of BCNs. Identification problems respectively via input-state and via input-output data are solved. It is shown that a BCN is identifiable from input-output data if and only if it is both controllable and observable. A numerical algorithm is provided and an approximate identification is considered. Chapter 18 discusses an application to game theory. The existence of an optimal control is proved and an algorithm to solve the game is proposed. It is emphasized that the results on Boolean and logical networks can be applied to finding Nash and sub-Nash solutions for the infinitely repeated games. Chapter 19 covers the subject of random Boolean networks. The random Boolean variables, the random logical matrices and their matrix expression are described. Some topological properties are emphasized and the stabilization of a random Boolean network is studied. In Appendix A numerical algorithms are presented for computing a logical matrix, as well as the basic functions for computing the semi-tensor product and the principal logical matrices. Appendix B contains the proofs of some theorems concerning the semi-tensor product. The book is self-contained and contains many examples which illustrate the concepts and the proposed techniques. It is stated that the book represents a fundamental reference for researchers in systems biology, systems science and physics.