Analysis and Control of Boolean Networks (eBook)

Daizhan Cheng received the Ph.D. degree in systems science from Washington University, St. Louis, in 1985. Currently, he is a Professor with the Institute of Systems Science, Chinese Academy of Sciences, Beijing, China. His research interests include nonlinear systems, numerical method, complex systems, etc. Dr. Cheng is Chairman of the Technical Committee on Control Theory (since 2003), Chinese Association of Automation, a Fellow of the IEEE, and a Fellow of the International Federation of Automatic Control. Hongsheng Qi received the Ph.D. degree in systems theory from the Academy of Mathematics and Systems Science, Chinese Academy of Sciences in 2008. He is currently a post-doctoral fellow at the Key Laboratory of Systems and Control, Chinese Academy of Sciences. His research interests include nonlinear systems control, complex systems, etc. Zhiqiang Li received the M.S. degree from Zhengzhou University in 2007. He is currently a Ph.D. student in the Academy of Mathematics and Systems Science, Chinese Academy of Sciences. His research interests include nonlinear systems control, complex systems, etc.

Preface 6
References 10
Contents 11
Notation 15
Propositional Logic 17
Statements 17
Implication and Equivalence 21
Adequate Sets of Connectives 24
Normal Form 27
Multivalued Logic 30
References 34
Semi-tensor Product of Matrices 35
Multiple-Dimensional Data 35
Semi-tensor Product of Matrices 45
Swap Matrix 53
Properties of the Semi-tensor Product 57
General Semi-tensor Product 65
References 69
Matrix Expression of Logic 70
Structure Matrix of a Logical Operator 70
Structure Matrix for k-valued Logic 74
Logical Matrices 78
References 80
Logical Equations 81
Solution of a Logical Equation 81
Equivalent Algebraic Equations 82
Logical Inference 92
Substitution 98
k-valued Logical Equations 99
Failure Location: An Application 103
Matrix Expression of Route Logic 103
Failure Location 106
Cascading Inference 111
References 114
Topological Structure of a Boolean Network 116
Introduction to Boolean Networks 116
Dynamics of Boolean Networks 117
Fixed Points and Cycles 121
Some Classical Examples 132
Serial Boolean Networks 137
Higher Order Boolean Networks 139
First Algebraic Form of Higher Order Boolean Networks 141
Second Algebraic Form of Higher Order Boolean Networks 150
References 152
Input-State Approach to Boolean Control Networks 154
Boolean Control Networks 154
Semi-tensor Product Vector Space vs. Semi-tensor Product Space 156
Cycles in Input-State Space 159
Cascaded Boolean Networks 164
Two Illustrative Examples 167
References 174
Model Construction via Observed Data 175
Reconstructing Networks 175
Model Construction for General Networks 183
Construction with Known Network Graph 188
Least In-degree Model 189
Construction of Uniform Boolean Network 193
Modeling via Data with Errors 196
References 199
State Space and Subspaces 200
State Spaces of Boolean Networks 200
Coordinate Transformation 202
Regular Subspaces 207
Invariant Subspaces 215
Indistinct Rolling Gear Structure 218
References 223
Controllability and Observability of Boolean Control Networks 224
Control via Input Boolean Network 224
Subnetworks 231
Controllability via Free Boolean Sequence 233
Observability 238
References 242
Realization of Boolean Control Networks 243
What Is a Realization? 243
Controllable Normal Form 245
Observable Normal Form 249
Kalman Decomposition 252
Realization 256
References 258
Stability and Stabilization 259
Boolean Matrices 259
Global Stability 263
Stabilization of Boolean Control Networks 271
References 283
Disturbance Decoupling 284
Problem Formulation 284
Y-friendly Subspace 285
Control Design 292
Canalizing Boolean Mapping 298
Solving DDPs via Constant Controls 301
References 304
Feedback Decomposition of Boolean Control Networks 306
Decomposition of Control Systems 306
The Cascading State-space Decomposition Problem 307
Comparable Regular Subspaces 312
The Parallel State-space Decomposition Problem 314
Input-Output Decomposition 317
References 320
k-valued Networks 321
A Review of k-valued Logic 321
Dynamics of k-valued Networks 324
State Space and Coordinate Transformations 328
Cycles and Transient Period 332
Network Reconstruction 333
k-valued Control Networks 338
Mix-valued Logic 348
References 353
Optimal Control 354
Input-State Transfer Graphs 354
Topological Structure of Logical Control Networks 358
Optimal Control of Logical Control Networks 363
Optimal Control of Higher-Order Logical Control Networks 368
References 376
Input-State Incidence Matrices 377
The Input-State Incidence Matrix 377
Controllability 380
Trajectory Tracking and Control Design 384
Observability 385
Fixed Points and Cycles 388
Mix-valued Logical Systems 389
References 394
Identification of Boolean Control Networks 395
What Is Identification? 395
Identification via Input-State Data 396
Identification via Input-Output Data 399
Numerical Solutions 402
General Algorithm 402
Numerical Solution Based on Network Graph 406
Identification of Higher-Order Systems 409
Approximate Identification 410
References 413
Applications to Game Theory 414
Strategies with Finite Memory 414
Cycle Strategy 417
Compounded Games 420
Sub-Nash Solution for Zero-Memory Strategies 422
Nash Equilibrium for µ-Memory Strategies 424
Common Nash (Sub-Nash) Solutions for µ-Memory Strategies 426
References 434
Random Boolean Networks 435
Markov Chains 435
Vector Form of Random Boolean Variables 443
Matrix Expression of a Random Boolean Network 446
Some Topological Properties 451
References 454
Appendix A Numerical Algorithms 455
Computation of Logical Matrices 455
Basic Functions 457
Some Examples 462
Appendix B Proofs of Some Theorems Concerning the Semi-tensor Product 467
References 470
Index 471