# A Note on the Observability of Temporal Boolean Control Network

Authors: Wenping Shi; Bo Wu; Jing Han
Journal: Abstract and Applied Analysis
 (2013)

---

## Abstract

Temporal Boolean network is a generalization of the Boolean network model that takes
into account the time series nature of the data and tries to incorporate into the model the
possible existence of delayed regulatory interactions among genes. This paper investigates the
observability problem of temporal Boolean control networks. Using the semi tensor product of
matrices, the temporal Boolean networks can be converted into discrete time linear dynamic
systems with time delays. Then, necessary and sufficient conditions on the observability via
two kinds of inputs are obtained. An example is given to illustrate the effectiveness of the
obtained results.


---

## Body

## 1. Introduction

Boolean network (BN) is the simplest logical dynamic system. It was proposed by Kauffman for modeling complex and nonlinear biological systems; see [1–3]. Since then, it has been a powerful tool in describing, analyzing, and simulating the cell networks. In this model, gene state is quantized to only two levels: true and false. Then, the state of each gene is determined by the states of its neighborhood genes, using logical rules.The control of BN is a challenging problem. So far, there are only few results on it because of the shortage of systematic tools to deal with logical dynamic systems; see [4, 5]. Recently, a new matrix product, which was called the semitensor product (STP) [4], was provided to convert a logical function into an algebraic function, and the logical dynamics of BNs could be converted into standard discrete-time dynamics. Based on this, a new technique has been developed for analyzing and synthesizing Boolean (control) networks (BCNs); see [4, 6–9]. Furthermore, [10] have presented some simple criteria to judge the controllability with respect to input-state incidence matrices of BCNs. A Mayer-type optimal control problem for BCNs with multi-input and single input has been studied in [11, 12].Systematic analysis of biological systems is an important topic in systems biology, and the observability is a structural property of systems. There have been many results on the controllability and observability of dynamic systems; see [13–18]. When it comes to the observability problem of BNs, Cheng and Qi have obtained necessary and sufficient conditions for the observability of BCNs in [8]. However, simple Boolean method cannot be used to study the kinetic properties of networks because it does not have time components, and time delay behaviors happen frequently in biological and physiological systems. In [19], the observability problem for a class of Boolean control systems with time delay is investigated.It is well known that time delay phenomenon is very common in the real world [20, 21] and very important in analysis and control for dynamic systems. Since many experiments involve obtaining gene expression data by monitoring the expression of genes involved in some biological process (e.g., neural development) over a period of time, the resulting data is in the form of a time series [22]. It is interesting to understand how the expression of a gene at some stage in the process is influenced by the expression levels of other genes during the stages of the process preceding it. Temporal Boolean networks (TBNs) are developed to help model the temporal dependencies that span several time steps and model regulatory delays, which may come about due to missing intermediary genes and spatial or biochemical delays between transcription and regulation; see [23–25].It should be noticed that TBCN is similar with higher-order BCN from Chapter 5 of [26] in which the higher-order BCN can be rewritten by a BCN by using the first algebraic form of the network. Hence, the observability analysis for higher-order BCNs can be obtained from [26]. However, if the first algebraic form is used, the dimension of network transition matrix depending on the number of logical variables will be much larger which would make computation cost much higher [27]. Motivated by the above analysis, the purpose of this paper is to use STP developed in [4, 6–9, 28] to analyze the observability problem of TBCN without changing it into BCN, which generalizes the BN model to cope with dependencies that span over more than one unit of time.The rest of this paper is organized as follows. Section2 provides a brief review for the STP of matrices and the matrix expression of logical function. In Section 3, we convert TBCN into discrete time delay systems. In Section 4, necessary and sufficient conditions for the observability of the temporal BCNs are obtained. An example is given to illustrate the efficiency of the proposed results in Section 5. Finally, a brief conclusion is presented.


## 2. Preliminaries

For simplicity, we first give some notations as in [4]. Denote Mm×n as the set of all m×n matrices. The delta set Δk:={δki∣i=1,2,…,k}, where δki is the ith column of identity matrix Ik with degree k. A matrix A∈Mm×n is called a logical matrix if the columns set of A, denoted by Col(A), satisfies Col(A)⊂Δm. The set of all m×n logical matrices is denoted by ℒm×n. Assuming A=[δmi1,δmi2,…,δmin]∈ℒm×n, we denote it as A=δm[i1,i2,…,in].We recall the concept of STP. LetX be a row vector of dimension np and Y a column vector of dimension p. Then, we split X into equal-sized blocks as X1,…,Xp, which are 1×p rows. Define the STP, denoted by ⋉, as
(1)X⋉Y=∑i=1p‍Xiyi∈Rn,YT⋉XT=∑i=1p‍yi(Xi)T∈Rn.
In this paper, “⋉” is omitted, and throughout this paper the matrix product is assumed to be the semi-tensor product as in [9].The swap matrixW[m,n] is an mn×mn matrix. Label its columns by (11,12,…,1n,…,m1,m2,…,mn) and its rows by (11,21,…,m1,…,1n,2n,…,mn). Then, its element in the position ((I,J),(i,j)) is assigned as
(2)w(I,J),(i,j)=δi,jI,J={1,I=i,J=j,0,otherwise.
When m=n, we briefly denote W[n]=W[m,n]. Furthermore, for X∈ℝm and Y∈ℝn,  W[m,n]⋉X⋉Y=Y⋉X and   W[n,m]⋉Y⋉X=X⋉Y.A logical domain, denoted by𝒟, is defined as 𝒟:={T=1,F=0}. To use matrix expression, we identify each element in 𝒟 with a vector as T~δ21 and F~δ22 and denote Δ:=Δ2={δ21,δ22}. Using STP of matrices, a logical function with n arguments L:𝒟n→𝒟 can be expressed in the algebraic form as follows.Lemma 1 (see [9]).
Any logical functionL(A1,…,An) with logical arguments A1,…,An∈Δ can be expressed in a multi-linear form as
(3)L(A1,…,An)=MLA1⋯An,
where ML∈ℒ2×2n is unique which is called the structure matrix of L.Lemma 2 (see [9]).
Assume thatPk=A1⋯Ak with logical arguments A1,…,Ak∈Δ, then
(4)Pk2=ΦkPk,
where Φk=∏i=1k‍I2i-1⊗[(I2⊗W[2,2k-i])Mr],  Mr=δ4[1,4].


## 3. Algebraic Form of Temporal Boolean Networks

We consider the temporal Boolean network [25] of a set of nodes A1,…,An∈Δ as follows:
(5)Ai(t+1)=fi(A1(t),…,An(t),A1(t-1),…,An(t-1),…,A1(t-τ),…,An(t-τ)),i=1,2,…,n,
where fi,  i=1,2,…,n are logical functions, t=0,1,2,…, and τ is a positive integer delay.Using Lemma1, for each logical function fi,  i=1,2,…,n, we can find its structure matrix Mi. Let x(t)=⋉i=1nAi(t). Then, the system (5) can be converted into an algebraic form as
(6)Ai(t+1)=Mi⋉j=1nAj(t)⋯⋉j=1nAj(t-τ)=Mix(t)⋯x(t-τ),i=1,…,n.
From Lemma 2, multiplying all systems in (6) together yields
(7)x(t+1)=⋉i=1nAi(t+1)=⋉i=1n[Mix(t)⋯x(t-τ)]=M1[(I2n(τ+1)⊗M2)Φn(τ+1)]x(t)⋯×x(t-τ)M3⋯Mnx(t)⋯x(t-τ)=M1[⋉i=23I2n(τ+1)⊗MiΦn(τ+1)]x(t)⋯×x(t-τ)M4⋯Mnx(t)⋯x(t-τ)=⋯=M1[⋉i=2nI2n(τ+1)⊗MiΦn(τ+1)]x(t)⋯x(t-τ).
Denote L0:=M1[⋉i=2nIn(τ+1)⊗MiΦn(τ+1)]. Then (7) can be expressed as
(8)x(t+1)=L0x(t)⋯x(t-τ),
and L0 is called the network transition matrix of (5).Next, we consider temporal Boolean control network with outputs as follows:(9)Ai(t+1)=fi(An(t-τ)u1(t),…um(t),A1(t),…,An(t),…,A1(t-τ),…,An(t-τ)),i=1,…,n,yj(t)=hj(A1(t),…,An(t)),j=1,…,p,
where ui,  i=1,2,…,m are inputs (or controls); yj(t),  j=1,…,p are outputs; fi,  i=1,…,n;  hj,j=1,…,p are logical functions.In this paper, two kinds of inputs (or controls) are considered for (9).(A) The controls satisfying certain logical rules are called input networks such as(10)uj(t+1)=gj(u1(t),u2(t)⋯um(t)),j=1,…,m,
where gi,  i=1,2,…,m are logical functions, and the initial states uj(0),  j=1,2,…,m, can be arbitrarily given.(B) The controls are free Boolean sequences, which means that the controls do not satisfy any logical rule.Letu(t)=⋉j=1muj(t),  y(t)=⋉j=1pyj(t). From Lemma 1, for every logical function fi,  gj,  hl, we can find its structure matrix M1i,  M2j,  M3l,  i=1,…,n,  j=1,…,m,  l=1,…,p, respectively. Then from (9) and (10), we can obtain
(11)Ai(t+1)=M1iu(t)x(t)⋯x(t-τ),i=1,…,n,(12)uj(t+1)=M2ju(t),j=1,…,m,(13)yl(t)=M3lx(t),l=1,…,p.
Similar with (7), multiplying (11) yields
(14)x(t+1)=⋉i=1n[M1iu(t)x(t)⋯x(t-τ)]=M11[(I2m+n(τ+1)⊗M12)Φm+n(τ+1)]u(t)x(t)⋯×x(t-τ)M13⋯×M1nu(t)x(t)⋯x(t-τ)=⋯=M11[⋉i=2n(I2m+n(τ+1)⊗M1iΦm+n(τ+1))]u(t)x(t)⋯×x(t-τ)≜Lu(t)x(t)⋯x(t-τ).
And, multiplying (12), it leads to
(15)u(t+1)=u1(t+1)u2(t+1)⋯um(t+1)=M21u(t)M22u(t)⋯M2nu(t)=M21(I2m⊗M22)Φm(I2m⊗M23)Φm⋯×(I2m⊗M2m)Φmu(t)≜Gu(t).
Multiplying (13) yields y(t)=Hx(t), where H=M31[⋉l=2p(I2n⊗M3lΦn)]. From the above conclusion, in an algebraic form, a BCN (9) and (10) can be expressed as
(16)x(t+1)=Lu(t)x(t)⋯x(t-τ),y(t)=Hx(t),(17)u(t+1)=Gu(t),
where L,H are the network transition matrices of two kinds of equations in (9), respectively, and G is the network transition matrix of (10).Remark 3.
It should be noticed that by using the first algebraic form of the network from Chapter 5 of [26], TBCN can be rewritten by a BCN with no delay. Hence, it can be a good idea to study the observability of TBCNs by using the corresponding BCNs from the results in [10]. However, if the first algebraic form is used, the dimension of network transition matrix of corresponding BCNs will be much bigger which would make computation cost much higher. From (16), it is easy to calculate that the dimension of L is 2n×2n(τ+1)+m. However, if the TBCNs are rewritten by BCNs using the first algebraic form, then the dimension of the corresponding network transition matrix of the BCNs would be 2n(τ+1)×2n(τ+1)+m, which is much bigger if n or τ is a large number. Furthermore, considering the TBCNs directly, we can find the relationship between the network transition matrix (or the Boolean functions) of the TBCN and the state clearly. However, if the BCN is used, the relationship would not be so clear.


## 4. Observability of Temporal Boolean Control Networks

In this section, we consider the observability problem of temporal Boolean control network (9), equivalently (16), and the analysis is given via two kinds of controls (A) and (B), respectively.Definition 4 (see [19]).
The temporal Boolean network (16) is observable if for the initial state sequence x(-i),  i∈{0,1,…,τ}, there exists a finite time s∈ℕ, such that the initial state sequence can be uniquely determined by the input controls u(0),u(1),…,u(s) and the outputs y(0),y(1),…,y(s).For simplicity, we denote the vector𝒳(i)=⋉j=0ix(-j)∈Δ2n(τ+1),  i∈{0,1,…,τ}.Definition 5 (see [19]).
For temporal Boolean network (16) and control (17) with fixed G, the input-state transfer matrix ℒiG∈ℒ2n×2m+n(τ+1),  i∈ℕ+, is defined as follows: for any u(0)∈Δ2m and any x(-i)∈Δ2n,  i∈{0,1,…,τ}, we have
(18)x(i)=ℒiGu(0)𝒳(τ),i∈ℕ+.Now we need a dummy operator to add some fabricated variables when these variables do not appear. Define(19)En,m≔[I2nI2n⋯I2n]︸2mn=δ2n[1,2,…,2n︸,…,1,2,…,2n︸]︸2mn.
A straightforward computation shows the following.Lemma 6.
Consider the temporal Boolean network (16),
(20)x(0)=En,τW[2n,2nτ]𝒳(τ).Proof.
Since⋉i=1τx(-i)∈Δ2nτ, from the definition of En,m, we have
(21)En,τ⋉i=1τx(-i)=I2n.
Hence,
(22)x(0)=I2nx(0)=En,τ⋉i=1τx(-i)x(0)=En,τW[2n,2nτ]𝒳(τ).


### 4.1. Observability of Input Boolean Networks

We first consider the case that controls satisfy certain logical rules as (17). Define a sequence of matrices ℒsG∈ℒ2n×2m+n(τ+1) as (23):
(23)ℒsG≔{L,s=1,LG[(I2m⊗ℒ1G)Φm][I2m⊗W2nτ,2n(τ+1)Φn(τ)],L,s=2,LGs-1[(I2m⊗ℒs-1G)Φm][⋉i=s-21ℳiG]⋉[I2m⊗W[2n(τ-s+2),2n(τ+1)]Φn(τ-s+2)],L,s=3,…,τ+1,LGs-1[(I2m⊗ℒs-1G)Φm][⋉i=s-2s-τ-1ℳiG],L,s>τ+1,
where ℳiG=I2m+n(τ+1)⊗ℒiGΦm+n(τ+1) and ℋ0G=HEn,τW[2n,2nτ],  ℋsG=HℒsG,s∈ℕ+, and the transition matrices L, G, and H are defined in (16) and (17). Furthermore, we split ℋjG∈ℒ2p×2m+n(τ+1), j∈ℕ+, into 2m equal blocks as ℋjG=[ℋj,1G,ℋj,2G,…,ℋj,2mG] with each ℋj,iG∈ℒ2p×2n(τ+1), i=1,2,…,2m, j∈ℕ+.Theorem 7.
Consider the temporal Boolean network (16) with control (17). Assume that u(0)=δ2mi,  i∈{1,2,…,2m}. Then, (16) and (17) are observable if and only if there exists a finite time s such that rank(𝒪1,i,s)=2n(τ+1), where
(24)𝒪1,i,s=[ℋ0Gℋ1,iG⋮ℋs,iG].Proof.
Firstly, from Lemma6 and (16),
(25)y(0)=Hx(0)=HEn,τW[2n,2nτ]𝒳(τ)≜ℋ0G𝒳(τ).
Since u(0)=δ2mi, we have from (18) that
(26)y(1)=Hx(1)=HLu(0)𝒳(τ)≜Hℒ1Gu(0)𝒳(τ)=ℋ1,iG𝒳(τ),y(2)=HLu(1)x(1)𝒳(τ-1)=HLGu(0)ℒ1Gu(0)𝒳(τ)𝒳(τ-1)=HLG[(I2m⊗ℒ1G)Φm]u(0)𝒳(τ)𝒳(τ-1)=HLG[(I2m⊗ℒ1G)Φm]u(0)W[2nτ,2n(τ+1)]Φnτ𝒳(τ)=HLG[(I2m⊗ℒ1G)Φm]×[I2m⊗W[2nτ,2n(τ+1)]Φnτ]u(0)𝒳(τ)≜Hℒ2Gu(0)𝒳(τ)=ℋ2,iG𝒳(τ),y(3)=HLu(2)x(2)x(1)𝒳(τ-2)=HLG2u(0)ℒ2Gu(0)𝒳(τ)ℒ1Gu(0)𝒳(τ)𝒳(τ-2)=HLG2[(I2m⊗ℒ2G)Φm]×u(0)𝒳(τ)ℒ1Gu(0)𝒳(τ)𝒳(τ-2)=HLG2[(I2m⊗ℒ2G)Φm]×[(I2m+n(τ+1)⊗ℒ1G)Φm+n(τ+1)]×u(0)𝒳(τ)𝒳(τ-2)=HLG2[(I2m⊗ℒ2G)Φm]×[(I2m+n(τ+1)⊗ℒ1G)Φm+n(τ+1)]×[I2m⊗W[2n(τ-1),2n(τ+1)]Φn(τ-1)]u(0)𝒳(τ)≜Hℒ3Gu(0)𝒳(τ)=ℋ3,iG𝒳(τ),⋮y(τ+1)=HLu(τ)x(τ)⋯x(1)𝒳(0)=HLGτu(0)[⋉i=τ1ℒiGu(0)𝒳(τ)]𝒳(0)=HLGτ[(I2m⊗ℒτG)Φm][⋉i=τ-11ℳiG]×[I2m⊗W[2n,2n(τ+1)]Φn]u(0)𝒳(τ)≜Hℒτ+1Gu(0)𝒳(τ)=ℋτ+1,iG𝒳(τ).
For s>τ+1, we can obtain that
(27)y(τ+2)=HLu(τ+1)x(τ+1)⋯x(1)=HLGτ+1u(0)[⋉i=τ+11ℒiGu(0)𝒳(τ)]=HLGτ+1[(I2m⊗ℒτ+1G)Φm]×[⋉i=τ1ℳiG]u(0)𝒳(τ)≜Hℒτ+2Gu(0)𝒳(τ)=ℋτ+2,iG𝒳(τ),y(τ+3)=HLu(τ+2)x(τ+2)⋯x(2)=HLGτ+2u(0)[⋉i=τ+22ℒiGu(0)𝒳(τ)]=HLGτ+2[(I2m⊗ℒτ+2G)Φm]×[⋉i=τ+12ℳiG]u(0)𝒳(τ)≜Hℒτ+3Gu(0)𝒳(τ)=ℋτ+3,iG𝒳(τ),⋮y(s)=HLu(s-1)x(s-1)⋯x(s-τ-1)=HLGs-1u(0)[⋉i=s-2s-τ-1ℒiGu(0)𝒳(τ)]=HLGs-1[(I2m⊗ℒs-1G)Φm]×[⋉i=s-2s-τ-1ℳiG]u(0)𝒳(τ)≜HℒsGu(0)𝒳(τ)=ℋs,iG𝒳(τ).
From the above analysis, and definition of 𝒪1,i,s in (24), we can see that
(28)𝒪1,i,s𝒳(τ)=[y(0)y(1)⋮y(s)].
Since 𝒳(τ)∈Δ2n(τ+1),  𝒪1,i,s𝒳(τ)∈Col(𝒪1,i,s). It implies that 𝒳(τ) is determined uniquely by the outputs y(0),…,y(s) if and only if there exist no similar elements in Col(𝒪1,i,s), or equivalently, there are no equal columns in 𝒪1,i,s, that is, rank(𝒪1,i,s)=2n(τ+1). The proof is completed.Corollary 8.
Consider the temporal Boolean network (16) with control (17). Equations (16) and (17) are observable if and only if there exist a finite time s and i∈{1,2,…,2m} such that rank(𝒪1,i,s)=2n(τ+1).Remark 9.
When the time delayτ=0, then the temporal Boolean control network (16) and (17) become a Boolean control network. In this case, it can be induced from (23) that
(29)ℒsG={L,s=1,LGs-1[(I2m⊗ℒs-1G)Φm],s>1.
Then, the observability of the BCN with input Boolean network controls can be deduced from Theorem 7 and Corollary 8.


### 4.2. Control via Free Boolean Sequence

In the following, the case where the controls are free Boolean sequences is considered. We splitL given in (16) into 2m equal blocks as
(30)L=[L1,L2,…,L2m],
with each Li∈ℒ2n×2n(τ+1),  i=1,2,…,2m. Define a sequence of matrices ℒ~s,is-1,…,i0∈ℒ2n×2n(τ+1),  s∈ℕ+, is-1∈{1,2,…,2m} as (31):
(31)ℒ~s,is-1,…,i0={Li0,s=1,Li1Li0W[2nτ,2n(τ+1)]Φnτ,s=2,Lis-1ℒ~s-1,is-2,…,i0[⋉j=s-21ℳ~j]⋉W[2n(τ-s+2),2n(τ+1)]Φn(τ-s+2),s=3,…,τ+1,Lis-1ℒ~s-1,is-2,…,i0[⋉j=s-2s-τ-1ℳ~j],s>τ+1,
where ℳ~j=I2n(τ+1)⊗ℒ~j,ij-1,…,i0Φn(τ+1), the transition matrices L, G, and H are defined in (16) and (17).Theorem 10.
Consider the temporal Boolean network (16). Assume that the controls are free Boolean sequences with u(l)=δ2mil,l∈ℕ,il∈{1,2,…,2m}. Then, (16) is observable if and only if there exists a finite time s such that rank(𝒪2,s)=2n(τ+1), where
(32)𝒪2,s=[ℋ0GHℒ~1,i0Hℒ~2,i1,i0⋮Hℒ~s,is-1,…,i0].Proof.
Since the controls are free Boolean sequences withu(l)=δ2mil, l∈ℕ, il∈{1,2,…,2m}, from (16) we have
(33)y(1)=Hx(1)=HLu(0)𝒳(τ)=HLi0𝒳(τ)≜Hℒ~1,i0𝒳(τ),y(2)=Hx(2)=HLu(1)x(1)𝒳(τ-1)=HLu(1)Lu(0)𝒳(τ)𝒳(τ-1)=HLu(1)Lu(0)W[2nτ,2n(τ+1)]Φnτ𝒳(τ)=HLi1Li0W[2nτ,2n(τ+1)]Φnτ𝒳(τ)≜Hℒ~2,i1,i0𝒳(τ),y(3)=Hx(3)=HLu(2)x(2)x(1)𝒳(τ-2)=HLu(2)ℒ~2,i1,i0𝒳(τ)ℒ~1,i0𝒳(τ)𝒳(τ-2)=HLi2ℒ~2,i1,i0[(I2n(τ+1)⊗ℒ~1,i0)Φn(τ+1)]×𝒳(τ)𝒳(τ-2)=HLi2ℒ~2,i1,i0[(I2n(τ+1)⊗ℒ~1,i0)Φn(τ+1)]×[W[2n(τ-1),2n(τ+1)]Φn(τ-1)]𝒳(τ)≜Hℒ~3,i2,i1,i0𝒳(τ),⋮y(τ+1)=HLu(τ)x(τ)⋯x(1)𝒳(0)=HLu(τ)[⋉j=τ1ℒ~j,ij-1,…,i0𝒳(τ)]𝒳(0)=HLiτℒ~τ,iτ-1,…,i0[⋉j=τ-11ℳ~j]×W[2n,2n(τ+1)]Φn𝒳(τ)≜Hℒ~τ+1,iτ,…,i0𝒳(τ).
For s>τ+1, we can obtain that
(34)y(τ+2)=HLu(τ+1)x(τ+1)⋯x(1)=HLu(τ+1)[⋉j=τ+11ℒ~j,ij-1,…,i0𝒳(τ)]=HLiτ+1ℒ~τ+1,iτ,…,i0[⋉i=τ1ℳ~j]𝒳(τ)≜Hℒ~τ+2,iτ+1,…,i0𝒳(τ),(35)y(τ+3)=HLu(τ+2)x(τ+2)⋯x(2)=HLu(τ+2)[⋉j=τ+22ℒ~j,ij-1,…,i0𝒳(τ)]=HLiτ+2ℒ~τ+2,iτ+1,…,i0[⋉i=τ+12ℳ~j]𝒳(τ)≜Hℒ~τ+3,iτ+2,…,i0𝒳(τ),⋮(36)y(s)=HLu(s-1)x(s-1)⋯x(s-τ-1)=HLu(s-1)[⋉i=s-2s-τ-1ℒ~j,ij-1,…,i0𝒳(τ)]=HLis-1ℒ~s-1,is-2,…,i0[⋉i=s-2s-τ-1ℳ~j]𝒳(τ)≜Hℒ~s,is-1,…,i0𝒳(τ).
Thus, from (25) and the definition of 𝒪2,s in (32), we can see that
(37)𝒪2,s𝒳(τ)=[y(0)y(1)⋮y(s)].
Similar with the proof of Theorem 7, we conclude that 𝒳(τ) can be determined uniquely by the outputs y(0),…,y(s) if and only if rank(𝒪2,s)=2n(τ+1). The proof is completed.Corollary 11.
Consider the temporal Boolean network (16). The system (16) is observable if and only if there exists a finite time s and a sequence i0,i1,…,is-1∈{1,2,…,2m} such that rank(𝒪2,s)=2n(τ+1).Remark 12.
As a special case, whenτ=0, then from the proof of Theorem 10, we have ℋ0G=H, and
(38)ℒ~1,i0=Li0,ℒ~s+1,is,…,i0=Lis+1ℒ~s,is-1,…,i0,s>0.
Then, Corollary 11 is equivalent with Theorem  26 in [8] for the observability of BCNs.Remark 13.
For Theorems7 and 10, when τ=1, the third explicit expressions of ℒsG in (23) and ℒ~s,is-1,…,i0 in (31) for s=3,…,τ+1 should be omitted.


## 4.1. Observability of Input Boolean Networks

We first consider the case that controls satisfy certain logical rules as (17). Define a sequence of matrices ℒsG∈ℒ2n×2m+n(τ+1) as (23):
(23)ℒsG≔{L,s=1,LG[(I2m⊗ℒ1G)Φm][I2m⊗W2nτ,2n(τ+1)Φn(τ)],L,s=2,LGs-1[(I2m⊗ℒs-1G)Φm][⋉i=s-21ℳiG]⋉[I2m⊗W[2n(τ-s+2),2n(τ+1)]Φn(τ-s+2)],L,s=3,…,τ+1,LGs-1[(I2m⊗ℒs-1G)Φm][⋉i=s-2s-τ-1ℳiG],L,s>τ+1,
where ℳiG=I2m+n(τ+1)⊗ℒiGΦm+n(τ+1) and ℋ0G=HEn,τW[2n,2nτ],  ℋsG=HℒsG,s∈ℕ+, and the transition matrices L, G, and H are defined in (16) and (17). Furthermore, we split ℋjG∈ℒ2p×2m+n(τ+1), j∈ℕ+, into 2m equal blocks as ℋjG=[ℋj,1G,ℋj,2G,…,ℋj,2mG] with each ℋj,iG∈ℒ2p×2n(τ+1), i=1,2,…,2m, j∈ℕ+.Theorem 7.
Consider the temporal Boolean network (16) with control (17). Assume that u(0)=δ2mi,  i∈{1,2,…,2m}. Then, (16) and (17) are observable if and only if there exists a finite time s such that rank(𝒪1,i,s)=2n(τ+1), where
(24)𝒪1,i,s=[ℋ0Gℋ1,iG⋮ℋs,iG].Proof.
Firstly, from Lemma6 and (16),
(25)y(0)=Hx(0)=HEn,τW[2n,2nτ]𝒳(τ)≜ℋ0G𝒳(τ).
Since u(0)=δ2mi, we have from (18) that
(26)y(1)=Hx(1)=HLu(0)𝒳(τ)≜Hℒ1Gu(0)𝒳(τ)=ℋ1,iG𝒳(τ),y(2)=HLu(1)x(1)𝒳(τ-1)=HLGu(0)ℒ1Gu(0)𝒳(τ)𝒳(τ-1)=HLG[(I2m⊗ℒ1G)Φm]u(0)𝒳(τ)𝒳(τ-1)=HLG[(I2m⊗ℒ1G)Φm]u(0)W[2nτ,2n(τ+1)]Φnτ𝒳(τ)=HLG[(I2m⊗ℒ1G)Φm]×[I2m⊗W[2nτ,2n(τ+1)]Φnτ]u(0)𝒳(τ)≜Hℒ2Gu(0)𝒳(τ)=ℋ2,iG𝒳(τ),y(3)=HLu(2)x(2)x(1)𝒳(τ-2)=HLG2u(0)ℒ2Gu(0)𝒳(τ)ℒ1Gu(0)𝒳(τ)𝒳(τ-2)=HLG2[(I2m⊗ℒ2G)Φm]×u(0)𝒳(τ)ℒ1Gu(0)𝒳(τ)𝒳(τ-2)=HLG2[(I2m⊗ℒ2G)Φm]×[(I2m+n(τ+1)⊗ℒ1G)Φm+n(τ+1)]×u(0)𝒳(τ)𝒳(τ-2)=HLG2[(I2m⊗ℒ2G)Φm]×[(I2m+n(τ+1)⊗ℒ1G)Φm+n(τ+1)]×[I2m⊗W[2n(τ-1),2n(τ+1)]Φn(τ-1)]u(0)𝒳(τ)≜Hℒ3Gu(0)𝒳(τ)=ℋ3,iG𝒳(τ),⋮y(τ+1)=HLu(τ)x(τ)⋯x(1)𝒳(0)=HLGτu(0)[⋉i=τ1ℒiGu(0)𝒳(τ)]𝒳(0)=HLGτ[(I2m⊗ℒτG)Φm][⋉i=τ-11ℳiG]×[I2m⊗W[2n,2n(τ+1)]Φn]u(0)𝒳(τ)≜Hℒτ+1Gu(0)𝒳(τ)=ℋτ+1,iG𝒳(τ).
For s>τ+1, we can obtain that
(27)y(τ+2)=HLu(τ+1)x(τ+1)⋯x(1)=HLGτ+1u(0)[⋉i=τ+11ℒiGu(0)𝒳(τ)]=HLGτ+1[(I2m⊗ℒτ+1G)Φm]×[⋉i=τ1ℳiG]u(0)𝒳(τ)≜Hℒτ+2Gu(0)𝒳(τ)=ℋτ+2,iG𝒳(τ),y(τ+3)=HLu(τ+2)x(τ+2)⋯x(2)=HLGτ+2u(0)[⋉i=τ+22ℒiGu(0)𝒳(τ)]=HLGτ+2[(I2m⊗ℒτ+2G)Φm]×[⋉i=τ+12ℳiG]u(0)𝒳(τ)≜Hℒτ+3Gu(0)𝒳(τ)=ℋτ+3,iG𝒳(τ),⋮y(s)=HLu(s-1)x(s-1)⋯x(s-τ-1)=HLGs-1u(0)[⋉i=s-2s-τ-1ℒiGu(0)𝒳(τ)]=HLGs-1[(I2m⊗ℒs-1G)Φm]×[⋉i=s-2s-τ-1ℳiG]u(0)𝒳(τ)≜HℒsGu(0)𝒳(τ)=ℋs,iG𝒳(τ).
From the above analysis, and definition of 𝒪1,i,s in (24), we can see that
(28)𝒪1,i,s𝒳(τ)=[y(0)y(1)⋮y(s)].
Since 𝒳(τ)∈Δ2n(τ+1),  𝒪1,i,s𝒳(τ)∈Col(𝒪1,i,s). It implies that 𝒳(τ) is determined uniquely by the outputs y(0),…,y(s) if and only if there exist no similar elements in Col(𝒪1,i,s), or equivalently, there are no equal columns in 𝒪1,i,s, that is, rank(𝒪1,i,s)=2n(τ+1). The proof is completed.Corollary 8.
Consider the temporal Boolean network (16) with control (17). Equations (16) and (17) are observable if and only if there exist a finite time s and i∈{1,2,…,2m} such that rank(𝒪1,i,s)=2n(τ+1).Remark 9.
When the time delayτ=0, then the temporal Boolean control network (16) and (17) become a Boolean control network. In this case, it can be induced from (23) that
(29)ℒsG={L,s=1,LGs-1[(I2m⊗ℒs-1G)Φm],s>1.
Then, the observability of the BCN with input Boolean network controls can be deduced from Theorem 7 and Corollary 8.


## 4.2. Control via Free Boolean Sequence

In the following, the case where the controls are free Boolean sequences is considered. We splitL given in (16) into 2m equal blocks as
(30)L=[L1,L2,…,L2m],
with each Li∈ℒ2n×2n(τ+1),  i=1,2,…,2m. Define a sequence of matrices ℒ~s,is-1,…,i0∈ℒ2n×2n(τ+1),  s∈ℕ+, is-1∈{1,2,…,2m} as (31):
(31)ℒ~s,is-1,…,i0={Li0,s=1,Li1Li0W[2nτ,2n(τ+1)]Φnτ,s=2,Lis-1ℒ~s-1,is-2,…,i0[⋉j=s-21ℳ~j]⋉W[2n(τ-s+2),2n(τ+1)]Φn(τ-s+2),s=3,…,τ+1,Lis-1ℒ~s-1,is-2,…,i0[⋉j=s-2s-τ-1ℳ~j],s>τ+1,
where ℳ~j=I2n(τ+1)⊗ℒ~j,ij-1,…,i0Φn(τ+1), the transition matrices L, G, and H are defined in (16) and (17).Theorem 10.
Consider the temporal Boolean network (16). Assume that the controls are free Boolean sequences with u(l)=δ2mil,l∈ℕ,il∈{1,2,…,2m}. Then, (16) is observable if and only if there exists a finite time s such that rank(𝒪2,s)=2n(τ+1), where
(32)𝒪2,s=[ℋ0GHℒ~1,i0Hℒ~2,i1,i0⋮Hℒ~s,is-1,…,i0].Proof.
Since the controls are free Boolean sequences withu(l)=δ2mil, l∈ℕ, il∈{1,2,…,2m}, from (16) we have
(33)y(1)=Hx(1)=HLu(0)𝒳(τ)=HLi0𝒳(τ)≜Hℒ~1,i0𝒳(τ),y(2)=Hx(2)=HLu(1)x(1)𝒳(τ-1)=HLu(1)Lu(0)𝒳(τ)𝒳(τ-1)=HLu(1)Lu(0)W[2nτ,2n(τ+1)]Φnτ𝒳(τ)=HLi1Li0W[2nτ,2n(τ+1)]Φnτ𝒳(τ)≜Hℒ~2,i1,i0𝒳(τ),y(3)=Hx(3)=HLu(2)x(2)x(1)𝒳(τ-2)=HLu(2)ℒ~2,i1,i0𝒳(τ)ℒ~1,i0𝒳(τ)𝒳(τ-2)=HLi2ℒ~2,i1,i0[(I2n(τ+1)⊗ℒ~1,i0)Φn(τ+1)]×𝒳(τ)𝒳(τ-2)=HLi2ℒ~2,i1,i0[(I2n(τ+1)⊗ℒ~1,i0)Φn(τ+1)]×[W[2n(τ-1),2n(τ+1)]Φn(τ-1)]𝒳(τ)≜Hℒ~3,i2,i1,i0𝒳(τ),⋮y(τ+1)=HLu(τ)x(τ)⋯x(1)𝒳(0)=HLu(τ)[⋉j=τ1ℒ~j,ij-1,…,i0𝒳(τ)]𝒳(0)=HLiτℒ~τ,iτ-1,…,i0[⋉j=τ-11ℳ~j]×W[2n,2n(τ+1)]Φn𝒳(τ)≜Hℒ~τ+1,iτ,…,i0𝒳(τ).
For s>τ+1, we can obtain that
(34)y(τ+2)=HLu(τ+1)x(τ+1)⋯x(1)=HLu(τ+1)[⋉j=τ+11ℒ~j,ij-1,…,i0𝒳(τ)]=HLiτ+1ℒ~τ+1,iτ,…,i0[⋉i=τ1ℳ~j]𝒳(τ)≜Hℒ~τ+2,iτ+1,…,i0𝒳(τ),(35)y(τ+3)=HLu(τ+2)x(τ+2)⋯x(2)=HLu(τ+2)[⋉j=τ+22ℒ~j,ij-1,…,i0𝒳(τ)]=HLiτ+2ℒ~τ+2,iτ+1,…,i0[⋉i=τ+12ℳ~j]𝒳(τ)≜Hℒ~τ+3,iτ+2,…,i0𝒳(τ),⋮(36)y(s)=HLu(s-1)x(s-1)⋯x(s-τ-1)=HLu(s-1)[⋉i=s-2s-τ-1ℒ~j,ij-1,…,i0𝒳(τ)]=HLis-1ℒ~s-1,is-2,…,i0[⋉i=s-2s-τ-1ℳ~j]𝒳(τ)≜Hℒ~s,is-1,…,i0𝒳(τ).
Thus, from (25) and the definition of 𝒪2,s in (32), we can see that
(37)𝒪2,s𝒳(τ)=[y(0)y(1)⋮y(s)].
Similar with the proof of Theorem 7, we conclude that 𝒳(τ) can be determined uniquely by the outputs y(0),…,y(s) if and only if rank(𝒪2,s)=2n(τ+1). The proof is completed.Corollary 11.
Consider the temporal Boolean network (16). The system (16) is observable if and only if there exists a finite time s and a sequence i0,i1,…,is-1∈{1,2,…,2m} such that rank(𝒪2,s)=2n(τ+1).Remark 12.
As a special case, whenτ=0, then from the proof of Theorem 10, we have ℋ0G=H, and
(38)ℒ~1,i0=Li0,ℒ~s+1,is,…,i0=Lis+1ℒ~s,is-1,…,i0,s>0.
Then, Corollary 11 is equivalent with Theorem  26 in [8] for the observability of BCNs.Remark 13.
For Theorems7 and 10, when τ=1, the third explicit expressions of ℒsG in (23) and ℒ~s,is-1,…,i0 in (31) for s=3,…,τ+1 should be omitted.


## 5. An Example

Given logical argumentsP,Q∈Δ, we have the following structure matrices for the fundamental logical functions: ¬P=MnP, P∨Q=MdPQ, P∧Q=McPQ, P→Q=MiPQ, P↔Q=MePQ, where Mn=δ2[2,1], Md=δ2[1,1,1,2], Mc=δ2[1,2,2,2], Mi=δ2[1,2,1,1], Me=δ2[1,2,2,1].Example 14.
Consider the following temporal Boolean network:(39)A(t+1)=u(t)∨A(t)⟶A(t-1)⟷A(t-2),y(t)=¬A(t).
Let x(t)=A(t), it is easy to get H=Mn, L=MeMiMd, and τ=2.
(A) When the controls satisfy the logical rule(40)u(t+1)=¬u(t),
then the transition matrix G=Mn. Now, assume that u(0)=δ21, by calculation, we have
(41)ℋ0G=δ2[2,2,2,2,1,1,1,1],ℋ1,1G=δ2[2,1,1,2,2,1,1,2],ℋ2,1G=δ2[2,2,2,2,1,2,2,1],ℋ3,1G=δ2[2,1,1,2,2,1,1,2],ℋ4,1G=δ2[2,1,1,2,1,1,1,1],ℋ5,1G=δ2[2,1,1,2,1,1,1,1],⋮𝒪1,1,s=[ℋ0Gℋ1,1Gℋ2,1Gℋ3,1Gℋ4,1Gℋ5,1G⋮]=[222211112112211222221221211221122112111121121111⋮].
Hence, for any s>0, there are only 4 linearly independent columns, which means that rank(𝒪1,1,s)<2n(τ+1)=8 for any s>0, and the system is not observable from Theorem 7. Similarly, if u(0)=δ22, we have the same conclusion.
(B) When controls are free sequences withu(0)=δ21, u(i)=δ22, i=1,2,…. By calculation, it leads to
(42)ℋ0G=δ2[2,2,2,2,1,1,1,1],Hℒ~1,1=δ2[2,1,1,2,2,1,1,2],Hℒ~2,2,1=δ2[2,2,1,1,1,2,1,2],Hℒ~3,2,2,1=δ2[2,1,2,2,1,2,1,1],Hℒ~4,2,2,2,1=δ2[2,1,2,1,2,1,1,2],⋮
and hence,
(43)𝒪2,s=[ℋ0GHℒ~1,1Hℒ~2,2,1Hℒ~3,2,2,1Hℒ~4,2,2,2,1⋮]=[2222111121122112221112122122121121212112⋮].
When s=2, it is enough to see that there are no equal columns in 𝒪2,2. So, the system is observable by Theorem 10.
From cases (A) and (B), it is easy to notice that the selection of controls is very important for the observability of the temporal Boolean control network.


## 6. Conclusion

In this brief paper, necessary and sufficient conditions for the observability of temporal Boolean control networks have been derived. By using semi-tensor product of matrices and the matrix expression of logic, we have converted the temporal Boolean control networks into discrete systems with time delays. Moreover, the observability has been investigated via two different kinds of controls. Finally, an example has been given to show the efficiency of the proposed results.



---

*Source: 631639-2013-05-07.xml*