# Predecessor and permutation existence problems for sequential dynamical systems [electronic resource].

- Published:
- Washington, D.C. : United States. Dept. of Energy, 2001.

Oak Ridge, Tenn. : Distributed by the Office of Scientific and Technical Information, U.S. Dept. of Energy. - Physical Description:
- 25 pages : digital, PDF file
- Additional Creators:
- Los Alamos National Laboratory, United States. Department of Energy, and United States. Department of Energy. Office of Scientific and Technical Information

##### Access Online

- Restrictions on Access:
- Free-to-read Unrestricted online access
- Summary:
- Motivated by the aim to build computer simulations for large scale systems [BMR99, BR99], we study a class of finite discrete dynamical systems called Sequential Dynamical Systems (SDSs). An SDS S is a triple (G, F, π), where (i) G(V, E) is an undirected graph with n nodes with each node having a 1-bit state, (ii) F = {l_brace}f₁, f₂, ..., f{sub n}{r_brace}, with f{sub i} denoting a symmetric Boolean function associated with node v{sub i} and (iii) π is a permutation of (or total order on) the nodes in V. A configuration of an SDS is a bit vector (b₁, b₂, ..., b{sub n}), where b{sub i} is the value of the state of node v{sub i}. A single SDS transition from one configuration to another is obtained by updating the states of the nodes by evaluating the function associated with each of them in the order given by π. Here, we address the complexity of two problems for SDSs. Given an SDS S and a configuration C, the PREDECESSOR EXISTENCE (or PRE) problem is to determine whether there is a configuration C′ such that S goes from C′ to C in one step. We show that the PRE problem NP-complete for several simple classes of SDSs (e.g. SDSs for which the set of node functions is {l_brace}AND, OR{r_brace}, SDSs whose underlying graphs are planar). We also identify several classes of SDSs for which the PRE problem can be solved efficiently (e.g. SDSs where each node function is from {l_brace}OR, NOR{r_brace} or {l_brace}AND, NAND{r_brace} or {l_brace}XOR, XNOR{r_brace}). We also show that the PRE problem is solvable in polynomial time when the function at each node is linear or when the underlying graph G is of bounded treewidth. Many of the easiness results extend to the case where we want to find an ancestor configuration that precedes a given configuration by a polynomial number of steps. Given the underlying graph G(V, E), and two configurations C and C′ of an SDS S, the PERMUTATION EXISTENCE (or PME) problem is to determine whether there is a permutation of nodes that takes S from C′ to C in one step. We show that the PME problem is NP-complete even when the function associated with each node is a simple-threshold function. We also show that a generalized version of the PME (GEN-PME) problem is NP-complete for SDSs where each node function is NOR and the underlying graph has a maximum node degree of 3. When each node computes the OR function or when each node computes the AND function, we show that the GEN-PME problem is solvable in polynomial time. Our results extend some of the earlier results by Sutner [Su95] and Green [Gr87] on the complexity of the PREDECESSOR EXISTENCE problem for 1-dimensional cellular automata.
- Report Numbers:
- E 1.99:la-ur-01-0668

E 1.99: la-ur-01-668

la-ur-01-668

la-ur-01-0668 - Subject(s):
- Note:
- Published through SciTech Connect.

01/01/2001.

"la-ur-01-0668"

" la-ur-01-668"

"Submitted to: International Conference on Symbolic and Algebraic Computations, University of Western Ontario, London, Ontario, Canada, January 2001.".

Hunt, H. B.; Barrett, C. L.; Stearns, R. E.; Marathe, M. V.; Ravi, S. S.; Rosenkrantz, D. J.

View MARC record | catkey: 14347272