ETS IV: Sequential dynamical systems: fixed points, invertibility and equivalence

摘要

Sequential dynamical systems (SDSs) are discrete dynamical systems that are obtained from the following data: (a) a finite (labeled) graph Y with vertex set {1,…,n} where each vertex has a binary state, (b) a vertex labeled sequence of functions (Fi,Y:F2n→F2n)i and (c) a permutation π∈Sn. The function Fi,Y updates the binary state of vertex i as a function of the states of vertex i and its Y-neighbors and leaves the states of all other vertices fixed. The permutation π represents a Y-vertex ordering according to which the functions Fi,Y are applied. By composing the functions Fi,Y in the order given by π we obtain the SDSFY,π=∏i=1nFπ(i),Y:F2n→F2n.In this paper we will generalize a class of results on SDS that have been proven for symmetric Boolean (local) functions to quasi-symmetric local functions. Further, we completely classify invertible SDS and investigate fixed points of sequential and parallel cellular automata (CA). Finally, we show sharpness of a combinatorial upper bound for the number of non-equivalent SDS that can be obtained through rescheduling for a certain class of graphs.