点击次数：

论文类型：期刊论文

发表时间：2018-01-01

发表刊物：SIAM JOURNAL ON CONTROL AND OPTIMIZATION

收录刊物：SCIE、EI、Scopus

卷号：56

期号：1

页面范围：388-416

ISSN号：0363-0129

关键字：Boolean control network; bisimulation; simulation; controllability; stabilizability; synchronization; NP-hardness

摘要：A framework for analyzing bisimulation relations of Boolean control networks (BCNs) is set up in this paper. Bisimulation relations are natural objectives in control systems theory: A bisimulation relation between a pair of control systems defines a relation on their state spaces or state sets explaining how a trajectory or transition of one system can be paired with a trajectory or transition of the other system, and vice versa. The paper first formalizes the notion of (bi)simulation in BCNs and presents detailed results characterizing (bi)simulation relations for BCNs. Then, as an application of the notion of bisimulation, it considers the propagation of the fundamental properties of (macro)controllability and stabilizability through a bisimulation relation. It thereby suggests the possibility that certain control properties of a BCN can be inferred by analyzing a potentially simpler BCN. The analysis developed in this paper is based on the semitensor product approach, which gives algorithms that have exponential time complexity. A question that naturally arises is if it is possible to check bisimulation relations for BCNs in polynomial time. This question is answered in the negative, by proving that the problem of deciding whether a relation between BCNs is a bisimulation relation is NP-hard.