In this paper are presented first results of a theoretical study on the role of non-monotone interactions in Boolean automata networks. We propose to analyse the contribution of non-monotony to the diversity and complexity in their dynamical behaviours according to two axes. The first one consists in supporting the idea that non-monotony has a peculiar influence on the sensitivity to synchronism of such networks. It leads us to the second axis that presents preliminary results and builds an understanding of the dynamical behaviours, in particular concerning convergence times, of specific non-monotone Boolean automata networks called XOR circulant networks.
We analyse a model of fixed in-degree Random Boolean Networks in which the fraction of input-receiving nodes is controlled by a parameter gamma. We investigate analytically and numerically the dynamics of graphs under a parallel XOR updating scheme. This scheme is interesting because it is accessible analytically and its phenomenology is at the same time under control, and as rich as the one of general Boolean networks. Biologically, it is justified on abstract grounds by the fact that all existing interactions play a dynamical role. We give analytical formulas for the dynamics on general graphs, showing that with a XOR-type evolution rule, dynamic features are direct consequences of the topological feedback structure, in analogy with the role of relevant components in Kauffman networks. Considering graphs with fixed in-degree, we characterize analytically and numerically the feedback regions using graph decimation algorithms (Leaf Removal). With varying gamma, this graph ensemble shows a phase transition that separates a tree-like graph region from one in which feedback components emerge. Networks near the transition point have feedback components made of disjoint loops, in which each node has exactly one incoming and one outgoing link. Using this fact we provide analytical estimates of the maximum period starting from topological considerations.
The paper proposes a simple formalism for dealing with deterministic, non-deterministic and stochastic cellular automata in a unifying and composable manner. Armed with this formalism, we extend the notion of intrinsic simulation between deterministic cellular automata, to the non-deterministic and stochastic settings. We then provide explicit tools to prove or disprove the existence of such a simulation between two stochastic cellular automata, even though the intrinsic simulation relation is shown to be undecidable in dimension two and higher. The key result behind this is the caracterization of equality of stochastic global maps by the existence of a coupling between the random sources. We then prove that there is a universal non-deterministic cellular automaton, but no universal stochastic cellular automaton. Yet we provide stochastic cellular automata achieving optimal partial universality.
In this work we consider random Boolean networks that provide a general model for genetic regulatory networks. We extend the analysis of James Lynch who was able to proof Kauffmans conjecture that in the ordered phase of random networks, the number of ineffective and freezing gates is large, where as in the disordered phase their number is small. Lynch proved the conjecture only for networks with connectivity two and non-uniform probabilities for the Boolean functions. We show how to apply the proof to networks with arbitrary connectivity $K$ and to random networks with biased Boolean functions. It turns out that in these cases Lynchs parameter $lambda$ is equivalent to the expectation of average sensitivity of the Boolean functions used to construct the network. Hence we can apply a known theorem for the expectation of the average sensitivity. In order to prove the results for networks with biased functions, we deduct the expectation of the average sensitivity when only functions with specific connectivity and specific bias are chosen at random.
Boolean Networks (BNs) are established models to qualitatively describe biological systems. The analysis of BNs might be infeasible for medium to large BNs due to the state-space explosion problem. We propose a novel reduction technique called emph{Backward Boolean Equivalence} (BBE), which preserves some properties of interest of BNs. In particular, reduced BNs provide a compact representation by grouping variables that, if initialized equally, are always updated equally. The resulting reduced state space is a subset of the original one, restricted to identical initialization of grouped variables. The corresponding trajectories of the original BN can be exactly restored. We show the effectiveness of BBE by performing a large-scale validation on the whole GINsim BN repository. In selected cases, we show how our method enables analyses that would be otherwise intractable. Our method complements, and can be combined with, other reduction methods found in the literature.
We study the stable attractors of a class of continuous dynamical systems that may be idealized as networks of Boolean elements, with the goal of determining which Boolean attractors, if any, are good approximations of the attractors of generic continuous systems. We investigate the dynamics in simple rings and rings with one additional self-input. An analysis of switching characteristics and pulse propagation explains the relation between attractors of the continuous systems and their Boolean approximations. For simple rings, reliable Boolean attractors correspond to stable continuous attractors. For networks with more complex logic, the qualitative features of continuous attractors are influenced by inherently non-Boolean characteristics of switching events.