Counting Periodic Points in Parallel Graph Dynamical Systems
Open Access
- 14 September 2020
- journal article
- research article
- Published by Wiley in Complexity
- Vol. 2020, 1-9
Abstract
Let be a parallel dynamical system over an undirected graph with a Boolean maxterm or minterm function as a global evolution operator. It is well known that every periodic point has at most two periods. Actually, periodic points of different periods cannot coexist, and a fixed point theorem is also known. In addition, an upper bound for the number of periodic points of has been given. In this paper, we complete the study, solving the minimum number of periodic points’ problem for this kind of dynamical systems which has been usually considered from the point of view of complexity. In order to do this, we use methods based on the notions of minimal dominating sets and maximal independent sets in graphs, respectively. More specifically, we find a lower bound for the number of fixed points and a lower bound for the number of 2-periodic points of . In addition, we provide a formula that allows us to calculate the exact number of fixed points. Furthermore, we provide some conditions under which these lower bounds are attained, thus generalizing the fixed-point theorem and the 2-period theorem for these systems.
Keywords
Funding Information
- Junta de Comunidades de Castilla-La Mancha (SBPLY/17/180501/000493, OP2014-2020, 2020-GRIN-29225, PGC2018-097198-B-I00)
- European Regional Development Fund (SBPLY/17/180501/000493, OP2014-2020, 2020-GRIN-29225, PGC2018-097198-B-I00)
- European Regional Development Fund (SBPLY/17/180501/000493, OP2014-2020, 2020-GRIN-29225, PGC2018-097198-B-I00)
- Ministry of Science, Innovation and Universities of Spain (SBPLY/17/180501/000493, OP2014-2020, 2020-GRIN-29225, PGC2018-097198-B-I00)
This publication has 33 references indexed in Scilit:
- Parallel dynamical systems over directed dependency graphsApplied Mathematics and Computation, 2012
- Sand piles: From physics to cellular automata modelsTheoretical Computer Science, 2012
- Parallel discrete dynamical systems on maxterm and minterm Boolean functionsMathematical and Computer Modelling, 2012
- Attraction Basins as Gauges of Robustness against Boundary Conditions in Biological Complex SystemsPLOS ONE, 2010
- Graphic requirements for multistability and attractive cycles in a Boolean dynamical frameworkAdvances in Applied Mathematics, 2008
- Optimal control of LTI systems over unreliable communication linksAutomatica, 2006
- On the Use of Cellular Automata in Symmetric CryptographyActa Applicandae Mathematicae, 2006
- Approximation of dynamical systems by continuous time recurrent neural networksNeural Networks, 1993
- Boolean formalization of genetic control circuitsJournal of Theoretical Biology, 1973
- Metabolic stability and epigenesis in randomly constructed genetic netsJournal of Theoretical Biology, 1969