Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.

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 :
Type de document :
Communication dans un congrès
Michel Morvan and Éric Rémila. Discrete Models for Complex Systems, DMCS'03, 2003, Lyon, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03), pp.69-80, 2003, DMTCS Proceedings
Domaine :

Littérature citée [10 références]

https://hal.inria.fr/hal-01183322
Contributeur : Coordination Episciences Iam <>
Soumis le : mercredi 12 août 2015 - 10:13:18
Dernière modification le : mardi 7 mars 2017 - 15:00:44
Document(s) archivé(s) le : vendredi 13 novembre 2015 - 11:35:23

Fichier

dmAB0106.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

• HAL Id : hal-01183322, version 1

Citation

Christopher L. Barrett, Harry Hunt, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, et al.. Predecessor and Permutation Existence Problems for Sequential Dynamical Systems.. Michel Morvan and Éric Rémila. Discrete Models for Complex Systems, DMCS'03, 2003, Lyon, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AB, Discrete Models for Complex Systems (DMCS'03), pp.69-80, 2003, DMTCS Proceedings. 〈hal-01183322〉

Métriques

Consultations de la notice

118

Téléchargements de fichiers