ETS IV: Sequential dynamical systems: fixed points, invertibility and equivalence. (English) Zbl 1028.37010
Summary: 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,\dots,n\}\) where each vertex has a binary state, (b) a vertex labeled sequence of functions \((F_{i,Y}: \mathbb{F}^n_2\to \mathbb{F}^n_2)_i\) and (c) a permutation \(\pi\in S_n\). The function \(F_{i,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 \(\pi\) represents a \(Y\)-vertex ordering according to which the functions \(F_{i,Y}\) are applied. By composing the functions \(F_{i,Y}\) in the order given by \(\pi\) we obtain the SDS \([F_Y,\pi]= \prod^n_{i=1}F_{\pi(i),Y}: \mathbb{F}^n_2\to \mathbb{F}^n_2\).
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.
For Part III, see ibid. 122, 325-340 (2001; Zbl 1050.68161).
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.
For Part III, see ibid. 122, 325-340 (2001; Zbl 1050.68161).
MSC:
37B15 | Dynamical aspects of cellular automata |
68U20 | Simulation (MSC2010) |
68Q80 | Cellular automata (computational aspects) |
Keywords:
sequential dynamical systems; quasi-symmetric functions; digraph isomorphism; topological conjugation; fixed points; cellular automataCitations:
Zbl 1050.68161References:
[1] | C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, Analysis problems for sequential dynamical systems and communicating state machines, Proc. 26th Mathematical Foundations of Computer Science (MFCS 01) 2136 (2001) 159-172; C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, Analysis problems for sequential dynamical systems and communicating state machines, Proc. 26th Mathematical Foundations of Computer Science (MFCS 01) 2136 (2001) 159-172 · Zbl 1006.37012 |
[2] | C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, P. Tosic, Garden of Eden and fixed point configurations in sequential dynamical systems, Proc. Int. Conf. on Discrete Models in Combinatorics, Computation and Geometry (DM-CCG), Paris, July 2-5, 2001; C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, R.E. Stearns, P. Tosic, Garden of Eden and fixed point configurations in sequential dynamical systems, Proc. Int. Conf. on Discrete Models in Combinatorics, Computation and Geometry (DM-CCG), Paris, July 2-5, 2001 · Zbl 1017.68055 |
[3] | Barrett, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of simulation II: sequential dynamical systems, Appl. Math. Comput., 107, 2-3, 121-136 (2000) · Zbl 1049.68149 |
[4] | Barrett, C. L.; Mortveit, H. S.; Reidys, C. M., Elements of a theory of simulation III: equivalence of SDS, Appl. Math. Comput., 122, 325-340 (2001) · Zbl 1050.68161 |
[5] | Barrett, C. L.; Reidys, C. M., Elements of a theory of simulation I: sequential CA over random graphs, Appl. Math. Comput., 98, 241-259 (1999) · Zbl 0927.68114 |
[6] | Jen, E., Cylindrical cellular automata, Comm. Math. Phys., 118, 569-590 (1988) · Zbl 0655.68060 |
[7] | Mortveit, H. S.; Reidys, C. M., Discrete, sequential dynamical systems, Discrete Math., 226, 281-295 (2001) · Zbl 1004.05056 |
[8] | Reidys, C. M., Acyclic orientations of random graphs, Adv. Appl. Math., 21, 181-192 (1998) · Zbl 0916.05062 |
[9] | Reidys, C. M., On acyclic orientations and SDS, Adv. Appl. Math., 27, 790-804 (2001) · Zbl 1017.68144 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.