On Some Special Classes of Sequential Dynamical Systems

c Birkh¨auser Verlag, Basel, 2003

Annals of Combinatorics 7 (2003) 381-408

Annals of Combinatorics

0218-0006/03/040381-28 DOI 10.1007/s00026-003-0193-z

On Some Special Classes of Sequential Dynamical Systems Chris Barrett1∗ , Harry B. Hunt III2† , Madhav V. Marathe1∗ , S.S. Ravi2† , Daniel J. Rosenkrantz2, and Richard E. Stearns2 1Los Alamos National Laboratory, MS M997, P.O. Box 1663, Los Alamos, NM 87545, USA

{barrett, marathe}@lanl.gov 2Department of Computer Science, University at Albany, Albany, NY 12222, USA

{hunt, ravi, djr, res}@cs.albany.edu Received September 3, 2002 AMS Subject Classification: 68Q10, 68Q17, 68Q80 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. Keywords: dynamical systems, simple threshold functions, lower and upper bounds, linear functions, cellular automata

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. ∗ †

The work was supported by the Department of Energy under Contract W-7405-ENG-36. Part of the work was done while the authors were visiting the Basic and Applied Simulation Sciences Group (D-2) of the Los Alamos National Laboratory. The authors from the University at Albany were also supported by NSF Grants CCR-97-34936 and CCR-01-05536.

381

382

C. Barrett et al.

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–3) (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–3) (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 NP-completeness, 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.