We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

On the rank and periodic rank of finite dynamical systems.

Gadouleau, Maximilien (2018) 'On the rank and periodic rank of finite dynamical systems.', Electronic journal of combinatorics., 25 (3). #P3.48.


A finite dynamical system is a function f:An→An where A is a finite alphabet, used to model a network of interacting entities. The main feature of a finite dynamical system is its interaction graph, which indicates which local functions depend on which variables; the interaction graph is a qualitative representation of the interactions amongst entities on the network. The rank of a finite dynamical system is the cardinality of its image; the periodic rank is the number of its periodic points. In this paper, we determine the maximum rank and the maximum periodic rank of a finite dynamical system with a given interaction graph over any non-Boolean alphabet. The rank and the maximum rank are both computable in polynomial time. We also obtain a similar result for Boolean finite dynamical systems (also known as Boolean networks) whose interaction graphs are contained in a given digraph. We then prove that the average rank is relatively close (as the size of the alphabet is large) to the maximum. The results mentioned above only deal with the parallel update schedule. We finally determine the maximum rank over all block-sequential update schedules and the supremum periodic rank over all complete update schedules.

Item Type:Article
Keywords:Finite dynamical systems, Boolean networks, Interaction graphs, Rank, Periodic points
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:© The author. Released under the CC BY license (International 4.0).
Date accepted:27 August 2018
Date deposited:05 October 2018
Date of first online publication:21 September 2018
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar