论文标题
改进的粗粒细胞自动机的算法
An Improved Algorithm for Coarse-Graining Cellular Automata
论文作者
论文摘要
在研究复杂系统中新兴现象的可预测性时，以色列和戈登菲尔德（Phys。Rev.Lett。，2004;Phys。Rev。E，2006）表明了如何进行粗粒（基础）细胞自动机（CA）。他们的算法找到超级电池尺寸$ n $的粗粒胶，以双重指定$ 2^{2^n} $ - 因此，只允许他们探索超级型超级尺寸$ n \ leq 4 $。在这里，我们介绍了一种新的，更高效的算法，用于在任意两个给定的CA之间找到粗粒，使我们能够系统地探索所有基本CA，其超级电池尺寸最高$ n = 7 $，并探索更大的超级电池大小的单个示例。我们的算法基于回溯搜索，类似于DPLL算法，具有单位传播的NP完整问题，布尔值令人满意。
In studying the predictability of emergent phenomena in complex systems, Israeli & Goldenfeld (Phys. Rev. Lett., 2004; Phys. Rev. E, 2006) showed how to coarse-grain (elementary) cellular automata (CA). Their algorithm for finding coarse-grainings of supercell size $N$ took doubly-exponential $2^{2^N}$-time, and thus only allowed them to explore supercell sizes $N \leq 4$. Here we introduce a new, more efficient algorithm for finding coarse-grainings between any two given CA that allows us to systematically explore all elementary CA with supercell sizes up to $N=7$, and to explore individual examples of even larger supercell size. Our algorithm is based on a backtracking search, similar to the DPLL algorithm with unit propagation for the NP-complete problem of Boolean Satisfiability.
