Gardens of Eden and Fixed Points in Sequential Dynamical Systems

Abstract : A class of finite discrete dynamical systems, called Sequential Dynamical Systems (SDSs), was proposed in [BMR99,BR99] as an abstract model of computer simulations. Here, we address some questions concerning two special types of the SDS configurations, namely Garden of Eden and Fixed Point configurations. A configuration $C$ of an SDS is a Garden of Eden (GE) configuration if it cannot be reached from any configuration. A necessary and sufficient condition for the non-existence of GE configurations in SDSs whose state values are from a finite domain was provided in [MR00]. We show this condition is sufficient but not necessary for SDSs whose state values are drawn from an infinite domain. We also present results that relate the existence of GE configurations to other properties of an SDS. A configuration $C$ of an SDS is a fixed point if the transition out of $C$ is to $C$ itself. The FIXED POINT EXISTENCE (or FPE) problem is to determine whether a given SDS has a fixed point. We show thatthe FPE problem is NP-complete even for some simple classes of SDSs (e.g., SDSs in which each local transition function is from the set{NAND, XNOR}). We also identify several classes of SDSs (e.g., SDSs with linear or monotone local transition functions) for which the FPE problem can be solved efficiently.
Type de document :
Communication dans un congrès
Cori, Robert and Mazoyer, Jacques and Morvan, Michel and Mosseri, Rémy. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), pp.95-110, 2001, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [25 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01182974
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 6 août 2015 - 11:58:25
Dernière modification le : mardi 7 mars 2017 - 15:00:03
Document(s) archivé(s) le : mercredi 26 avril 2017 - 09:46:37

Fichier

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

Identifiants

  • HAL Id : hal-01182974, version 1

Collections

Citation

Christopher Barrett, Marry Hunt, Madhav Marathe, S. Ravi, Daniel Rosenkrantz, et al.. Gardens of Eden and Fixed Points in Sequential Dynamical Systems. Cori, Robert and Mazoyer, Jacques and Morvan, Michel and Mosseri, Rémy. Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG 2001, 2001, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001), pp.95-110, 2001, DMTCS Proceedings. 〈hal-01182974〉

Partager

Métriques

Consultations de la notice

239

Téléchargements de fichiers

287