On Some Special Classes of Sequential Dynamical Systems |
| |
Authors: | Email author" target="_blank">Chris?BarrettEmail author Harry?B?Hunt III Madhav?V?Marathe S?S?Ravi Daniel?J?Rosenkrantz Richard?E?Stearns |
| |
Institution: | (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 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.AMS Subject Classification: 68Q10, 68Q17, 68Q80. |
| |
Keywords: | dynamical systems simple threshold functions lower and upper bounds linear functions cellular automata |
本文献已被 SpringerLink 等数据库收录! |
|