title: Compositional properties of random Boolean networks.
abstract: Random Boolean networks (RBNs) are used in a number of applications, including cell differentiation, immune response, evolution, gene regulatory networks, and neural networks. This paper addresses the problem of computing attractors in RBNs. An RBN with n vertices has up to 2(n) states. Therefore, for large n , computing attractors by full enumeration of states is not feasible. The state space can be reduced by removing irrelevant vertices, which have no influence on the network's dynamics. In this paper, we show that attractors of an RBN can be computed compositionally from the attractors of the independent components of the subgraph induced by the relevant vertices of the network. The presented approach reduces the complexity of the problem from O (2(n)) to O (2(l)), where l is the number of relevant vertices in the largest component.
authors.affiliation: Department of Microelectronics and Information Technology, Royal Institute of Technology, Electrum 229, 164 40 Kista, Sweden.
authors.forename: Elena
authors.initials: E
authors.lastname: Dubrova
authors.forename: Maxim
authors.initials: M
authors.lastname: Teslenko