On the Rank and Periodic Rank of Finite Dynamical Systems

Gadouleau, Maximilien

Abstract

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.

Citation

Gadouleau, M. (2018). On the Rank and Periodic Rank of Finite Dynamical Systems. Electronic Journal of Combinatorics, 25(3), Article #P3.48

• Journal Article Type: Article
• Acceptance Date: Aug 27, 2018
• Online Publication Date: Sep 21, 2018
• Publication Date: Sep 21, 2018
• Deposit Date: Oct 4, 2018
• Publicly Available Date: Oct 5, 2018
• Journal: Electronic Journal of Combinatorics
• Electronic ISSN: 1077-8926
• Publisher: Electronic Journal of Combinatorics
• Peer Reviewed: Peer Reviewed
• Volume: 25
• Issue: 3
• Article Number: #P3.48
• Keywords: Finite dynamical systems, Boolean networks, Interaction graphs, Rank, Periodic points
• Public URL: https://durham-repository.worktribe.com/output/1317217
• Publisher URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p48