# Conversion between Logic and Algebraic Expressions of Boolean Control Networks
## 4 Conversion of Expressions of Boolean Control Networks
### From Logic Expression to Algebraic Expression  
A method for computing the next state of BN (4) is provided in [3] based on the algebraic expression as below. [[3]] For BN (5), if \(x(t)=\delta_{2^{n}}^{2^{n}-i}\), then \(x(t+1)=L\ltimes\delta_{2^{n}}^{2^{n}-i}=\delta_{2^{n}}^{2^{n}-c_{i}}\), where  
\[c_{i}=\sum_{j=1}^{n}s_{i}^{(j)}\times 2^{n-j},\ i=0,1,\cdots,2^{n}-1,\]  
and \(s_{i}^{(j)}\) is the function value in the row \(i\) of the truth table of \(f_{j}\). The lemma above can be extend to BCNs for converting the logic expression into the algebraic expression. For BCN (6), let \(c_{i}\) be defined by  
\[c_{i}=\sum_{j=1}^{n}s_{i}^{(j)}\times 2^{n-j},\ i=0,1,\ldots,2^{m+n}-1, \tag{11}\]  
where \(s_{i}^{(j)}\) is the function value in the row \(i\) of the truth table of \(f_{j}\). Then, the transition matrix of \(N_{in}\) is  
\[L=\delta_{2^{n}}[2^{n}-c_{2^{n+n}-1},\ldots,2^{n}-c_{1},2^{n}-c_{0}]. \tag{12}\]  
In the theorem above, it can be seen that \(c_{i}\) is the decimal representation of the \(n\)-bit binary number whose \(j\)th bit code is \(s_{i}^{(j)}\). Proof. : Let \(L\) be the transition matrix of \(N_{\text{in}}\) and \(x(t)\ltimes u(t)=\delta_{2^{n}}^{2^{n}-i}\). It can be inferred from (7) and Lemma 6 that  
\[x(t+1)=L\ltimes x(t)\ltimes u(t)=L\ltimes\delta_{2^{n}}^{2^{n}-i}=\delta_{2^{n}} ^{2^{n}-c_{i}}.\]  
This implies that the \((i+1)\)th column of \(L\) from right is \(\delta_{2^{n}}^{2^{n}-c_{i}}\), i.e., \(L\) is equal to (12). The following lemma for constructing the transition matrix of \(N_{\text{out}}\) can be obtained in almost the same way. Theorem 4.2: _For BCN (6), let \(\tilde{c}_{i}\) be defined by_  
\[\tilde{c}_{i}=\sum_{r=1}^{p}\tilde{s}_{i}^{(r)}\times 2^{p-r},\ i=0,1,\ldots,2^ {n}-1, \tag{13}\]  
_where \(\tilde{s}_{i}^{(r)}\) is the function value in the row \(i\) of the truth table of \(g_{r}\). Then, the transition matrix of \(N_{\text{out}}\) is_  
\[H=\delta_{2^{p}}[2^{p}-\tilde{c}_{2^{n}-1},\ldots,2^{p}-\tilde{c}_{1},2^{p}- \tilde{c}_{0}]. \tag{14}\]  
The following algorithm for converting the logic expression to the algebraic expression of a BCN can then be developed. Next, let us consider the computational complexity of Algorithm 1 starting from the minterm canonical form. Input: Logic expression of \(N_{\text{in}}\) (resp. \(N_{\text{out}}\)). Output: Transition matrix \(L\) (resp. \(H\)). Setp 1. For \(N_{\text{in}}\), construct the truth table of \(f_{j}\) for each \(j\in\{1,2,\ldots,n\}\), which is denoted by  
\[(s_{0}^{(j)}\ s_{1}^{(j)}\ \ldots\ s_{2^{m+n}-1}^{(j)})^{\intercal}.\]  
Setp 2. Compute \(c_{i}\) by Formula (11). Setp 3. The control-depending network transition matrix is given in (12). Setp 4. For \(N_{\text{out}}\), construct the truth table of \(g_{r}\) for each \(r\in\{1,2,\ldots,p\}\), which is denoted by  
\[(\tilde{s}_{0}^{(r)}\ \tilde{s}_{1}^{(r)}\ \ldots\ \tilde{s}_{2^{m}-1}^{(r)})^{\intercal}.\]  
Setp 5. Compute \(\tilde{c}_{i}\) by Formula (13). Setp 6. The transition matrix from \(x(t)\) to \(y(t)\) is given in (14). Theorem 4.3: _Algorithm 1 has a complexity of \(O(2^{m+n}n)\)._  
Proof. : In Step 1 (resp. Step 4), the truth tables of \(f_{j}\) (resp. \(g_{r}\)) can be obtained directly from their minterm canonical forms without any calculation. In Step 2, the computation cost of \(c_{i}\) is one exponent and \(n\) multiplication together with \(n-1\) addition. Hence, the number of operations of Step 2 is at most \(2n\times 2^{m+n}=2^{m+n+1}n\). Step 3 requires \(2^{m+n}\) subtraction operations to compute the transition matrix \(L\). Hence, the computation cost of \(N_{\text{in}}\) is \(2^{m+n+1}n+2^{m+n}=2^{m+n}(2n+1)\). Similarly, the computation cost of \(\tilde{c}_{i}\) is \(2p\), and hence the number of operations of Step 5 is at most \(2p\times 2^{n}=2^{n+1}p\). Step 6 requires \(2^{n}\) subtraction operations to compute the transition matrix \(H\). Hence, the computation cost of \(N_{\text{out}}\) is \(2^{n+1}p+2^{n}=2^{n}(2p+1)\). Therefore, the computational complexity of Algorithm 1 is \(O(2^{m+n}n)\).