


























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 ${n\choose \lfloor n/2 \rfloor}$. 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。