TY - JOUR
T1 - Asymptotic Behavior of Conjunctive Boolean Networks over Weakly Connected Digraphs
AU - Chen, Xudong
AU - Gao, Zuguang
AU - Basar, Tamer
N1 - Funding Information:
Manuscript received February 10, 2019; revised June 27, 2019; accepted July 20, 2019. Date of publication July 23, 2019; date of current version May 28, 2020. This work was supported in part by the Office of Naval Research (ONR) MURI under Grant 00014-16-1-2710. This work was presented at the 56th IEEE Conference on Decision and Control, Melbourne, Australia, December 2017. Recommended by Associate Editor F. R. Wirth. (Corresponding author: Xudong Chen.) X. Chen is with the Department of Electrical, Computer, and Energy Engineering, University of Colorado Boulder, Boulder, CO 80309 USA (e-mail:,xudong.chen@colorado.edu).
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2020/6
Y1 - 2020/6
N2 - A conjunctive Boolean network (CBN) is a finite state dynamical system, whose variables take values from a binary set, and the value update rule for each variable is a Boolean function consisting only of logic and operations. We investigate the asymptotic behavior of CBNs by computing their periodic orbits. When the underlying digraph is strongly connected, the periodic orbits of the associated CBN have been completely understood, one-to-one corresponding to binary necklaces of a certain length given by the loop number of the graph. We characterize in the paper the periodic orbits of CBNs over arbitrary weakly connected digraphs. We establish, among other things, a new method to investigate their asymptotic behavior. Specifically, we introduce a graphical approach, termed system reduction, which turns the underlying digraph into a special weakly connected digraph, whose strongly connected components are all cycles. We show that the reduced system uniquely determines the asymptotic behavior of the original system. Moreover, we provide a constructive method for computing the periodic orbit of the reduced system, which the system will enter for a given, but arbitrary initial condition.
AB - A conjunctive Boolean network (CBN) is a finite state dynamical system, whose variables take values from a binary set, and the value update rule for each variable is a Boolean function consisting only of logic and operations. We investigate the asymptotic behavior of CBNs by computing their periodic orbits. When the underlying digraph is strongly connected, the periodic orbits of the associated CBN have been completely understood, one-to-one corresponding to binary necklaces of a certain length given by the loop number of the graph. We characterize in the paper the periodic orbits of CBNs over arbitrary weakly connected digraphs. We establish, among other things, a new method to investigate their asymptotic behavior. Specifically, we introduce a graphical approach, termed system reduction, which turns the underlying digraph into a special weakly connected digraph, whose strongly connected components are all cycles. We show that the reduced system uniquely determines the asymptotic behavior of the original system. Moreover, we provide a constructive method for computing the periodic orbit of the reduced system, which the system will enter for a given, but arbitrary initial condition.
KW - Asymptotic behavior
KW - Boolean network
KW - graph theory
KW - system reduction
UR - http://www.scopus.com/inward/record.url?scp=85085983963&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85085983963&partnerID=8YFLogxK
U2 - 10.1109/TAC.2019.2930675
DO - 10.1109/TAC.2019.2930675
M3 - Article
AN - SCOPUS:85085983963
SN - 0018-9286
VL - 65
SP - 2536
EP - 2549
JO - IRE Transactions on Automatic Control
JF - IRE Transactions on Automatic Control
IS - 6
M1 - 8770125
ER -