On Some Special Classes of Sequential Dynamical Systems

Chris Barrett^{1}, Harry B. Hunt III^{2}, Madhav V. Marathe^{1}, S.S. Ravi^{2}, Daniel J. Rosenkrantz^{2}, and Richard E. Stearns^{2}

{barrett, marathe}@lanl.gov

{hunt, ravi, djr, res}@cs.albany.edu

Annals of Combinatorics 7 (4) p.381-408 December, 2003

Abstract:

Sequential Dynamical Systems
(SDSs) are mathematical models for analyzing simulation systems.
We investigate phase space properties of some special
classes of SDSs obtained by restricting the local transition functions used at the nodes.
We show that any SDS over the Boolean domain with symmetric
Boolean local transition functions can be efficiently simulated by
another SDS which uses only simple threshold and simple
inverted threshold functions, where the same threshold value
is used at each node and the underlying graph is *d*-regular
for some integer *d*. We establish tight or nearly tight upper and lower bounds on the number of steps needed for SDSs over the Boolean domain with *1-*, *2-* or
*3-*threshold functions at each of the nodes to reach a fixed point.
When the domain is a unitary semiring and each node computes a linear
combination of its inputs, we present a polynomial time algorithm to
determine whether such an SDS reaches a fixed point.
We also show (through an explicit construction) that
there are Boolean SDSs with the NOR function at each node such that
their phase spaces contain directed cycles whose length is exponential
in the number of nodes of the underlying graph of the SDS.

References:

1. C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, and R.E. Stearns, Analysis problems for sequential dynamical systems and communicating state machines, In: Proc. International Symposium on Mathematical Foundations of Computer Science, Marianske Lazne, Czech Republic, August 2001, Lecture Notes in Computer Science, Vol. 2136, Springer-Verlag, New York, 2001, pp. 159每172.

2. C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, and R.E. Stearns, Dichotomy results for reachability problems in sequential dynamical systems, preprint, 2002.

3. C.L. Barrett, H.B. Hunt III, M.V. Marathe, S.S. Ravi, D.J. Rosenkrantz, and R.E. Stearns, Reachability problems for sequential dynamical systems with threshold functions, Theoret. Comput. Sci. 295 (1?) (2003) 41每65.

4. C.L. Barrett, H. Mortveit, and C. Reidys, Elements of a theory of simulation II: sequential dynamical systems, Appl. Math. Comput. 107 (2?) (1999) 121每136.

5. C.L. Barrett, H. Mortveit, and C. Reidys, Elements of a theory of computer simulation III: equivalence of SDS, Appl. Math. Comput. 122 (2001) 325每340.

6. M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NPcompleteness, W.H. Freeman and Co., San Francisco, CA, 1979.

7. Z. Kohavi, Switching and Finite Automata Theory,McGraw-Hill Book Company, New York, NY, 1970.

8. R. Laubenbacher and B. Pareigis, Finite dynamical systems, Technical report, Department of Mathematical Sciences, New Mexico State University, Las Cruces, NM, 2000.

9. H. Mortveit and C. Reidys. Discrete sequential dynamical systems, Discrete Math. 226 (2001) 281每295.

10. C.H. Papadimitriou, Computational Complexity, Addison-Wesley, Reading, MA, 1994.

11. C. Reidys, Sequential dynamical systems: phase space properties, Adv. Appl. Math., to appear.

12. S. Wolfram, Ed., Theory and Applications of Cellular Automata, World Scientific, Singapore, 1986.