Garden-of-Eden states and fixed points of monotone dynamical systems

arXiv1805.03163MaRDI QIDQ6301337FDOQ6301337

Christian M. Reidys, Ricky X. F. Chen, Henning S. Mortveit

Publication date: 8 May 2018

Abstract: In this paper we analyze Garden-of-Eden (GoE) states and fixed points of monotone, sequential dynamical systems (SDS). For any monotone SDS and fixed update schedule, we identify a particular set of states, each state being either a GoE state or reaching a fixed point, while both determining if a state is a GoE state and finding out all fixed points are generally hard. As a result, we show that the maximum size of their limit cycles is strictly less than $nchooselfloorn/2floor$. We connect these results to the Knaster-Tarski theorem and the LYM inequality. Finally, we establish that there exist monotone, parallel dynamical systems (PDS) that cannot be expressed as monotone SDS, despite the fact that the converse is always true.

Mathematics Subject Classification ID

Partial orders, general (06A06) Cellular automata (computational aspects) (68Q80) Discrete-time control/observation systems (93C55)

This page was built for publication: Garden-of-Eden states and fixed points of monotone dynamical systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301337)