Gardens of Eden and Fixed Points in Sequential Dynamical Systems
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 Fi...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2001-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2294/pdf |
| _version_ | 1797270606258896896 |
|---|---|
| author | Christopher Barrett Marry Hunt Madhav Marathe S. Ravi Daniel Rosenkrantz Richard Stearns Predrag Tosic |
| author_facet | Christopher Barrett Marry Hunt Madhav Marathe S. Ravi Daniel Rosenkrantz Richard Stearns Predrag Tosic |
| author_sort | Christopher Barrett |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:06:56Z |
| format | Article |
| id | doaj.art-1ab9de6f84044b29b7d2dfa1a77a8113 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:06:56Z |
| publishDate | 2001-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-1ab9de6f84044b29b7d2dfa1a77a81132024-03-07T14:27:42ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502001-01-01DMTCS Proceedings vol. AA,...Proceedings10.46298/dmtcs.22942294Gardens of Eden and Fixed Points in Sequential Dynamical SystemsChristopher Barrett0Marry Hunt1Madhav Marathe2S. RaviDaniel Rosenkrantz3Richard Stearns4Predrag Tosic5Los Alamos National LaboratoryDepartment of Computer Science [Albany]Los Alamos National LaboratoryDepartment of Computer Science [Albany]Department of Computer Science [Albany]Los Alamos National LaboratoryA 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.https://dmtcs.episciences.org/2294/pdfcomputational complexitycellular automatadiscrete dynamical systems[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] |
| spellingShingle | Christopher Barrett Marry Hunt Madhav Marathe S. Ravi Daniel Rosenkrantz Richard Stearns Predrag Tosic Gardens of Eden and Fixed Points in Sequential Dynamical Systems Discrete Mathematics & Theoretical Computer Science computational complexity cellular automata discrete dynamical systems [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] |
| title | Gardens of Eden and Fixed Points in Sequential Dynamical Systems |
| title_full | Gardens of Eden and Fixed Points in Sequential Dynamical Systems |
| title_fullStr | Gardens of Eden and Fixed Points in Sequential Dynamical Systems |
| title_full_unstemmed | Gardens of Eden and Fixed Points in Sequential Dynamical Systems |
| title_short | Gardens of Eden and Fixed Points in Sequential Dynamical Systems |
| title_sort | gardens of eden and fixed points in sequential dynamical systems |
| topic | computational complexity cellular automata discrete dynamical systems [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] |
| url | https://dmtcs.episciences.org/2294/pdf |
| work_keys_str_mv | AT christopherbarrett gardensofedenandfixedpointsinsequentialdynamicalsystems AT marryhunt gardensofedenandfixedpointsinsequentialdynamicalsystems AT madhavmarathe gardensofedenandfixedpointsinsequentialdynamicalsystems AT sravi gardensofedenandfixedpointsinsequentialdynamicalsystems AT danielrosenkrantz gardensofedenandfixedpointsinsequentialdynamicalsystems AT richardstearns gardensofedenandfixedpointsinsequentialdynamicalsystems AT predragtosic gardensofedenandfixedpointsinsequentialdynamicalsystems |