| Affiliation: | (1) MS M997, Los Alamos National Laboratory, P.O. Box 1663, 87545 Los Alamos, NM, USA;(2) Department of Computer Science, University at Albany, 12222 Albany, NY, USA |
| Abstract: | Sequential Dynamical Systems (SDSs) are mathematical models for analyzing simulationsystems. We investigate phase space properties of some special classes of SDSs obtainedby restricting the local transition functions used at the nodes. We show that any SDS over theBoolean domain with symmetric Boolean local transition functions can be efficiently simulatedby another SDS which uses only simple threshold and simple inverted threshold functions, wherethe same threshold value is used at each node and the underlying graph is d-regular for some integerd. We establish tight or nearly tight upper and lower bounds on the number of steps neededfor SDSs over the Boolean domain with 1-, 2- or 3-threshold functions at each of the nodes toreach a fixed point. When the domain is a unitary semiring and each node computes a linearcombination of its inputs, we present a polynomial time algorithm to determine whether such anSDS reaches a fixed point. We also show (through an explicit construction) that there are BooleanSDSs with the NOR function at each node such that their phase spaces contain directed cycleswhose length is exponential in the number of nodes of the underlying graph of the SDS.AMS Subject Classification: 68Q10, 68Q17, 68Q80. |
