Stability of boolean dynamical systems and graph periodicity

Abstract

In the study of finite dynamical systems it is important to develop efficient algorithms that provide information about the dynamics of the systems. Criteria for determining when a system described by monomials, over the two element field, is a fixed point, have already been determined. We make use of such criteria to study the concept of stability for finite dynamical systems. In order to do this, we use the fact that a monomial dynamical system’s cycle structure can be described by the structure of the monomials. This monomial structure can be represented by a digraph. The algorithms presented in this paper, one for stability, the other for fixed points, combine such criteria with the efficiency of depth-first search rendering both algorithms with complexity O(n 2 log(n)).

En el estudio de sistemas dinámicos finitos es importante crear algoritmos que provean información sobre la dinámica de los sistemas de manera eficiente. Los criterios para determinar cuándo un sistema representado por monomios, sobre el cuerpo de dos elementos, es de punto fijo, ya han sido establecidos. Utilizaremos estos para estudiar un concepto de estabilidad para sistemas dinámicos finitos. Tomaremos en consideración que la estructura cíclica está completamente definida por su estructura monomial. Esta estructura se representa con un dígrafo. Los algoritmos en este escrito, uno para estabilidad y otro para puntos fijos, combinan estos criterios con la eficiencia de búsqueda en profundidad para crear algoritmos con orden O(n 2 log(n)).