zbMATH — the first resource for mathematics

Gardens of Eden and fixed points in sequential dynamical systems. (English) Zbl 1017.68055
Discrete models: combinatorics, computation, and geometry. Proceedings of the 1st international conference (DM-CCG), Paris, France, July 2-5, 2001. Paris: Maison de l’Informatique et des Mathématiques Discrètes (MIMD), Discrete Math. Theor. Comput. Sci., Proc. AA, 95-110, electronic only (2001).
Summary: A class of finite discrete dynamical systems, called Sequential Dynamical Systems (SDSs), was proposed in 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 a previous paper. 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 that the 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.
For the entire collection see [Zbl 0985.00015].

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
Full Text: EMIS