# Conversion between Logic and Algebraic Expressions of Boolean Control Networks
## 2 Preliminaries
\begin{array}{rcl}x_{1}(t+1)&=&f_{1}(x_{1}(t),\ldots,x_{n}(t),u_{1}( t),\ldots,u_{m}(t)),\\ \vdots&&\\ x_{n}(t+1)&=&f_{n}(x_{1}(t),\ldots,x_{n}(t),u_{1}(t),\ldots,u_{m}(t)),\\ y_{1}(t)&=&g_{1}(x_{1}(t),\ldots,x_{n}(t)),\\ \vdots&&\\ y_{p}(t)&=&g_{p}(x_{1}(t),\ldots,x_{n}(t)),\end{array} \right. \tag{6}\]  
where \(f_{j}\) (\(j\in\{1,2,\ldots,n\}\)) and \(g_{r}\) (\(r\in\{1,2,\ldots,p\}\)) are Boolean functions, \(x_{j}(\cdot)\) (\(j\in\{1,2,\ldots,n\}\)) are states, \(u_{k}(\cdot)\) (\(k\in\{1,2,\ldots,m\}\)) are inputs and \(y_{r}(\cdot)\) (\(r\in\{1,2,\ldots,p\}\)) are outputs. Denote by \(N_{\text{in}}\) the network of states and inputs, and by \(N_{\text{out}}\) the network of states and outputs. Since the dynamics of a BCN is composed of a set of Boolean functions, the STP can be used to establish the algebraic expression of BCN (6) as follows:  
\[\left\{ \begin{array}{rcl}x(t+1)&=&L\ltimes x(t)\ltimes u(t),\\ y(t)&=&H\ltimes x(t),\end{array} \right. \tag{7}\]where \(x(t)=\ltimes_{j=1}^{n}x_{j}(t)\in\{0,1\}^{2^{n}}\) is state vector, \(u(t)=\ltimes_{k=1}^{m}u_{k}(t)\in\{0,1\}^{2^{m}}\) and \(y(t)=\ltimes_{r=1}^{p}y_{r}(t)\in\{0,1\}^{2^{p}}\) are input and output vectors, respectively, \(L\in\{0,1\}^{2^{n}\times 2^{n+n}}\) is the control-depending network transition matrix, \(H\in\{0,1\}^{2^{p}\times 2^{n}}\) is the transition matrix from \(x(t)\) to \(y(t)\) (see, e.g., [21; 22; 23]). The STP based method has been presented in ([11], Theorem IV.6) for obtaining the algebraic expression of BCNs by introducing the swap matrix, dummy matrix and power reducing matrix, which has a very high computational complexity of \(O(2^{6(m+n)}n)\) (see [3], Theorem 1). Recently, [PERSON] et al. [26; 27] proposed a Khatri-Rao product based method to obtain such an algebraic expression. **Definition 2** ([28]). : _For \(A\in\mathbb{R}^{m\times p}\) and \(B\in\mathbb{R}^{n\times p}\), the Khatri-Rao product of \(A\) and \(B\) is defined to be a partitioned matrix of order \(mn\times p\) as follows:_  
\[A*B=[A_{1}\otimes B_{1}\;\;A_{2}\otimes B_{2}\;\;\cdots\;\;A_{p}\otimes B_{p}],\]  
_where \(A_{r}\) (resp. \(B_{r}\)) \((r\in\{1,2,\ldots,p\})\) is the \(r\)-th column of \(A\) (resp. \(B\)), and \(\otimes\) is the Kronecker product of matrices._  
**Lemma 3** ([26; 27]). : _For BCN (6), the control-depending network transition matrix is \(L=*_{j=1}^{n}M_{j}^{in}\), and the transition matrix from \(x(t)\) to \(y(t)\) is \(H=*_{r=1}^{p}M_{r}^{out}\), where \(M_{j}^{in}\) and \(M_{r}^{out}\) are the structure matrices of \(f_{j}\) and \(g_{r}\), respectively._  
It is known that at most \(mnp\) multiplication operations are required to compute the Khatri-Rao product of two matrices with sizes of \(m\times p\) and \(n\times p\). Then, at most \(2^{n}2^{m+n}=2^{m+2n}\) (resp. \(2^{p}2^{n}=2^{n+p}\)) operations are requited to compute the transition matrix \(L\) (resp. \(H\)) by using the lemma above. Hence, the computational complexity of Lemma 3 is \(O(2^{m+2n})\), which decreases exponentially that of the STP based method. Quantitatively, the complexity of the STP based method is \(2^{5m+4n}n\) times that of the Khatri-Rao product based method. This paper will provide a method with a much lower complexity.