Dynamics of Automata Networks: Theory and numerical experiments.

Abstract

Automata Networks are discrete dynamical systems initially introduced by von Neumann [84], Mc-Culloch [50] and Ulam [81] and they have been used to model diverse complex systems such as the study of the evolution and self-organization of physical [36] and biological [20] systems. Automata Networks are composed of a graph, where each node acquires different states (from a finite set) and evolves in units of discrete time, according to a certain function – known as the local transition rule – that depends on the neighboring states of the network. Cellular Automata (CA) and Boolean Networks (BN) are particular cases of Automata Networks. In the CA, the neighborhood structure and the transition rules are the same for all nodes. On the other hand, Boolean Networks are non-uniform, binary systems, meaning that each node can take only two possible states and evolves according to its own local Boolean transition rule, on an arbitrary finite graph (orientated or not oriented). The thesis consists of three parts. The first two study problems related to Cellular Automata: a class of decision problems with binary, one-dimensional CAs, and the complexity analysis of a specific decision problem for elementary CA, the prediction of the so-called stability problem. The third part is focused on the dynamics of Boolean Networks with Memory (RBM) and their applications.