Trajectory tracking approach to logical (control) networks

1.   Introduction

Since Kauffman proposed the Boolean network to formulate a genetic regulatory network in 1969 ^[1], there has been considerable researches going on in this field. The most important problem is the topological structure of a Boolean network, which involves the fixed points, cycles, and their basins of attraction ^[2].

Since 2009, the semi-tensor product (STP) of matrices has been introduced into the study of Boolean networks ^[3,4]. STP provides a convenient way to formulate Boolean networks ^[5]. It, therefore, promotes the development of the theory of Boolean network. The development has been merged mainly in two directions. One is the control of Boolean networks. Various of control problems, such as controllability ^[6,7,8], observability ^[9,10,11], stabilization ^[12,13,14], optimal control ^[15,16], tracking ^[17,18], decoupling ^[19,20] etc. Another direction is that the values of states in the networks have been generated from Boolean case, which allows only $\{0, 1\}$, to $k$-valued logical networks ^[21], mix-valued logical networks ^[22], or finite fields ^[23]. Based on the applications of STP to finite valued systems, many valuable results have been obtained, such as game theory ^[24], quantum networks ^[25], shift registers ^[26,27], {finite automaton} ^[28,29], fuzzy systems ^[30], and so on. In addition, STP has important applications in the analysis of finite base spaces, such as numerical/non-numerical algebra ^[31], finite Boolean-type algebras ^[32], etc. Besides, researchers have focused on reinforcement learning-based techniques to study Boolean networks. Literature ^[33,34,35] uses a model-free method based on reinforcement learning to study control issues such as stability and output tracking problems, which is a good alternative to the STP-based methods when the actual system is unknown.

Although the previous research about Boolean networks has tended to be perfect, a severe obstacle in applying STP to finite-valued networks is the computational complexity. Using previous algebraic methods to study finite-value networks tends to bring a high computational cost. In order to reduce the computational complexity, vector form expression of logical (control) networks is proposed in this paper, which is called the structure vector method (SVM). Then, through a one-step trajectory table, some classical problems in control theory, such as topology structure, controllability, and observability, are analyzed again to demonstrate the effectiveness of this method in reducing computational complexity. In fact, $2^n\times 2^n$ dimensional matrices should be computed in the algebraic method used in the existing literature, while only $2^n$ dimensional vectors are used in the structure vector method. Therefore, compared with the algebraic method, the vector form expression can greatly reduce the computational complexity.

The rest of this paper is organized as follows: Section 2 presents some relevant previous results on STP and Boolean networks. Section 3 is devoted to analyzing the attractor and its basin of logical networks. Sections 4 and 5 discuss the controllability and observability of logical networks with some numerical examples. Section 6 summarizes our results in this paper.

Before ending this section, we give a list of notations:

$(1) \; { \mathcal M}_{m\times n}$: The set of $m\times n$ dimensional real matrices.

$(2) \; \mathbb{R}^{n}$: The set of $n$-dimensional real vectors.

$(3) \; \text{Col}(A)$ : The set of columns (rows) of $A$; $\text{Col}_i(A)$ ($\text{Row}_i(A)$): The $i$-th column (row) of $A$.

$(4) \; { \mathcal D}_k$: ${ \mathcal D}_k = \{1, 2, \cdots, k-1, 0\}$.

$(5) \; {\delta}_k^i$: The $i$-th column of identity matrix $I_k$.

$(6) \; {\Delta}_k$: ${\Delta}_k = \text{Col}(I_k) = \left\{{\delta}_k^i\; |\; i = 1, \cdots, k\right\}$

$(7) \; A\in { \mathcal M}_{m\times n}$ is called a logical matrix, if $\text{Col}(A)\subset {\Delta}_m$.

$(8) \; { \mathcal L}_{m\times n}$: The set of $m\times n$ logical matrices.

$(9)$ Assume $L\in { \mathcal L}_{m\times n}$, then $L = [{\delta}_m^{i_1}, {\delta}_m^{i_2}, \cdots, {\delta}_m^{i_n}]: = {\delta}_m[i_1, i_2, \cdots, i_n].$

$(10) \; M_{ij}$: The $(i, j)$-th element of matrix $M$, and $M = [M_{ij}]$ denotes a matrix whose $(i, j)$-th element is $M_{ij}$.

$(11) \; A^T$ denotes the transpose of matrix $A$.

2.   Preliminaries

2.1.   Semi-tensor product of matrices

Since STP is a fundamental tool in our construction, this section will give a brief survey for STP. We refer to ^[36] for more details.

Definition 2.1. Let $A\in \mathcal{M}_{m\times n}$ and $B\in \mathcal{M}_{p\times q}$, $t = \text{lcm}(n, p)$ be the least common multiple of $n$ and $p$. Then the STP of $A$ and $B$, denoted by $A\ltimes B$, is defined as

where $\otimes$ is Kronecker product.

It is easy to see that STP is a generalization of conventional matrix product. That is, when $n = p$, it degenerates to the conventional matrix product, i.e., $A\ltimes B = AB$. Because of this, we omit the symbol $\ltimes$ in most cases.

One of the most important advantages of STP is that it keeps most properties of conventional matrix product available, including association, distribution, etc. In the following we introduce some additional properties of STP, which will be used in the sequel.

Define a swap matrix $W_{[m, n]}\in { \mathcal M}_{mn\times mn}$ as follows:

Proposition 2.2. Let $x\in {\mathbb R}^m$ and $y\in {\mathbb R}^n$ be two column vectors. Then

The following proposition shows how to "swap" a vector with a matrix:

Proposition 2.3. Let $x\in {\mathbb R}^t$ be a column vector, and $A$ be an arbitrary matrix. Then

Definition 2.4. Let $A\in { \mathcal M}_{p\times n}$ and $B\in { \mathcal M}_{q\times n}$. The Kratri-Rao product of $A$ and $B$, denoted by $A*B\in { \mathcal M}_{pq\times n}$, is defined by

Define a matrix $PR_k\in { \mathcal L}_{k^2\times k}$, called the power reducing matrix, as follows:

The function of the power reducing matrix is the following.

Proposition 2.5. Assume $x\in {\Delta}_k$, then

Throughout this paper the default matrix product is assumed to be STP, and the symbol $\ltimes$ is omitted if there is no possible confusion.

2.2.   Matrix expression of logical networks

Assume $X\in { \mathcal D}_k$. The vector form expression of $X$, denoted by $x = \vec{X}$ is defined as

It is worth noting that since the data values used in this paper are all integers, the intervals in the following refer to integer values unless otherwise specified. For example, $[1, n]$ refers to integers from 1 to $n$.

Definition 2.6. Let $X_i\in { \mathcal D}_{k_i}$, $i\in [1, n]$.

(i) A mapping $F:\prod_{i = 1}^n{ \mathcal D}_{k_i}{\rightarrow} { \mathcal D}_{k_0}$ is called a mix-valued logical function, expressed by

(ii) If $k_i = k$, $i\in {[1, n]}$, $F$ is called a $k$-valued logical function.

(iii) If $k_i = 2$, $i\in {[1, n]}$, $F$ is called a Boolean function.

Proposition 2.7. ^[5] Let $F:\prod_{i = 1}^n{ \mathcal D}_{k_i}{\rightarrow} { \mathcal D}_{k_0}$ be a mix-valued logical function. Then there exists a unique logical matrix $M_F$, called the structure matrix of $F$, such that {vector form} (8) can be expressed as

where $y$ and $x_i$, $i\in [1, n]$ are vector form of $Y$ and $X_i$, $i\in [1, n]$ respectively.

Definition 2.8. Let $X_i(t)\in { \mathcal D}_{k_i}$, $i\in [1, n]$, $t = 0, 1, \cdots$ be a set of time-varying logical variables, $G = (N, E)$ be a directed graph with $N = \{1, 2, \cdots, n\}$ and $X_i(t)$ as the logical value of node $i$ at time $t$, $i\in [1, n]$.

(i)

is called a mix-valued logical network, where $F_i$, $i\in [1, n]$ are mix-valued logical functions, ${ \mathcal N}_i \; i\in [1, n]$ are neighborhood of node $i$.

(ii) If there are controls $U_j\in { \mathcal D}_{{\alpha}_j}$, $j\in [1, m]$ and outputs $Y_{\ell}\in { \mathcal D}_{{\beta}_{\ell}}$, $\ell\in [1, p]$, such that

then (11) is called a mix-valued logical control network.

(iii) If $k_i = {\alpha}_s = {\beta}_{\ell} = k$, $i\in [1, n]$, $s\in [1, m]$ and $\ell\in[1, p]$, then (10) is called a $k$-valued logical network, and (11) is called a $k$-valued logical control network.

(iv) If $k_i = {\alpha}_s = {\beta}_{\ell} = 2$, $i\in [1, n]$, $s\in [1, m]$ and $\ell\in[1, p]$, then (10) is called a Boolean network, and (11) is called a Boolean control network.

Set $\kappa = \prod_{i = 1}^nk_i$, ${\alpha} = \prod_{s = 1}^m{\alpha}_s$, ${\beta} = \prod_{\ell = 1}^p{\beta}_{\ell}$. Using Proposition 2.7 to network (10) and control network (11) respectively yields the following result.

Proposition 2.9. ^[5]

(i) Vector form (10) can be expressed as

where $x(t) = \ltimes_{i = 1}^nx_n(t)$, $M_i\in { \mathcal L}_{k_i\times \kappa}$, $i\in [1, n]$.

(ii) In vector form (11) can be expressed as

(12) and (13) are called the component-wise algebraic state space representation (ASSR) of(10) and (11) respectively.

Putting all the components together yields the following overall ASSR.

Proposition 2.10. ^[5]

(i) The component-wise ASSR (12) can be expressed into (overall) ASSR as

where $M = M_1*M_2*\cdots*M_n\in { \mathcal L}_{\kappa\times \kappa}$.

(ii) The component-wise ASSR (13) can be expressed into (overall) ASSR as

where $L = L_1*L_2*\cdots*L_n\in { \mathcal L}_{\kappa\times \kappa{\alpha}}$ and $E = E_1*E_2*\cdots*E_p\in { \mathcal L}_{{\beta}\times \kappa}$.

3.   Attractor and basin of attraction

Consider the ASSR of a logical network (14). Since $M\in { \mathcal L}_{2^n\times 2^n}$, using short-hand expression, one sees easily that a mix-valued logical network can be expressed as a $\kappa$-dimensional vector, which is called the structure vector of network (10).

Next, we consider how to use this structure vector to calculate the attractors of (10). We give an example to depict this.

Example 3.1. Assume $X_1(t), X_3(t)\in { \mathcal D}_2$, $X_2(t)\in { \mathcal D}_3$, and the network dynamics is as follows.

where ${\bigtriangledown}: { \mathcal D}_3\times { \mathcal D}_2{\rightarrow} { \mathcal D}_3$, $\vee: { \mathcal D}_2\times { \mathcal D}_2{\rightarrow} { \mathcal D}_2$, $\neg: { \mathcal D}_2{\rightarrow} { \mathcal D}_2$ with their structure matrices as

It is easy to calculate the structure matrices of $M_i \; i = 1, 2, 3$ as follows:

It follows that

Hence, the ASSR of (16) is

where $M$ is shown in (17). Hence, the network is uniquely determined by the vector

which is called the structure vector of network (16).

The physical meaning of $V_M$ is: It determines a mapping $\pi_M: \Delta_{2^n}\rightarrow {\Delta_{2^n}}$. Say, the first element in $V_{M}$ is $2$ meaning that $\pi_M(\delta_{12}^1) = \delta_{12}^2$, which can also be briefly denoted by $\pi_M(1) = 2$. Hence, we have the mapping as shown in Table 1.

${\delta}_{12}^1$, briefly $1$, is maps to $2$, denoted by $1{\rightarrow} 2$, and

Using this mapping, it is easy to calculate the attractors of network (16) by the following Table 1.

Using this mapping, we can start from any state to calculate whole trajectory as described in Table 2. Note that for each trajectory, if an old state appears again, we use a $*$ to stop the trajectory. That means the trajectory start to go on the second round of cycle.

From Table 2, one sees easily that there is a fixed point, which is $P = {\delta}_{12}^4\sim (1, 2, 2)$, and a cycle, which is $C:{\delta}_{12}^2\leftrightarrow {\delta}_{12}^6$ or $C:(1, 1, 2)\leftrightarrow (1, 3, 2)$. The basin of attraction of each attractor is also clear. That is,

Remark 3.2. Assume $X_i\in { \mathcal D}_{k_i}$, $i\in [1, n]$. The states have two expressions:

(i) Component-wise expression:

(ii) Vector form: Assume $x_i = \vec{X}_i$, $i\in [1, n]$, then the state $X$ can be expressed into its vector form as

Now there are two ways to convert them from one form to the other.

(i) Tabulator method:

Arrange $(X_1, X_2, \cdots, X_n)$ in alphabetic order, then their corresponding vector expressions are in order. For instance, recall Example 3.1. If $(X_1, X_2, X_3)$ are in alphabetic order, then their vector forms are already in order. See Table 3 for this.

(ii) Formula method:

is easily calculated. We consider how to convert $x$ back to $(X_1, X_2, \cdots, X_n)$. Define

Then

4.   Controllability

To describe the transition mapping of a control network, we first introduce a {multi-valued} transition matrix.

Definition 4.1. Let $N = \{1, 2, \cdots, \kappa\}$ be a given finite set. A multi-valued transition matrix is an $\kappa\times \kappa$ matrix $M = [M_{i, j}]$, where $M_{i, j}\in N$.

$M_{i, j}\in N$ means that each element of the matrix $M$ belongs to set $N$, which is also the origin of the name of multi-valued transition matrix.

Definition 4.2. For system (11), let $X(0)\in\mathcal{D}_{\kappa}$ be the initial state and $k > 0$.

● $X(k)\in\mathcal{D}_{\kappa}$ is said to be reachable from $X(0)$ at time $k$ if there exists a control sequence $U(t)$, $t = 1, 2, \dots, k-1$, that leads system (11) from $X(0)$ to $X(k)$. The reachable set from $X(0)$ at time $k$ is denoted by $\mathcal{R}_{k}(X(0))$. The overall reachable set from $X(0)$ is denoted by $\mathcal{R}(X(0)) = \mathcal{D}_{\kappa}$.

● System (11) is said to be controllable at $X(0)$ if $\mathcal{R}(X(0)) = \mathcal{D}_{\kappa}$.

● System (11) is said to be controllable if it is controllable at every $X(0)\in\mathcal{D}_{\kappa}$.

It is well known that in game theory bi-matrix is widely used ^[37]. Multi-valued matrix can be considered as a generalization of bi-matrix. We give an example to depict it.

Example 4.3. Consider a mix-valued network

where $X_1(t), U(t)\in { \mathcal D}_2$, $X_2(t)\in { \mathcal D}_3$, ${\Delta}:{ \mathcal D}_3\times { \mathcal D}_2{\rightarrow} { \mathcal D}_2$ is determined by its structure matrix

and $\Box:{ \mathcal D}_2\times { \mathcal D}_3{\rightarrow} { \mathcal D}_3$ is determined by its structure matrix

The component-wise ASSR of (19) can be calculated as

Then

Then

Finally, we have ASSR of (19) as

where

Since $u$ can be either $0$ or $1$, as $x(0) = {\delta}_{6}^1$ the one step transition mapping, denoted by $\pi_L$, maps ${\delta}_6^1$ into two possible values ${\delta}_6^6$ and ${\delta}_6^3$. We briefly denote it by $\pi_L(1) = \{6, 3\}$. Similarly for other states, we have the {multi-valued} transition mapping, described in Table 4.

Using this mapping, the controllability of (19) can easily be calculated. We construct a set transition matrix. The constructing process is similar to the construction of Table 2. The only difference is now each step the image of $\pi_L$ is a set. Moreover, in the following we construct each column of entries only by picking out new elements. As the process does not provide new element, we stop this column with $\emptyset$. Then we have Table 5 as follows.

By construction the following result is obvious.

Proposition 4.4. Consider the multi-valued trajectory matrix of a control network.The union of elements of each column of set entries, denoted by $R(i)$, $i\in [1, \kappa]$, is the reachable set of the initial element corresponding to this column. So ${\delta}_{\kappa}^i$ is reachable (to any ${\delta}_{\kappa}^j$, $j\in [1, \kappa]$), if and only if, $R(i) = N = \{1, 2, \cdots, \kappa\}$. The network is completely controllable, if and only if, $R(i) = N$, $\forall i\in [1, \kappa]$.

Proof. The union of elements of each column of set entries is actually the reachable set $\mathcal{R}(X(0))$ mentioned in Definition 4.2, where the first element of each column corresponds to the initial state $X(0)$. $R(i) = N = \{1, 2, \cdots, \kappa\}$ means that $\mathcal{R}(X(0)) = \mathcal{D}_{\kappa}$, which is exactly the second rule of the definition of controllability. $\forall i\in [1, \kappa]$, $R(i) = N$ means that it is controllable at every $X(0)\in\mathcal{D}_{\kappa}$, which is exactly the third rule of the definition of controllability.

Example 4.5. Consider network (19). Observe its multi-valued trajectory matrix in Table 5. According to Proposition 4.4, (19) is completely controllable.

5.   Observability

Definition 5.1. System with outputs (11) is said to be observable if for any initial state $X(0)$, there exists at least a control sequence, such that the initial state can be determined by the output sequence.

Observability of Boolean networks has been discussed for long time ^[3]. ^[38] proposed a method to solve the observability of Boolean networks via set controllability. Following the technique of ^[38], the method of multi-valued trajectory matrix can be used to solve observability of mix-valued control networks.

We use an example to describe this.

Example 5.2. Recall network (19). Assume the output is

Following ^[38], we construct an auxiliary system as

Set $\Xi(t) = [X_1(t), X_2(t), Z_1(t), Z_2(t)]$. Then the ASSR of $\Xi$ can be obtained as follows:

where

The mapping $\pi_{\Psi}:N{\rightarrow} 2^N$ can then be determined by $\Psi$ as:

The $\xi(t) = x(t)z(t)$ is called the one-step indistinguishable state, if $x(t)\neq z(t)$ and $y(x(t)) = y(z(t))$. The set of one-step indistinguishable states is denoted by ${ \mathcal I}$. If $x(t)\neq z(t)$ and $y(x(t))\neq y(z(t))$, $\xi(t)$ is called the one-step distinguishable state, and the set of one-step distinguishable states is denoted by ${ \mathcal J}$. Then it is clear that ^[38] a control network is observable, if and only if, each state $\xi\in { \mathcal I}$ can be driven into ${ \mathcal J}$.

Using $M_{{\Delta}}$, it is easy to verify that for network (23) we have

Now we construct the multi-valued trajectory matrix for ${ \mathcal I}$ in Table 6. In each column, when ${ \mathcal J}$ is reached ${ \mathcal J}$ is used to end the trajectory. If there is no new state appearing, $\emptyset$ is used to end the trajectory, which means the $\xi = xz$ in this column is not distinguishable at all.

Now it is clear that the network (19)–(21) is not observable. The only indistinguishable initial pair is ${\delta}_{36}^{24} = {\delta}_6^4{\delta}_6^6\sim \{(2, 1), (2, 3)\}$.

Proposition 5.3. Consider the multi-valued trajectory matrix of a control network. The network is observable if and only if for any state $\delta_{2^n}^i\in I$, it holds that$R(i)\cap{ \mathcal J}\neq\emptyset$.

Proof. $R(i)\cap{ \mathcal J}\neq\emptyset$ holds for any $\delta_{2^n}^i\in I$, if and only if each element in the set of one-step indistinguishable states ${ \mathcal I}$ can be driven into the set of one-step distinguishable states ${ \mathcal J}$ by a proper control, which means that any two initial states can be distinguished, i.e., any initial state can be determined by the output sequence.

Remark 5.4. Assume a mix-valued logical network with $n$ nodes, $m$ inputs and $p$ outputs. Assume $X_{i}\in\mathcal{D}_{k_{i}}$, $U_{s}\in\mathcal{D}_{\alpha_{s}}$, $Y_{l}\in\mathcal{D}_{\beta_l}$, $i = 1, 2, \dots, n$, $s = 1, 2, \dots, m$, $l = 1, 2, \dots, p$. Next we consider the computational complexity of the methods in this paper when the vector form of the system is known. For the method of calculating the attractors in Section 3, since there are at most $\kappa$ states, each column of the table will end after at most $\kappa-1$ steps. Hence, the computational complexity of calculating the attractors is $O(\kappa(\kappa-1))$ in the worse case, where $\kappa = \prod_{i = 1}^{n}k_{i}$. For the method of determining controllability in Section 4, there are also at most $\kappa$ states, and the state generated by every step should be compared with the previous states. Each state needs to be compared at most $1+2+\dots+(\kappa-1)$ times. Therefore, the computational complexity of determining controllability is $O(\frac{\kappa^{2}(\kappa-1)}{2})$ in the worse case. For the method of determining observability in Section 5, there are also at most $1+2+\dots+(\kappa-1)$ state pairs, and each column of the table will end after at most $\kappa-1$ steps. Hence, the computational complexity of determining observability is $O(\frac{\kappa(\kappa-1)^{2}}{2})$ in the worse case, where $\kappa = \prod_{i = 1}^{n}k_{i}$.

6.   Conclusions

Structure vector method for logical (control) networks has been proposed in order to reduce the computational complexity. Using trajectory table, topology structure, controllability and observability has been analyzed. Compared with the existing method, the vector form expression greatly reduces the computational complexity. The method can be used to discuss other problems of logical networks, such as decoupling, delectability, tracking, etc.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (62103716), and the Natural Science Foundation of Shandong Province (ZR2019BF023).

Conflict of interest

All authors declare no conflicts of interest in this paper.