Morgan’s problem of Boolean control networks

Shihua FU,Yuanhua WANG,Daizhan CHENG,Jiangbo LIU

1.School of Control Science and Engineering,Shandong University,Jinan Shandong 250061,China;

2.School of Management Science and Engineering,Shandong Normal University,Jinan Shandong 250014,China;

3.Department of Computer Science and Information Systems,Bradley University,Peoria,IL,61625,U.S.A.

Morgan’s problem of Boolean control networks

Shihua FU1,Yuanhua WANG2,Daizhan CHENG1,Jiangbo LIU3?

1.School of Control Science and Engineering,Shandong University,Jinan Shandong 250061,China;

2.School of Management Science and Engineering,Shandong Normal University,Jinan Shandong 250014,China;

3.Department of Computer Science and Information Systems,Bradley University,Peoria,IL,61625,U.S.A.

This paper investigates the Morgan’s problem of Boolean control networks.Based on the matrix expression of logical functions,two key steps are proposed to solve the problem.First,the Boolean control network is converted into an outputdecomposed form by constructing a set of consistent output-friendly subspaces,and a necessary and sufficient condition for the existence of the consistent output-friendly subspaces is obtained.Secondly,a type of state feedback controllers are designed to solve the Morgan’s problem if it is solvable.By solving a set of matrix equations,a necessary and sufficient condition for converting an output-decomposed form to an input-output decomposed form is given,and by verifying the output controllability matrix,the solvability of Morgan’s problem is obtained.

Boolean control network,Morgan’s problem,regular subspace,y-friendly subspace,semi-tensor product of matrices

1 Introduction

The Boolean network,which is first introduced by Kauffman[1],is known as a useful model to describe and simulate the behavior of genetic regulatory networks.Using semi-tensor product method and the matrix expression of logical functions,the dynamics of a Boolean network can be converted into a linear discrete-time system[2].And in recent decades,many classical problems for Boolean networks were solved by using this method,including stability and stabilization[3],controllability[4],observability[5],identification[6],optimal control[7],output tracking problem[8],weighted l1-gain problem[9]and so on.

In modern control theory the Morgan’s problem is one of the most famous problems for both linear and non-linear control systems.Consider a linear control system

where x∈Rnis the set of state variable,u∈Rmis the control,y∈Rpis the output.Assume m≥p.The Morgan’s problem means to find a partition of u as u={u1,...,up},such that each uicontrols yiwithout affecting yj,j≠i[10].When m=p,the problem has been completely solved by providing a necessary and sufficient condition as the decoupling matrix is nonsingular[11].Unfortunately,as for the general case,it is still open till now.The situation of the nonlinear case is similar[12,13].

As for the Boolean control networks,it is obvious that the input-output decomposition is also a theoretically interesting and practically useful problem.But because of certain difficulties,the problem has not been discussed much.A closely related but easier one is the disturbance decoupling problem,which has been discussed by several authors[14,15].The system decomposition with respect to inputs for Boolean control networks has been investigated by[16].A recent work on input-output decomposition of Boolean networks is presented in[17],which considers the case of m=p and does not use the coordinate transformation.Besides,[17]just proposed a method to evaluate whether a Boolean control network was input-output decoupled or not,and didn’t give a controller design algorithm to make a given Boolean control network input-output decoupled.

This paper considers the input-output decoupling of Boolean control networks under more general case,where m≥p.Moreover,similar to the nonlinear system[18],a coordinate transformation and state feedback controls are allowed.

For the statement ease,a list of notations is presented as follows:

1)Mm×n:the set of m × n real matrices.

2)D:={0,1}.

3)δin:the ith column of the identity matrix In.

4)Δn:={δin|i=1,...,n}.

6)0p×q:a p × q matrix with zero entries.

7)Coli(M)(Rowi(M)):the ith column(row)of M.

8)A matrix L ∈ Mm×nis called a logical matrix if the columns of L are of the form of δkm.That is,Col(L)? Δm.Denote by Lm×nthe set of m × n logical matrixes.

9)If L ∈ Ln×r,by definition it can be expressed asFor the sake of compactness,it is briefly denoted as L=δn[i1,i2,...,ir].

10)A matrix L ∈ Mm×nis called a Boolean matrix,if all its entries are either 0 or 1.Bm×n:the set of m × n Boolean matrices(Bn:the set of n dimensional Boolean vectors).

11)Let{x1,...,xk}be a set of logical variables.F?(x1,...,xk)is the set of logical functions of{x1,...,xk}.

12)Let A ∈ Mm×kand B ∈ Mn×k.Then A?B ∈ Mmn×kis the Khatri-Rao product of A and B[19].

The rest of this paper is organized as follows:Section2 presents some necessary preliminaries.The Morgan’s problem formulation is given in Section3.In Section4,a necessary and sufficient condition for the existence of the output-decomposed form is given,and the form is obtained by constructing a set of consistent outputfriendly subspaces.Section5 proposes a controller design method to solve the input-output decoupling problem.Based on the input-output decomposition form,the solvable condition of the Morgan’s problem is presented in Section6.Section7 is a brief conclusion.

2 Preliminaries

This section presents some related concepts about semi-tensor product of matrices,state space of Boolean control networks and its subspaces.We refer to[2,14]for details.

Def i nition 1[2]Let M ∈ Mm×nand N ∈ Mp×q,and t=lcm{n,p}be the least common multiple of n and p.The semi-tensor product of M and N is defined as

where?is the Kronecker product.

Throughout this paper,we assume the product of two matrices is the semi-tensor product,and the symbolis omitted without the confusion.

Lemma 1[2] Consider a logical mapping f:Δn→Δk.There exists a unique matrix Mf∈ L2k×2n,called the structure matrix of f,such that

Consider a Boolean control network(BCN)

where xi(i=1,...,n),uj(j=1,...,m)and yk(k=1,...,p)are logical variables.That is,they can take values 0 or 1.

Identify 1～ δ12and 0～ δ22.Using Lemma 1,the algebraic expression of(2)can be described as

Def i nition 2[14] Consider the BCN(2).

1)The state space of(2)is described as

that is,the state space is the set of logical functions of{x1,x2,...,xn}.

2)Let{y1,...,yk}?X.A subspace Y?X,generated by{y1,...,yk},is

Given a subspace Y=F?(y1,...,yk)? X.Since yi,i=1,...,k,are functions of{x1,...,xn},we can use the vector expression of yiand express yiin algebraic form as

where x=ni=1xi,and Gi∈ L2×2n,i=1,...,k.Setting y=kj=1yj,then we have

where G=G1?...?Gk.Then G is called the structure matrix of the subspace Y.

Definition 3[14]Let{z1,...,zn}?X and Z=F?(z1,...,zn).Then Ψ :x → z is called a coordinate transformation(or coordinate change)if Ψ is one to one and onto.

Proposition 1[14] Let z=and the structure matrix of Z be T.That is z=Tx.Then Ψ :x → z is a coordinate transformation,if and only if,T ∈ L2n×2nis nonsingular.

Def i nition 4[14]Let Z=F?(z1,...,zk)? X.Z is called a regular subspace if there exists a set of logical variables{zk+1,...,zn}? X such that Ψ :(x1,...,xn)→(z1,...,zn)is a coordinate transformation.

Proposition 2[14]Let Z=F?(z1,...,zk)? X,and its structure matrix be T0.That is,

where z=kj=1zj.Then Z is a regular subspace,if and only if the elements of T0satisfy

Example 1Consider X=F?(x1,x2,x3)and its subspace Z=F?(z1,z2)? X.

1)Assume z1=x1∧x3,z2=x3.Then z=Gx,where

Z is not a regular subspace.

2)Assume z1=x1?x3,z2=x3.Then z=Gx,where

Z is a regular subspace.

Definition 5[14]Let Y?X be a subspace and Z?X a regular subspace.If Y?Z,then Z is called a Y-friendly subspace.If Z is the smallest size of Y-friendly subspace,it is called a minimum Y-friendly subspace.

Lemma 2[14] Assume y has its algebraic form y=Hx,and

1)There is a Y-friendly subspace of dimension r,iff nj,j=1,2,...,2phave a common factor 2n?r.

2)Assume 2n?ris the largest common factor,which has the form2s,ofnj,j=1,2,...,2p.Then the minimum Y-friendly subspace is of dimension r.

Proposition 3[2] Define a power reducing matrix

Let x∈Δn,then

3 Problem formulation

Definition 6Consider BCN(2)and assume m≥p.The input-output decomposition problem is:finding a coordinate transformation x→z and a state feedback

where K ∈ L2p×2n+p,such that(2)can be converted into an input-output decomposed form

where z=(z0,z1,...,zp)is a partition of z=(z1,z2,...,zn),v(t)=(v1(t),v2(t),...,vp(t)),and vi(t)∈D,j=1,...,p are the reference inputs.Moreover,if vjcan completely control yj,the problem is called the Morgan’s problem of Boolean control networks.

System(7)motivates the following concept.

Definition 7Let

be a set of regular subspaces of X.{Zj|j=1,...,p}is called a set of consistent regular subspaces,if there exists z0,such that{z0,z1,...,zp}form a new coordinate frame.

The following proposition follows from Definition 7 immediately.

Proposition 4{Zj|j=1,...,p}is called a set of consistent regular subspaces,if and only if,

is a structure matrix of a regular subspace.Precisely speaking,T satisfies Proposition 2.

As a corollary,we have the following necessary condition.

Corollary 1Assume the input-output decomposition problem is solvable.Then there exists a set of consistent regular subspaces Zj|j=1,...,p,such that Zjis yj-friendly,j=1,...,p.Such a set of yj-friendly consistent regular subspaces is called a consistent yfriendly subspaces.

From Definition 6,one sees that the Morgan’s problem can be solved in two steps:i)finding consistent regular subspaces Zjsuch that yj∈Zj,j=1,2,...,p;ii)designing a controller,such that zj(t+1)is a function of zj(t)and vj(t),moreover,vjcan completely control yj.

4 Output decomposition

This section devotes to finding a set of consistent yjfriendly subspaces of system(2).

First,we give two lemmas,which will be used for the deduction.

Lemma 3Let A ∈ Mm×n,B ∈ Mn×s,C ∈ Mp×q,D ∈Mq×s.Then

Note that for two column vectors X and Y we have

Lemma 4Let xi∈ Δki,i=1,...,n.Then

ProofA straightforward calculation shows that

Under a new coordinate frame z,if system(2)can be expressed as

where zj,j=1,...,p are consistent regular subspaces,then we call(8)the output-decomposed form of(2).

Next,we should determine the existence of the consistent output-friendly subspaces.

Since the output yj∈X,j=1,2,...,p,we can express it in algebraic form as

Assume Hjhas njrcolumns which are equal to δr2,r=1,2,then,njrcan be calculated by

In the following,we give an algorithm for constructing the minimum yj-friendly subspace.We just need to construct a logical matrix,such that we can find a logical matrix,satisfying

where zj(t)=Tjx(t)is a minimum yj-friendly subspace.

.Step 1:Calculate the two rows of Hj,where

.Step 2:Split Rowr(Hj)into mjrblocks as

It is easy to check that Hj=GjTj.

By Lemma 4,we can recover zji,i=1,2,...,njfrom zj.We have

is a set of minimum yj-friendly subspaces.

Remark 1It is worth noting that for any subspace yj∈X,j=1,2,...,p,the minimum yj-friendly subspace is not unique.

We have the following theorem.

Theorem 1Consider BCN(2)with outputs yj,j=1,2,...,p,there exist consistent yj-friendly subspaces,iff(11)is a set of consistent regular subspaces.

Proof(Necessity)Assume

is a set of minimum consistent yj-friendly subspaces.Denotethen there exist matrices G′j∈and T′j∈such that

Since(11)are a set of yj-friendly subspaces,we have

Let y(t)=pj=1yj(t).Using Lemma 3,we have

where G=G1?G2?...?Gpand T=T1?T2?...?Tp.Similarly,we have

where G′=G′1? G′2? ...? G′p.

From the form of Gjand G′j,j=1,2,...,p,there exist permutation matrices,j=1,2,...,p such that

Since G′T′=H=GT=andit is obvious that the matrix T sat-By Propositions 2 and 4,we get that(11)are a set of consistent regular subspaces.The conclusion of necessity follows.

The sufficiency is obvious.

Now assume zj,j=1,...,p are consistent regular subspaces.Then we can find z0and T0,suchthatz={z0,z1,...,zp}is a new coordinate frame,where

DenoteT=T0?T1?...?Tp.Then,under coordinate frame z,system(2)can be expressed as

where z(t)=pj=0zj(t).

Example 2Consider the following system:

Then it is easy to figure out that a minimum y1-friendly subspace is

and a minimum y2-friendly subspace is

It is ready to verify that{z1,z2}is a regular subspace,and we may choose

such that z={z0,z1,z2}becomes a new coordinate frame.Moreover,under z,system(13)becomes its output-decomposed form as

wherez0(t)=z1(t),z1(t)=(z2(t),z3(t)),andz2(t)=z4(t).

5 Input-output decomposition

In this section we consider how to convert an outputdecomposed form into an input-output decomposed form.

Assume the algebraic form of state dynamics of(8)is

where zj,j=1,...,p is a set of consistent regular subspaces.The state feedback control used for the inputoutput decomposition is

where K ∈ L2m×2n+p.

The input-output decomposition problem is:find,if possible,a state feedback control(16)such that the closed form(8)of system(2)can be expressed into an input-output decomposed form as

We call(17)the input-output decomposed form of(2).

Plugging(16)into(15)yields

where Pj∈ L2nj×2nj+1can be chosen freely and

Summarizing the above argument,we have the following result:

Theorem 2An output-decomposed system(8)is convertible into an input-output decomposed form by a state feedback control,if and only if,there exist K ∈ L2m×2n+m,Pj∈ L2nj×2nj+1,j=1,...,p,such that

where Ξjand Θjare defined in(19).

Example 3Recall Example 2 again.According to Theorem 2,system(14)is input-output decomposable,if and only if,there exist K ∈ L22×26,P1∈ L22×23,P2∈L21×22such that

There is a standard procedure to calculate the algebraic form of(14),we have

We can choose P1and P2as

and

Then we can check that the following K is a solution of(21):

By Lemma 4,we get that ui(t)can be calculated as follows:

where K1=(I2?1T2)K and K2=(1T2?I2)K.

Using K1and K2,we can construct the state feedback control as

Then the closed-loop form of(14)becomes

It is obvious that(23)is an input-output decomposed form.

Next,we should like to convert(20)into an integrated form,which provides a set of linear algebraic equations.

Multiplying the equations in(18)together yields

where M=M1?M2?...?Mp.Define

Using Lemmas 3 and 4,we have the equation

where Φ ∈ M2p×2p?1and Ψ ∈ M2p?1×2n+p.Then we have the following result:

Corollary 2Consider the output-decomposed system(15).If there exist Φ ∈ M2p×2p?1and Ψ ∈ M2p?1×2n+psuch that

then there exists a feedback control as shown in(16)such that the closed form of(15)becomes an inputoutput decomposed form.

Remark 2Equation(26)is a linear equation about Φ and Ψ ,where Φ and Ψ are independent unknowns.Hence,to solve the input-output decomposition problem,we can solve the linear equations deduced from(26).

6 Morgan’s problem

6.1 Output controllability

Definition 8Consider system(2)with its algebraic expression(3).

1)ydis said to be reachable,if for any x(0)there exists a time T＞0 and a control sequence u(0),u(1),...,u(T?1)such that driven by this sequence of controls the trajectory will reach a terminal state x(T)such that yd=Hx(T).

2)System(2)is said to be output controllable,if each y is reachable.

Split L as

where Li∈ L2n×2n.Then we define

and define the controllability matrix of(2)as

where M(i)is the Boolean matrix product of M(i.e.,a+b=a∨b,a×b=ab).C is called the controllability matrix and we have the following result about the controllability of(2)[2].

Theorem 3Consider system(2).

1)The system is reachable from x(0)=to x(T)=i.e.,there exists T＞0 and a sequence of controls as in Definition 8 such that the system trajectory can be driven fromif and only if Ci,j=1;

2)The system is reachable tofrom any x(0),if and only if

3)The system is controllable,i.e.,from any x(0)to any x(T),if and only if

Using controllability matrix C,we can construct an output controllability matrix as

where CYis the Boolean matrix product of H and C,and H is the output structure matrix(see(3)).

Then the following result is an immediate consequence of Definition 8.

Theorem 4Consider system(2).

2)The system is output controllable,if and only if,

6.2 Solution to Morgan’s problem

Consider the Morgan’s problem.Since each yjcan be completely controlled by vj,it is clear that the overall system should be output controllable.Hence we have the following necessary condition.

Proposition 5Consider system(2).If the Morgan’s problem is solvable,then the system is output controllable.

Then the following result is obvious.

Theorem 5Consider system(2).The Morgan’s problem is solvable,if

1)there exist a coordinate transformation z=z(x)and a state feed u=g(v,x),such that the system can be converted into an input-output decomposed form(17);

2)each subsystem

j=1,...,m is output controllable.

By(12)and(18),we know the algebraic form of each subsystem can be expressed as

where Cyjis the Boolean matrix product of Gjand Czj.

Example4Considersystem(23).Lettingz1=z2z3and z2=z4,we can obtain the algebraic form of the two subsystems as

where P1= δ4[1 1 2 3 4 4 4 4]and P2= δ2[1 2 2 1].

A simple calculation shows that

where G1=δ2[1 2 2 2],G2=I2.

that is,the two systems are all output controllable.Thus,the Morgan’s problem of system(13)is solved.

Remark 3By Theorem 5,we know the output controllability of each subsystem(29)depends completely on the matrices Gjand Pj,j=1,2,...,p.Since Gjis conformed in(10)and Pjcan be chosen freely,thus,to guarantee the solvability of the Morgan’s problem,we should choose the kind of Pjwhich can make subsystem zjoutput controllable.Once Pjis conformed,the Morgan’s problem is converted into solving the matrix equation(25).

7 Conclusions

In this paper we have investigated the Morgan’s problem of the Boolean control networks.First,by constructing the output-friendly subspaces,a necessary and sufficient condition for the existence of the outputdecomposed form of a Boolean control network has been presented.Furthermore,the method to converted a Boolean control network into its output-decomposed form has been given.Second,by solving a set of matrix equations,a type of state feedback controllers have been obtained to solve the input-output decoupling problem if it is solvable.Moreover,by constructing the output controllability matrices for each subsystem,the solvability of Morgan’s problem has been converted to verifying whether there exists a solution of(20)which satisfies(31).Since the set of solutions of(20)is finite,the verification is executable.

[1]S.A.Kauffman.Metabolic stability and epigenesis in randomly constructed genetic nets.Journal of Theoretical Biology,1969,22(3):437–467.

[2]D.Cheng,H.Qi,Z.Li.Analysis and Control of Boolean Networks–A Semi-tensor Product Approach.London:Springer,2011.

[3]D.Cheng,H.Qi,Z.Li,et al.Stability and stabilization of Boolean networks.International Journal of Robust and Nonlinear Control,2011,21(2):134–156.

[4]D.Cheng,H.Qi.Controllability and observability of Boolean control networks.Automatica,2009,45(7):1659–1667.

[5]D.Laschov,M.Margaliot,G.Even.Observability of Boolean networks:A graph-theoretic approach.Automatica,2013,49(8):2351–2362.

[6]D.Cheng,Y.Zhao.Identification of Boolean control networks.Automatica,2011,47(4):702–710.

[7]E.Fornasini,M.E.Valcher.Optimal control of Boolean control networks.IEEE Transactions on Automatic Control,2014,59(5):1258–1270.

[8]H.Li,Y.Wang.Output tracking of switched Boolean networks underopen-loop/closed-loop switching signals.Nonlinear Analysis:Hybrid Systems,2016,22:137–146.

[9]M.Meng,J.Lam,J.Feng,et al.l1-gain analysis and model reduction problem for Boolean control networks.Information Sciences,2016,348:68–83.

[10]B.Morgan.The synthesis of linear multivariable systems by statevariable feedback.IEEE Transactions on Automatic Control,1964,9(4):405–411.

[11]W.M.Wonham.Linear Multivariable Control.Berlin:Springer,1974.

[12]A.Glumineau,C.H.Moog.Nonlinear Morgan’s problem:Case of(p+1)inputs and p outputs.IEEE transactions on Automatic Control,1992,37(7):1067–1072.

[13]H.Nijmeijer.Feedback decomposition of nonlinear control systems.IEEE Transactions on Automatic Control,1983,28(8):861–862.

[14]D.Cheng.Disturbance decoupling of Boolean control networks.IEEE Transactions on Automatic Control,2011,56(1):2–10.

[15]M.Yang,R.Li,T.Chu.Controller design for disturbance decoupling of Boolean control networks.Automatica,2013,49(1):273–277.

[16]Y.Zou,J.Zhu.System decomposition with respect to inputs for Boolean control networks.Automatica,2014,50(4):1304–1309.

[17]M.E.Valcher.Input/output decoupling of Boolean control networks.IET Control Theory and Applications,2017,11(13):2081–2088.

[18]W.Respondek.On decomposition of nonlinear control systems.Systems&Control Letters,1982,1(5):301–308.

[19]D.Cheng,H.Qi,Y.Zhao.An Introduction to Semi-tensor Product of Matrices and Its Applications.Singapore:World Scientific,2012.

25 May 2017;revised 22 September 2017;accepted 25 September 2017

DOIhttps://doi.org/10.1007/s11768-017-7068-z

?Corresponding author.

E-mail:jiangbo@bradley.edu.Tel.:1-309-6772386.

This paper is dedicated to Professor T.J.Tarn on the occasion of his 80th birthday.

This work was supported by the National Natural Science Foundation of China(No.61333001).

?2017 South China University of Technology,Academy of Mathematics and Systems Science,CAS,and Springer-Verlag GmbH Germany

Shihua FUreceived her M.Sc.degree from the Department of Mathematics,Liaocheng University,Liaocheng,China,in 2014.Since 2014 she has been pursuing her Ph.D.degree at the School of Control Science and Engineering,Shandong University.Her research interests include game theory,logical dynamic systems.E-mail:fush_shanda@163.com.

Yuanhua WANGreceived her B.Sc.degree and M.Sc.degree from the School of Control Science and Engineering,Shandong University,Jinan,China,in 2004 and 2007,respectively.Since 2013 she is pursuing her Ph.D.at the School of Control Science and Engineering,Shandong University.Currently,she is working in the School of Management Science and Engineering,Shandong Normal University.Her research interests include game theory,analysis and control of logical dynamic systems.E-mail:wyh_1005@163.com.

DaizhanCHENG(SM’01-F’06)receivedthe B.Sc.degree from Department of Mechanics,Tsinghua University,in 1970,received the M.Sc.degree from Graduate School of Chinese Academy of Sciences in 1981,the Ph.D.degree from Washington University,St.Louis,in 1985.Since 1990,he is a Professor with Institute of Systems Science,Academy of Mathematics and Systems Science,Chinese Academy of Sciences.He is the author/coauthor of over 200 journal papers,9 books and 100 conference papers.He was Associate Editor of the International Journal of Mathematical Systems,Estimation and Control(1990–1993);Automatica(1999–2002);the Asian Journal of Control(2001–2004);Subject Editor of the International Journal of Robust and Nonlinear Control(2005–2008).He is currently Editor-in-Chief of the J.Control Theory and Applications and Deputy Editor-in-Chief of Control and Decision.He was the Chairman of IEEE CSS Beijing Chapter(2006–2008),Chairman of Technical Committee on Control Theory,Chinese Association of Automation,Program Committee Chair of annual Chinese Control Conference(2003–2010),IEEE Fellow(2005–)and IFAC Fellow(2008–).Prof.Cheng’s research interests include nonlinear system control,hamiltonian system,numerical method in system analysis and control,complex systems.E-mail:dcheng@iss.ac.cn.

Jiangbo LIUreceived his M.Sc.and Ph.D.degrees from Washington University in St.Louis,in 1981 and 1985,respectively.Currently,he is a professor in the Computer Science and Information Systems Department,Bradley University.His research interests include computer networks,distributed computing,mobile computing,and linear and nonlinear control systems.E-mail:jiangbo@bradley.edu.