Matrix expression and reachability analysis of finite automata

J Control Theory Appl 2012 10 (2) 210- -215DOI 10.1007/511768-012-1178-4Matrix expression and reachability analysis offinite automataXiangru XU, Yiguang HONGKey Laboratory of Systems and Control, Academy of Mathematics and Systerms Science, Chinese Academy of Sciences, Beiing 100190, ChinaAbstract: In this paper, we propose a matrix -based approach for finite automata and then study the reachabilityconditions. Both the deterministic and nondeterministic automata are expressed in matrix forms, and the necessary andsufficient conditions on reachability are given using semitensor product of matrices. Our results show that the matrixexpression provides an effective computational way for the reachability analysis of finite automata.Keywords: Finite automata; Reachability; Matrix expression; Semitensor product1 Introductiontomata is shown in Section 2. Then, a sufficient and nec-.Automata provide an appropriate model for the design essary condition for the reachability problem of both deter-and analysis of discrete -event systems and hybrid dynam- ministic and nondeterministic automata are given in Sec-ics [1-4]. Reachability analysis of automata is an interest-tion3, while further discussion is carried out on the reach-ing and important topic, which is essential to many related ability computation and the construction of reachable set inproblems such as robust stability of hybrid system, blocking Section 4. Finally, conclusions are given in Section 5.detection and safety properties of automata [5-7].Algebraic approach is an elegant branch for automata the-2 Matrix-based expression of automataory [8], but few efforts have been devoted to the matrix-In this section, we first give preliminaries and then pro-based methods. For example, reference [9] introduced the pose a matrix-based expression for finite automata.notion of transition matrix in the study of sequential ma-First of all, we introduce notations for the following us-chines, reference [10] presented a Boolean- matrix -basedmethod for automata to investigate regularity-preserving. 8h is the kth column of the identity matrix In∈Rnxn,functions, and reference [11] addressed a state equation-like and denote An := {......approach for automata and defines controllability, reacha-●col;(A) is the ith column of matrix A, and Col(A) is thebility and stabilizability following the conventional frame- set of all the columns of matrix A.work of control theory. Although some results were pro- . on ∈R" is the vector with each element equal to 0,vided in the eisting leraures, many importat poblemns while T。∈R" is the veter with each element equal to 1.remain to be solved.The objective of the paper is to propose a matrix-based. Givenη = (....n)T,5 = (1....n)T∈R",approach for finite automata with the help of semitensordenoteη≤ζifηi≤Gi fori= ...... M(p,g) denotes the element in the pth row and qth col-product (STP). First proposed by Cheng [12], STP (or sim-umn of a given matrix M.ply called Cheng product) is a generalization of the con-STP or Cheng product was first proposed by Cheng [12].ventional matrix product, and has been fully developed andDefinition 1 For M∈RmXn and N∈RPx9, theirwidely applied to many areas including Boolean networksSTP (or Cheng product), denoted by M X N, is defined as[12], Boolean calculus [13], and nonlinear control [14].follows:Compared with the previous models, the STP-based ma-trix method proposed in this paper provide a very naturalMx N := (M 8 Is/n)(N 8Is/p),1)way in the modeling of finite automata for both determin-where 8 is the least common multiple of n and p and⑧isistic and nondeterministic cases. The state and input of athe Kronecker product.given automaton can be expressed in column vector forms,and the run of an input string can be considered as straight-Obviously, the conventional matrix product is the partic-forward matrix products in the sense of STP. What is more,ular case of STP whenn = p. We assume the matrix prod-we do not confine the matrix operation in the Boolean do- uct throughout the paper to be STP, so we omit the sym-main, which can provide us with more informnation. With thebol x when there is no confusion. For a matrix A, denotenew expression, the analysis on reachability can be carriedAl= A,Ai+1= Aix A,Vi≥1.out uniformly for both deterministic and nondeterministicFor any two column vectorsx∈Rm and y∈R", there isautomata.a unique swap matrix Wrm,n]∈Rmnxmnonly dependingThe paper is organized as follows. Basic notations andon n, m such thatdefinitions are given and the matrix expression for finite au-中国煤化工(2)Received 30 August 2011; evised6 February 2012.MYHCNMHGThis work was supported by the National Natural Science Foundation of China (No. 61 1740/1).◎South China University of Technology and Academy of Mathematics and Systems Science, CAS and Sprigr-Verlag Berlin Heidelberg 2012X. Xu et al. /J Control Theory Appl 2012 10 (2) 210 -215211Other useful properties of STP can be found in [12].there is an equivalent relationship between the transitionBefore providing the matrix expression, we first intro- function f of automaton A and its transition structure ma-duce the basic concepts of finite automata [1- -2]:trix F.Definition 2 An automaton is a five-tuple A= (X, E，Remark1 Although each element of matix F is eitherf,x0, Xm), where X is a finite set of states; E is a finite set 0or 1, P is esntially diferent from the logical matix dis-of input symbols called alphabet; x0∈X is the initial state; cussed in Boolean network [12]. If the finite automaton AXm C x is the set of accepted states; andf :XxE→2X is deterministic, every column of F contains no more thanwhere 2X denotes the power set of x (i.e., the set of all sub- one '1', while if A is nondeterministic, some columns ofFsets of X), thatis, f(x,e)∈X whenever it is defined.may contain more than one 1's. However, each column ofA is a deterministic finite automaton (DFA) if for eachlogical matrix in [12] has exactly one '1'.x∈X,e∈E,lf(x,e)| ≤1; otherwise, itis said to beIf we consider the state of the automaton evolves witha nondeterministic finite automaton (NFA). Both DFA and a given input ei at every step, a finite automaton can beNFA can be generally called finite automaton.viewed as a dynamical system. We introduce some conceptsDenote E* as the set of finite strings on the alpha- that will be used in the sequel.bet E which excludes the empty transition. Given an in-The vector form of input of a given automaton A at timeput stringe = e...et∈E*, we define f(x,e) = t isacolumn vector u(t)∈Am, and u(t) = om with the in-f(f(... f(f(x,e1)2)...),et). In other words, the au- put ei at time step t. An input stringe= eiei...eir∈E*tomaton starting from the initial state x reads the inpute1 can be identifed with xj=1u(j) := ()()..(t)∈and moves tox'∈f(x, e1), and then reads input e2 and Otm (that is,e ~ xj=xu()), where ei; is identified withmoves tox"∈f(x',e2), and so on. We calx 4 x' 4 u(i),V1≤j≤t.x"... a path of the automaton given input string e and ini-The vector form of state of A at time step t is a columntial state x. We call a state x is reachable from yif thereis vector x(t) = (x(),x(+()... x()T∈R", wheree∈E* such thaty∈ f(x,e). It is easy to see that, given y x*(t) is the number of different paths by which the initialthat is reachable from x, there is only one path fromx toyif state can reach state i with a given input string of lengththe automaton considered is deterministic, and there might t- 1, where x(1) = x0. For DFA, the target state frombe more than one path if the automaton is nondeterministic. which the initial state can move to with a given input stringGiven an automatonA = (X, E,f,x0,X"), the reachabil- of length t - 1 is unique and only one path exists from theity problem is to find a string of E* that makes A go from initial state to the target state. Therefore, there is only one jthe initial state to the target state at least once [15].with1≤j≤n such thatxi(t) = 1, namely, x(t)∈On.Then, we will introduce a new matix expression for au- If no state is reachable with the input string of lengtht- 1,tomata. To do this, we first define the transition structure x(t) = 0n. For NFA, given an input string, the states reach-matrix, which is the key for the modeling and calculationof able from the initial state forms a set, and there may ex-finite automata.ist more than one paths from the initial state to the targetGiven a finite automaton A = (X,E,f,x", Xm). As- states. Thus, there may exist more than one elements in x(t)sume X = {x,2..., xn}. Identify xi withδi(1≤i≤greater than 0.n) (expressed as xi ~ δ for simplicity), and call究the The following is a basic result for the matrix expressionvector form of xi. Now, we can denote On as the set of of automata using notations above.states X, namely,X = {oh, 8..... }. Similarly, assumeTheorem 1 Given a finite input string Xj= :1u(j) for fi-E= {e1, e2.... em}, we identifyej withom(1≤j≤m) nite automaton A, the dynamics of A can be described by(denoted as ej ~ m), called the vector form of ei, and the following equation:the set of input symbol E can be expressed as Om, namely,x(t+1)= Fu(t)x(t)，1≤t≤8.(4)E = {m, ..... om}. Therefore, xi∈f(xj,ek) can beequivalently expressed asi∈f(8%, 疏) using the vectorProof We prove it by mathematical induction.form of the input and state.Whent = 1, we have Fu(1)x(1) = Fx(1)∈Rn withInputei∈E(1≤i≤m)of A determines aunique u(1) =点where1≤k≤m is arbitrary. If u(1) movesmatrix F:∈RnXn, called transition structure matrix withx(1) to路,1≤j≤n, then the jth element of Fxx(1)respect to ei, whereequals 1 from the definition of transition structure matrix,[1, ifδi∈f(85,om),while Fx(1) = On if u(1) cannot move x(1) to any otherFi(e,t)=3)state. By the meaning of the vector form of state x(2), it isl 0，otherwise.obvious that (4) holds whent= 1. .Actually, F is the adjacency matrix of the ei-labeled sub- Suppose (4) holds whent=p- 1, andu(p)=疏for .graph associated with A [16], and the 'transition matrix' in- any k with1 < k≤m. Then,troduced in [1] and [9] is the transpose of F.Therefore, a finite automaton A determines a matrix F =F"l(p)x(prVT中国煤化工()T[F1 F2 ... Fm]∈Rnxmn, which is called the transitionstructure matrix of A. On the other hand, once the matrix"THC N M H (202)2()...F is given, it is obvious that the transition function of theS Frn()())T.automaton can be uniquely determined by (3). As a result,212X. Xu et al.1J Control Theory Appl 2012 10(2) 210 -215By (3), we havegiven input stringe ~ x克=1u(k) = 8nt. From the defini-tion of vector form of state, we conclude that x* is reachable2 Fr.x)x'()= 2xi(p), VI≤j≤n,from x0 with input sting e.Summarizing the above analysis, we obtain the conclu-whereIj=. {il≤i≤n,i moves to i with input ek}. sion. The proof is completed.Therefore, 2 x*(p) equals the sum of the number of dif-The vector form of the input string that makes initial stateferent paths by which the initial state xo can reach state δireach the target state can be easily constructed from thewith the input stringe= x=iu(s), and then from h to疏proof of Theorem 2. Furthermore, it is not hard to see thatwith input u(p) =阶, where i can be arbitrary. On the otherif A is DFA, then the necessary and sufficient condition ofhand, x(p + 1) equals the number of different paths, byTheorem 2 becomes f∈Col((FW[n,m)'R).which the initial state xo can reach h with the input stringThe following corollary gives a criterion for the languageaccepted by A.xg= :1u(s). Thus, xr'(p+ 1) = 2 Fi(j,)x() for each j Corollary 1 Given finite automaton A = (X, E,f,x°.(double counting), which implies Fu(p)x(p) = x(p+ 1).xm) with x0 =积. The language of length t accepted byAis the set {elxtarg ≤(FWrn,m)*8R X%=1 u(k), whereBy mathematical induction, the proof is completed.From equation (4), it is clear that, ifx(t) =. on, thene=xu_(u(k)xtarB∈ X"}.Based on Corollary 1, we can formally obtain the lan-x(k)= On,Vk≥t.guage accepted by A. We give the following examples toRemark2 As mentioned above, matrix based methodsillustrate the given results and related algorithms.were also investigated in [9- -1 1], where the matrix with re-Example 11) Consider DFAA = (X,E,f,x0, Xm)spective to every input was defined and consideredinasep- shown in Fig. 1, where X = {21,2,23,14,.5},E =arate manner. Our matrix-based formulation, however, han-{e1,e2,e3,e4},x0=x1,X"= {x4,xs}.dles the automata in a unified way for both DFA and NFA.3 Reachability analysisIn this section, we propose matrix-based analysis for the一国气国reachaility of finite automata.Consider a finite automaton A = (X, E,f,x0,X"),where X = {x1,2....n}, E = {e,2e...,em}. Iden-tifyxi with8i(1≤i≤n), andej with8m(1≤j≤m), asFig.1 DFA of Example 1.described above.The transition structure matrix of A isThen, we have the following main result based on the pro-/00000 00000 00000 00000\posed matrix expression.10000 00000 00000 00000Theorem 2 Suppose F is the transition structure ma-F=00000 01000 00100 00000trix of A. Then, target state x89 is reachable from0010000000 01000 00000x0 =积with input strings of length t if and only if there00000 00000 00000 001 10/exists η∈Col((FW[n,m])*8R) such that8≤η.Proof Let x(t) and u(t) be the vector form of state andWhent = 2, (FW5.4)26号∈RS5x16, whereinput of A at time t, respectively. x(1) = x0. For a finiteinput stringe= eqeiz...eit∈E*, whereei, ~ u(j), wecol2((FWi5,4)28号) =酷, col3((FWi5,4)28)= ∞havewith all the other columns equal to 0s. Thus, by Theorem2,x(t+ 1)= Fu(t)x(t)states δ3 and ζ are reachable from x0 with input string of= FWin,m)x(t)u(t)length 2. For example, suppose δ号is the target state. Since= (FWn,m)2x(t - 1)u(t - 1)u(t)δψ = (FW(5,4)28号K 88, the corresponding input string ise= u(1)u(2)= 816 withu(1)=δ~e1,u(2)=~e3.Therefore, the string e = e1e3 moves the initial state to the= (FWmn,m)*x(1)x=1 u(k)target state x告= (FWrn,m)4R) x=1 u(k).Whent = 3, (FWi5.4)3眙∈R5x64, where'only if' part: Because (FWn,m)*R∈Rnxm' andcols((FWs,4)8号) =酷, cole((FWs,1)38号) = 8X众_1u(k)∈Om', we can letcole((FWi5,4)6号) = 6g, col2((FWi5.4)号)= εgη = x(t+ 1)∈Col(FWrn,m)R)。with all the other columns equal to os. Thus, 明,路晤Sincex* = 8器is reachable from x0 =咒with input string are reachable from r0 with inout string of length 3. Takee, it is obvious thatx9(t+1)> 0. For DFA,x(t+1)∈An，8 for exam中国煤化工)u(2)u(3)。= 84we have 8旯x(t+1)=n;andforNFA,wehaveor8品2canrget state 8. SinceYH贸≤x(t+1)=8器= 8}8际δCNMHaESUeion。V64‘if’part: Since there is η such that 8咒≤η and η = input stringse = e1e2e4 ande = e1e3e4 can move 8号to thecol((FWn,m)*8R)(1≤τ≤m'), we havex9(t+ 1)≥1 target state xg.X. Xu et al. /J Control Theory Appl 2012 10(2) 210 -215213Whent=4,4 Further analysiscol2o((FWi5,1)48号) =鸪, col25((FWi5,4)4号) =号,It is known that the computation is not easy when thecol27((FWi5,1)48号) =号, col28((FWis,4)4号) =∞size of the automaton is large. With our matrix method,(FWm,m) in Theorem 1 is of dimensionn x m'n. Whenwith all the other columns equal to Os. Therefore,号,酷, 8 the length of input string t is not short enough, the size ofare reachable from x0 with input string of length 4. We have (FWnm) will be too large to calculate. However, if weare only interested in the reachability relation between statesδ286 = 81828184→e= ere2e1e4 moves g to 唱,of a finite automaton and do not care much about what theδ256 = 88子84→e=ee2e3e1 moves δ号to酷paths are with input strings of a given length, the computa-8256 = 848288寸e= ere2e3e3 moves ξ to码,tion may become relatively easier.δ28ε= 8碌86→e= e1e2e3e4 moves号to 8.The following result is given to show the number of dif-By Corollary 1, the language of length 4 accepted by A isferent paths from state 6R to state .Theorem 3 Consider a finite automaton A = (X, E,{e1e2e1e4, e1e2e3e1, e1e2ze3e4}.Other arbitrary finite length of input strings can be ana-f,x0,Xm) with transition structure matrix F. Then,M*(q,p) equals the number of different paths that state 8lyzed likewise.2) Consider NFA A= (X, E, f, x0, Xm) shown in Fig. 2,trix:an reach state咒with input string of length t, where ma-where X =. {x1,T2,T3,E4,xs}, E = {e1,e2,e3,e4},M'=(&)Tx(TmxF)°x Im.(5x0 = x1, and xm = {xs}. It can be seen that the stateT2 can move to T3 or x4 given input e2.Proof Set matrix K = (1m x F)∈RmnKmn. SinceF=[Fi F2 ... Fm] ∈IRnxmn, we have(F F2... Fm\eh e一国二国e. erK=F F2... FmFr F2... FmFig. 2 NFA of Example 1Obviously, K is row-periodic, and so is Kt fort≥1. Parti-The transition structure matrix of A istion Kt into equal block matrices as follows:/00000 00000 00000 00000\K{ K... Kmn10000 00000 00000 00000K{ K... KmKt:F=| 00000 01000 00100 000000010001000 01000 00000KR... Km)00000 00000 00000 00110/where K'∈RrnXn, 1≤s≤m.Whent= 2,We claim that, if K<(i) = C, there are c different paths tocol2((FWis,.)28号) = (0,0,1,1,0)T,make xj reach xi;, with input string of length t which beginswith eg. In fact, the claim can be proved by mathematical in-col3((FWrs,4)28号) = (0,0,0, 1,0)Tduction. When t = 1, the conclusion follows immediately.with all the other columns equal to 05. Since 酷≤ Suppose the claim holds whent= l. Then, Kl+1 = KK'(0,0,1,1,0)T and 酷≤(0,0,0,1,0)T, 告is reachable andfrom o with inpu srige=u()u(3)=的=的sce r+las)= 艺K(aK(as)= z亡Fi(xaKswo.)"a1e1e2 or e = u(1)u(2)_ = 86 = 882 ~ e1e3. Sinceb二1k=1ξ≤(0,0,1,1,0)T, 号is reachable from x0 with input(6stringe= u(1)u(2)= 8i6= 8]82 ~ e1e2.Given an input stringe = eanea, .ae+1 withear =Whent = 3, we haveeg, a path from xj to reach xi can be considered as fol-cols((FWi5.,)38引) = (0,0,0, 1,0)T,lows: the state first moves from xj to xk with input stringcol((FWs,)38号) = (0,0, 1,0,0)T,eaneas ...eae, and then from Tk to Xi with input stringear+1. Since K'(t.,) is the number of paths by which xjcol((FWs,4)6)= (0,0,0,0,2)T,can reach xk, with input string of length l that begins withcol2((FW5s,4)8号) = (0,0,0,0,1)Teg, and Fr(i,k) = 1 if and only if input eb can move xk towith all the other columns equal to 05. For instance,xi, we can find that the rightmost hand side of (6) exactlysince x(3) = (0,0,0,0,2)T with input string e =shows the number of paths that xj can reach xi with inputu(1)u(2)u(3) = 84 = δ}8204 ~ e1e2e4, initial statestring e of length l + 1 which begins with eg. The claim isthus proved.中国煤化工δg can reach the target state 8 via two different paths:x1斗x2≌x3 4xs andx1≌ζx2≌x44 x5.Since (81YHCN MH Gt, it is clear thatBy Corollary 1, the language of length 3 accepted by Ais {e1e2e4, e1e3e4}.A(qa) = E K(q,p). The conclusion is obtained imme-214X. Xu et al.1J Control Theory Appl 2012 10 (2) 210-215diately by the claim we have just proved.case, we obtainRemark 3 Reference [17] proposed a so calld 'input-/00000/00000\state incidence matrix' to reduce the size of the matrices in00000the computation for Boolean networks. In some sense, ma-M2=| 11 100M3=| 11100rix 1m X F in (5) serves the same purpose, since it is a11100square matrix, and for any t the size of (1m x F)* will(02200/(22200/not increase. In some sense, transition structure matrix F ofautomaton A and matrix 1m x F correspond to the 1ogi-cal structure matrix L' and the 'input-state incidence matrixJ(E)' in [17], respectively. However, Theorem 3 cannot beM4=obtained immediately from [17], because matrix in our pa-per is in general not a logical matrix.22200The following result is quite straightforward.Take M4 for example. M*(5,2) = 2 means that there areCorollary 2 With notations used in Theorem 3, the tar- two different paths for δ号to reach ε with input strings ofget statex* = g is reachable fromx0 =咒with an input length 4, which aree = e2e3e3e4 ande = e2e3e1e4 (asstring of length t if and only if M(q,)> 0.shown in Fig. 1).Moreover, we consider the construction of the reachableFor the NFA case, we obtain/00000)Corollary 3 For automaton A with F as its transitionstructure matrix, the set of states reachable fromx0=咒isM2= .11100.M3:21 10011 100R(xo)= {始亡M(km)>0, 1≤k≤n}03200/32200/with matrix Mj defned in (5).Ifτ(≤n) is the the length of the longest simple path(that is, a path without repeated state) originating from ini-M4 =tial state xO, then1 1100R(xo)= {%| 2 M(rm)>0, 1≤k≤n}.j=1The conclusion can be checked similarly. Furthermore, theProof If a state x is reachable from xo, there must be aset of states that are reachable from an initial state δg is ob-string with its length no more than τ(≤n) that can move.tained as R(2) = {号,δg,δ号}.xo to x.咒is reachable from xo if and only if there exist 5 Conclusionsat least one string of lengths (1≤s≤T) that moves xoWe proposed a matrix-based approach for finite automatato 8咒namely,二M(g,p) > 0 by Corllary 2. Thus, the using semitensor product in this paper. We expressed de-terministic and nondeterministic finite automata in matrixconclusion follows. The proof is completed.forms, based on which we studied the reachability problemThe automaton A is called acessible if every statex∈X and obtained necessary and suficient conditions.is reachable from x0 [1]. It is clear that A is accessible if and We believe that the matrix framework provides an effec-only if R(xo) = X. Generally, define the reachability ma- tive way in the analysis and computation for finite automata.trix M(A) of automaton A as follows: M(A)(ij) = 1 if Many interesting related problems such as hierarchical de-composition and task assignment using automata are under二M*(.,) > 0 and M(A)u,) = 0 otherwise.investigation.Remark 4 Boolean algebra can be used in the STP cal-Referencesculation and matrix. based approach for automata [10,16- m s. Eilenberg. Automa, Languges, and Machines. New York:17]. If elements in F are taken as Boolean values with ad-Academic Press, 1976.dition and multiplication between matrices as Boolean op~ [2] C. Casandras, s. Lafotune. Inroduction 10 Discrete Event Systems.erations, Corollaries 1, 2 and 3 still hold after small modi-New York: Springer-Verlag, 2008.fications. In fact, it is easy to find that Lemmas 2.1 and 2.2[3] M. Lamego. Automata control systems. IET Control Theory &Applications, 2007. 1(1): 358 - 371.in [10] are consistent with Collaries 2 and 1, rspecively [4] W. Womham, p Ramadge On the supemal colablol sbanguagegNevertheless, the lemmas in [10] is basically descriptive, butofa given中国煤化工rol and Opimiationour results are constructive.1987, 25(3)5] s. Abdelw:C N M H Gcion in discrete eventBefore the end of this section, we show an ilustrative ex-systems. Proceedings of American Control Conference. New York:ample for Theorem 3.IEEE, 2003: 1673- 1678.Example 2 Consider Example 1 again. For the DFA [6] J. Lygeros, C. Tomlin, s. Sastry Cortollers for reachabilitytX. Xu et al. /J Control Theory Appl 2012 10 (2) 210-215215specifcations for hybrid systems. Automatica, 1999, 35(3): 349 - 370. [16] K. Kim. Boolean Matrix Theory and Aplications. New York: Dekker,[7] A. Casagrande, A. Balluchi, L. Benvenuti, et al. Improving1982.anl” for engine control. IEEreachability analysihybridautomata for engine control. IEEE [17] Y. Zhao, H. Qi, D. Cheng. Input. state incidence matrix of BoolanConference on Decision and Control. New York: lEEE, 2005: 2322control networks and its applications. Systems & Control Letters,2010, 59(12): 767 - 774.8] W. Kuich, A. Salomaa. Semirings, Automata, Languages. Berlin:XiangruXU received his B.S. degree in Ap-Speringer-Verlag, 1986.plied Mathematics from Beijing Normal Univer-9] S. Seshu, R. Miller, G. Metze. Transition matrices of sequentialsity in 2009. Currently, he is a Ph.D. candi-machines. IRE Transactions on Circuit Theory, 1959, 6(1):5- 12date of Academy of Mathematics and Systems[10] G. Zhang. Automata, Boolean matrices, and ultimate periodicity.Science, Chinese Academy of Sciences, Beijing,Informnation and Compuatioin, 1999, 152(1): 138- 154.China. His research interests include automata[11] M. Dogruel, U. Ozguner. Contolability, reachability, sabizbilitytheory and multi-agent systems. E-mail: xuxian-and state reduction in automata. Proceedings of the IEEEgru@ amss.ac.cn.International Symposium on Intelligent Control. New York: IEEE,1992: 192- 19Yiguang HONG reeived his B.S. and M.S. de-[12] D. Cheng, H. Qi, z. Li. Analysis and Control of Boolean Networks: Agrees from Peking University in 1987 and 1990,Semi-tensor Product Approach. London: Springer-Verlag. 2010.respectively, and Ph.D. degree from Chinese[13] D. Cheng, Y. Zhao, x. Xu. From Boolean algebra to Boolean calculus.Academy of Sciences (CAS) in 1993. He is cur-Control Theory & Applications, 2011, 28(10): 1513 - 1523 (inrently a professor in Academy of Mathematics andChinese).Systems Science, CAS. He is serving as Deputy[14] A. Xue, F. Wu, Q. Lu, et al. Power system dynamic security regionEditor-in-Chief of Acta Automatica Sinca, andand its approximations. IEEE Transactions on Circuits and Systems -Associate Editors for several joumals including1, 2006, 53(12): 2849 - 2859.IEEE TAC. His current research interests include[15] J. Delvenne, V. Blondel. Complexity of control on finite automata. nonlinear control, multi-agent systems, and complex systems. E-mail:IEEE Transactions on Automatic Control, 2006, 51(6);: 977 - 986.yghong@iss.ac.cn.中国煤化工YHCNMHG