2020/12/22 by Yerim Song, Song, Yerim, Joshua A. Grochow +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #37B15 #68Q80 #68W05 #Algorithms and Data Compression #Cellular Automata and Applications #Cellular Automata and Lattice Gases (nlin.CG) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #FOS: Physical sciences #G.4 #Pattern Formation and Solitons (nlin.PS) #Statistical Mechanics (cond-mat.stat-mech)
paper · pdf · doi:10.48550/arxiv.2012.12153
openalex publication_date 2020/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 22N-time, and thus only allowed them to explore supercell sizes N ≤ 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.