<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue4" %>
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
Annals of Combinatorics 7 (4) p.381-408 December, 2003
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.

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.