Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. Gardens of Eden and ...
Conference paper

Gardens of Eden and Fixed Points in Sequential Dynamical Systems

Christopher Barrett (1), Marry Hunt (2), Madhav Marathe (1), S. Ravi, Daniel Rosenkrantz (2), Richard Stearns (2), Predrag Tosic (3) (1)
(1) Los Alamos National Laboratory
(2) Department of Computer Science [Albany]
(3) Department of Computer Science
Download article
Open on HAL
Imported on
November 21, 2016
Published on
December 31, 2000
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AA, Discrete Models: Combinatorics, Computation, and Geometry (DM-CCG 2001)
Proceedings
DOI
10.46298/dmtcs.2294
License
https://about.hal.science/hal-authorisation-v1
Indicators
986
Views
941
Downloads

Gardens of Eden and Fixed Points in Sequential Dynamical Systems

Christopher Barrett (1), Marry Hunt (2), Madhav Marathe (1), S. Ravi, Daniel Rosenkrantz (2), Richard Stearns (2), Predrag Tosic (3) (1)
(1) Los Alamos National Laboratory
(2) Department of Computer Science [Albany]
(3) Department of Computer Science
Abstract
A class of finite discrete dynamical systems, called <b>Sequential Dynamical Systems</b> (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 <b>NP</b>-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.
Keywords
  • [INFO]Computer Science [cs]
  • [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC]
  • Discrete Dynamical Systems
  • Cellular Automata
  • Computational Complexity
Cited by

Source: OpenCitations

  • Agent-Based Computational Epidemiological Modeling

    Journal of the Indian Institute of Science

    Authors : Keith R. Bissett, Jose Cadena ORCID, Maleq Khan, Chris J. Kuhlman ORCID

    Journal reference : Volume 101, 2021, pp. 303-327

    DOI : 10.1007/s41745-021-00260-2

  • Analysis Problems for Sequential Dynamical Systems and Communicating State Machines

    OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information)

    Authors : Chris Barrett ORCID, Harry B. Hunt, Madhav V. Marathe ORCID, S. S. Ravi ORCID, Daniel J. Rosenkrantz ORCID, Richard E. Stearns ORCID

    Journal reference : Volume , 2001, pp. 159-172

    DOI : 10.1007/3-540-44683-4_15

  • Complexity of reachability problems for finite discrete dynamical systems

    Journal of Computer and System Sciences

    Authors : Christopher L. Barrett ORCID, Harry B. Hunt, Madhav V. Marathe ORCID, S.S. Ravi ORCID, Daniel J. Rosenkrantz ORCID, Richard E. Stearns ORCID

    Journal reference : Volume 72, 2006, pp. 1317-1345

    DOI : 10.1016/j.jcss.2006.03.006

  • ETS IV: Sequential dynamical systems: fixed points, invertibility and equivalence

    Applied Mathematics and Computation

    Authors : C.L. Barrett ORCID, H.S. Mortveit ORCID, C.M. Reidys ORCID

    Journal reference : Volume 134, 2002, pp. 153-171

    DOI : 10.1016/s0096-3003(01)00277-6

  • Concurrency vs. sequential interleavings in 1-D threshold cellular automata

    18th International Parallel and Distributed Processing Symposium, 2004. Proceedings.

    Authors : P. Tosic, Gul Agha ORCID

    Journal reference : Volume 9, 2004, pp. 179-186

    DOI : 10.1109/ipdps.2004.1303188

  • Cellular Automata Communication Models

    IGI Global eBooks

    Authors : Predrag T. Tošic

    Journal reference : Volume , 2012, pp. 271-290

    DOI : 10.4018/978-1-4666-1574-8.ch015

  • Computational Complexity Studies of Synchronous Boolean Finite Dynamical Systems

    Lecture notes in computer science

    Authors : Mitsunori Ogihara ORCID, Kei Uchizawa ORCID

    Journal reference : Volume , 2015, pp. 87-98

    DOI : 10.1007/978-3-319-17142-5_9

  • Solution to the predecessors and Gardens-of-Eden problems for synchronous systems over directed graphs

    Applied Mathematics and Computation

    Authors : Juan A. Aledo ORCID, Luis G. Diaz ORCID, Silvia Martinez, Jose C. Valverde ORCID

    Journal reference : Volume 347, 2018, pp. 22-28

    DOI : 10.1016/j.amc.2018.10.077

  • Predecessors and Gardens of Eden in sequential dynamical systems over directed graphs

    Applied Mathematics and Nonlinear Sciences

    Authors : Juan A. Aledo ORCID, Luis G. Diaz ORCID, Silvia Martinez, Jose C. Valverde ORCID

    Journal reference : Volume 3, 2018, pp. 593-602

    DOI : 10.2478/amns.2018.2.00046

  • Update sequence stability in graph dynamical systems

    Discrete and Continuous Dynamical Systems - S

    Authors : Matthew Macauley ORCID, Henning S. Mortveit

    Journal reference : Volume 4, 2011, pp. 1533-1541

    DOI : 10.3934/dcdss.2011.4.1533

  • Complexity of Inferring Local Transition Functions of Discrete Dynamical Systems

    Lecture notes in computer science

    Authors : Abhijin Adiga ORCID, Chris J. Kuhlman ORCID, Madhav V. Marathe ORCID, S. S. Ravi ORCID, Daniel J. Rosenkrantz ORCID, Richard E. Stearns ORCID

    Journal reference : Volume , 2015, pp. 21-34

    DOI : 10.1007/978-3-319-22360-5_3

  • Predecessor existence problems for finite discrete dynamical systems

    Theoretical Computer Science

    Authors : Chris Barrett ORCID, Harry B. Hunt, Madhav V. Marathe ORCID, S.S. Ravi ORCID, Daniel J. Rosenkrantz ORCID, Richard E. Stearns ORCID, Mayur Thakur ORCID

    Journal reference : Volume 386, 2007, pp. 3-37

    DOI : 10.1016/j.tcs.2007.04.026

  • On Simple Models of Associative Memory: Network Density Is Not Required for Provably Complex Behavior

    Lecture notes in computer science

    Authors : Predrag T. Tošić

    Journal reference : Volume , 2016, pp. 61-71

    DOI : 10.1007/978-3-319-47103-7_7

  • On Modeling and Analyzing Sparsely Networked Large-Scale Multi-agent Systems with Cellular and Graph Automata

    Lecture notes in computer science

    Authors : Predrag T. Tošić

    Journal reference : Volume , 2006, pp. 272-280

    DOI : 10.1007/11758532_38

  • Characterizing Configuration Spaces of Simple Threshold Cellular Automata

    Lecture notes in computer science

    Authors : Predrag T. Tosic, Gul A. Agha ORCID

    Journal reference : Volume , 2004, pp. 861-870

    DOI : 10.1007/978-3-540-30479-1_89

  • Graphical dynamical systems and their applications to bio-social systems

    International Journal of Advances in Engineering Sciences and Applied Mathematics

    Authors : Abhijin Adiga ORCID, Chris J. Kuhlman ORCID, Madhav V. Marathe ORCID, Henning S. Mortveit, S. S. Ravi ORCID, Anil Vullikanti ORCID

    Journal reference : Volume 11, 2018, pp. 153-171

    DOI : 10.1007/s12572-018-0237-6

  • Cellular Automata Communication Models

    International Journal of Natural Computing Research

    Authors : Predrag T. Tošic

    Journal reference : Volume 1, 2010, pp. 66-84

    DOI : 10.4018/jncr.2010070105

  • Cellular Automata for Distributed Computing: Models of Agent Interaction and Their Implications

    2005 IEEE International Conference on Systems, Man and Cybernetics

    Authors : P.T. Tosic

    Journal reference : Volume 4, 2006, pp. 3204-3209

    DOI : 10.1109/icsmc.2005.1571639

  • Synchronous Boolean Finite Dynamical Systems on Directed Graphs over XOR Functions

    Theory of Computing Systems

    Authors : M. Ogihara ORCID, K. Uchizawa ORCID

    Journal reference : Volume 67, 2022, pp. 569-591

    DOI : 10.1007/s00224-022-10111-x

  • Period-3 Orbits of Sequential Dynamical Systems and Their Relationship to Error-Correcting Codes over Finite Fields

    Graphs and Combinatorics

    Authors : Tuğçe Ulutaş, Mehmet Emin Köroğlu ORCID

    Journal reference : Volume 42, 2026, pp.

    DOI : 10.1007/s00373-025-03008-2

  • On Computational Complexity of Counting Fixed Points in Symmetric Boolean Graph Automata

    Lecture notes in computer science

    Authors : Predrag T. Tošić, Gul A. Agha ORCID

    Journal reference : Volume , 2005, pp. 191-205

    DOI : 10.1007/11560319_18

  • Modeling and Simulation of Large Biological, Information and Socio-Technical Systems: An Interaction Based Approach

    Interactive Computation

    Authors : Chris Barrett ORCID, Stephen Eubank ORCID, Madhav Marathe ORCID

    Journal reference : Volume , 2006, pp. 353-392

    DOI : 10.1007/3-540-34874-3_14

  • Agent Based Modeling, Mathematical Formalism for

    Encyclopedia of Complexity and Systems Science

    Authors : Reinhard Laubenbacher ORCID, Abdul S. Jarrah ORCID, Henning S. Mortveit, S.S. Ravi ORCID

    Journal reference : Volume , 2009, pp. 160-176

    DOI : 10.1007/978-0-387-30440-3_10

  • Agent-Based Modeling, Mathematical Formalism for

    Encyclopedia of Complexity and Systems Science

    Authors : Reinhard Laubenbacher ORCID, Abdul S. Jarrah ORCID, Henning S. Mortveit, S. S. Ravi ORCID

    Journal reference : Volume , 2013, pp. 1-25

    DOI : 10.1007/978-3-642-27737-5_10-5

  • Boolean Network Models of Collective Dynamics of Open and Closed Large-Scale Multi-agent Systems

    Lecture notes in computer science

    Authors : Predrag T. Tošić, Carlos Ordonez ORCID

    Journal reference : Volume , 2017, pp. 95-110

    DOI : 10.1007/978-3-319-64635-0_8

  • On Efficiency and Predictability of the Dynamics of Discrete-Time Boolean Networks

    Springer proceedings in complexity

    Authors : Predrag T. Tošić

    Journal reference : Volume , 2021, pp. 349-362

    DOI : 10.1007/978-3-030-67318-5_23
Preview
Loading PDF preview...