On the Enumeration of Cycle-equivalent Classes of Sequential Dynamical Systems

Andrew Dove

Sequential dynamical systems (SDSs) is a class of dynamical systems that can be used to model many complex systems. Two SDSs are cycle equivalent if their periodic orbits are isomorphic as directed graphs. This means that the two systems have similar long-term dynamics. This paper approaches the problem of applying the vertex functions sequentially to the states of the vertices in a given graph Y, using an update order instead of applying all the vertex functions to Y in parallel. Three forms of equivalence for SDSs are functional equivalence, dynamical equivalence, and cycle equivalence. This paper describes upper bounds for the number of equivalence classes for each of these forms of equivalence, focusing mainly on cycle equivalence and its bound, κ. This paper gives new results for the evaluation of κ for certain families of graphs.