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.
|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 (295Kb)
|Publisher Web site:||http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p48|
|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|