Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.Report as inadecuate




Predecessor and Permutation Existence Problems for Sequential Dynamical Systems. - Download this document for free, or read online. Document in PDF available to download.

1 NISAC - National Infrastructure Simulation and Analysis Center 2 CS - Department of Computer Science Albany

Abstract : A class of finite discrete dynamical systems, called Sequential Dynamical Systems SDSs, was introduced in BR99 as a formal model for analyzing simulation systems. Here, we address the complexity of two basic problems and their generalizations for SDSs.Given an SDS $\mathcal{S}$ and a configuration $\mathcal{C}$, the PREDECESSOR EXISTENCE or PRE problem is to determine whether there is a configuration $\mathcal{C}-$ such that $\mathcal{S}$ has a transition from $\mathcal{C}-$ to $\mathcal{C}$. Our results provide separations between efficiently solvable and computationally intractable instances of the PRE problem. For example, we show that the PRE problem can be solved efficiently for SDSs with Boolean state values when the node functions are symmetric and the underlying graph is of bounded tree width. In contrast, we show that allowing just one non-symmetric node function renders the problem $\mathbf{NP}$-complete even when the underlying graph is a star which has a tree width of 1. 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.Given two configurations $\mathcal{C}$ and $\mathcal{C}-$ of a partial SDS $\mathcal{S}$, the PERMUTATION EXISTENCE or PME problem is to determine whether there is a permutation of nodes such that $\mathcal{S}$ has a transition from $\mathcal{C}-$ to $\mathcal{C}$ in one step. We show that the PME problem is $\mathbf{NP}$-complete even when the function associated with each node is a simple-threshold function. We also show that the problem can be solved efficiently for SDSs whose underlying graphs are of bounded degree and bounded tree width. We consider a generalized version GEN-PME of the PME problem and show that the problem is $\mathbf{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.

Keywords : Computational Complexity Discrete Dynamical Systems Cellular Automata Predecessor Existence Permutation Existence





Author: Christopher L. Barrett - Harry Hunt - Madhav V. Marathe - S. S. Ravi - Daniel J. Rosenkrantz - Richard E. Stearns -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents