Transition System Representation of Boolean Control Networks

Since Kauffman proposed the BN to formulate genetic networks [17], the study of BNs and BCNs becomes a heat topic in the biological community as well as in the control community. Consider a BN,

where $X_{i}\in{\mathcal{D}}:=\{0,1\}$, $f_{i}:{\mathcal{D}}^{n}\rightarrow{\mathcal{D}}$, $i\in[1,n]$.

It is clear that every trajectory can converge to an attractor (either a fixed point or a cycle) because it consists only of finite nodes and each node can take only two values ${\mathcal{D}}=\{0,1\}$. Thus, the attractors, with their attractor basins, form the entire topological structure of a BN. Therefore, finding both fixed points and cycles of a given BN becomes a first priority problem in the study of BN. Many early works considered this problem by providing methods to solve a certain class of BNs [8, 13, 9, 12], to name a few.

In the last two decades, the semi-tensor product (STP) of matrices has been used to transform BN (or BCN) into an algebraic discrete-time dynamical (control) system. The STP approach to BN (BCN) has proven to be very efficient. Many theoretical results have been obtained.

The basic step for the STP approach can be described in a nutshell as follows: construct the so-called vector form of $X_{i}$ as

where $\Delta:=\Delta_{2}$, and $\Delta_{k}:=\operatorname{Col}(I_{k})$ is the column set of the identity matrix $I_{k}$.

Using the vector form for $X_{i}$, the system (1) can be expressed in its algebraic state space representation (ASSR) as [3]

where $x(t)=\ltimes_{i=1}^{n}x_{i}(t)\in\Delta_{2^{n}}$ and $M=M_{1}*M_{2}*\cdots,*M_{n}\in{\mathcal{L}}_{2^{n}\times 2^{n}}$, with $M_{i}$ being the structure matrix of $f_{i}$, $*$ is the Khatri-Rao product of matrices [5].

The general formula for calculating the number of attractors is given by [2] as

Consider a $k$-valued logical network. Assume it is expressed as in (1) with only $X_{i}\in{\mathcal{D}}_{k}=\{1,\cdots,k\}$, $i\in[1,n]$. Let $j\sim\delta_{k}^{j}$, $j\in[1,k]$, and

is the vector form of $X_{i}$. Then its ASSR is still expressed as in (2) with only $M\in{\mathcal{L}}_{k^{n}\times k^{n}}$.

Taking into account the observations of Remark I.2, the following result is also obvious.

The cycles of BCN have also been studied in several papers, e.g. [25, 19] etc. But there is no formula similar to (3) to calculate all control attractors.

A transition system (TS) is a more general finite-valued network. A BN can be seen as an autonomous TS and a BCN as a TS. The TS itself is a very useful framework for representing finite automata (FA) [10, 15, 16]. In particular, it provides a fundamental framework for hybrid systems [22, 21]. The STP approach to FAs has also been developed [23, 24, 7].

To our best knowledge, the topological structure of a TS, or the structure of its attractors, has not been clearly revealed. “Can the formula (3) be applied to them?” is still an open problem.

In this paper, we first consider the topological structure of autonomous TS. Two types of cycles are considered: simple cycles and compound cycles. Then the number of attractors with different lengths is calculated. Then the transformation of BCN into autonomous TS is considered. Using transformed TS, the attractors of BCN can be calculated. Finally, some applications of such transformations are examined.

The remainder of this paper is structured as follows:

Section II considers the topological structure of TSs, and the formula of fixed points and cycles for networks is extended to TSs. Section III investigates the state-based representation of BCNs with some direct applications. Section IV discusses the output-based representation of BCNs, called the simulation of BCNs. Furthermore, the formula for the simulation dynamics is obtained. The output robust controls are also investigated. Section V is a brief conclusion.

The notations used in the text are listed below:

• •

  $\operatorname{Col}(A)$ ($\operatorname{Row}(A)$): the set of columns (rows) of $A$.

• •

  ${\mathcal{D}}_{k}:=\{1,2,3,\cdots,k\}$.

• •

  $\delta_{n}^{i}$: the $i$-th column of the identity matrix $I_{n}$.

• •

  $\Delta_{n}:=\Delta_{n}=\{\delta_{n}^{i}\,|\,i=1,2,\cdots,n\}$.

• •

  ${\mathcal{L}}_{m\times n}$: the set of ${m\times n}$ logical matrices, that is, $\operatorname{Col}({\mathcal{L}})\subset\Delta_{m}$.

• •

  ${\mathcal{B}}_{m\times n}$: the set of $m\times n$ Boolean matrices, that is, $[{\mathcal{B}}]_{i,j}\in{\mathcal{D}}:=\{0,1\}$.

• •

  $\delta_{m}[i_{1},i_{2},\cdots,i_{n}]:=[\delta_{m}^{i_{1}},\delta_{m}^{i_{2}},\cdots,\delta_{m}^{i_{n}}]\in{\mathcal{L}}_{m\times n}$.

• •

  $A+_{\mathcal{B}}B$: the Boolean addition of $A,B\in{\mathcal{B}}_{m\times n}$ that is, $[A+_{\mathcal{B}}B]_{i,j}=[A]_{i,j}\vee[B]_{i,j}$, $\mathop{\sum}\limits_{\mathcal{B}}$ is the Boolean sum.

• •

  $A\times_{\mathcal{B}}B$: the Boolean product of $A,B$. For $A\in{\mathcal{B}}_{n\times n}$, $A^{(s)}:=\underbrace{A\times_{\mathcal{B}}A\times_{\mathcal{B}}\cdots\times_{\mathcal{B}}A}_{s}$.

Then the dynamics of a TS can be expressed as

For a TS where $|{\mathcal{X}}|=n$, $|{\mathcal{U}}|=m$, and $|{\mathcal{O}}|=p$, a subset $X(t)\in 2^{\mathcal{X}}$ can be expressed into vector form as $x(t)=(x_{1}(t),x_{2}(t),\cdots,x_{n}(t))^{\mathrm{T}}\in{\mathcal{B}}^{n}$, which is a Boolean vector, where

Using vector form expressions, similar to BN (or $k$-valued network), the ASSR of a transition system can be expressed as

where $L\in{\mathcal{B}}_{n\times nm}$ is a Boolean matrix, $H\in{\mathcal{L}}_{p\times n}$ is a logical matrix.

It is also clear that the ASSR of an autonomous TS is

where, $M\in{\mathcal{B}}_{n\times n}$ is a Boolean matrix.

Consider a partition as:

Following the argument in Remark I.2, it is easy to obtain the following result:

As shown in Example II.5, the length $s>0$ of a CC could be arbitrarily large, so applying formula (3) to calculate the numbers of all its CCs with arbitrary length $s>0$ is impossible. The problem can be solved by observing the following facts:

• •

  An SC is a cycle of length $s\leqslant n$;

• •

  Any CC can be viewed as a recursive concatenation or insertion of SCs. For example, consider a trajectory of the form $C:=(y,\cdots,\xi,x_{1},x_{2},\cdots,x_{\ell-1},\xi,\cdots,y)$ where $x_{1},x_{2},\cdots,x_{\ell-1}$ are distinct; then $(\xi,x_{1},x_{2},\cdots,x_{\ell-1})$ is an SC (of length less than $n$); replace the subsequence $\xi,x_{1},x_{2},\cdots,x_{\ell-1},\xi$ in $C$ by $\xi$ and keep finding subcycles that are SCs in the remaining trajectory, we will end up partitioning the trajectory into SCs and finding it constructed by recursively inserting SCs into an SC.

Therefore, we only have to compute all SCs using the formula (3) and the algorithm for finding attractors of BNs (or $k$-valued networks) [2]. Then the SCs are sufficient to describe the topological structure of the autonomous TS.

We consider a simple example.