Polynomial-complexity distributed approaches for reachability of symmetric boolean networks

Symmetric Boolean networks (SBNs) are a class of binary-valued dynamical systems, where the couplings in logical iteration formulas (LIFs) are equally constrained within symmetric logic operators. Its evolution can remain invariant under arbitrary perturbation of literals in LIFs, generating important applications in cryptography, software design and threshold-based gene regulation. Building upon this property, we develop a novel distributed approach from (n x n)-dimensional dependency matrix to construct the explicit formulas and iterative algorithms for judging reachability of SBNs. Compared with traditional approaches based on (2ⁿ x 2ⁿ)-dimensional state transition matrix, the complexity is markedly reduced from O(K2²ⁿ) to O(Kn³). We also demonstrate that the developed approach owns interactivity, reversibility and scalability. Moreover, for SBNs with unreachable target states, optimal pinning controllers are designed to efficiently achieve the reachable goal. In addition, a new theoretical framework is established to deal with the unitary and three kinds of distributed time-varying delays in SBNs. Improved criteria from the pruned trees method and a combined algorithm are further constructed to determine reachability under these delay conditions. Finally, we validate applications of the theoretical results on a cholesterol regulatory pathway network and a delayed cellular shape-dependent regulatory network.