Computing Aggregate Properties of Preimages for 2D Cellular Automata

Autor:	Beer, Randall D.
Rok vydání:	2017
Předmět:	Nonlinear Sciences - Cellular Automata and Lattice Gases
Zdroj:	Chaos 27:111104 (2017)
Druh dokumentu:	Working Paper
DOI:	10.1063/1.5006143
Popis:	Computing properties of the set of precursors of a given configuration is a common problem underlying many important questions about cellular automata. Unfortunately, such computations quickly become intractable in dimension greater than one. This paper presents an algorithm --- incremental aggregation --- that can compute aggregate properties of the set of precursors exponentially faster than na{\"i}ve approaches. The incremental aggregation algorithm is demonstrated on two problems from the two-dimensional binary Game of Life cellular automaton: precursor count distributions and higher-order mean field theory coefficients. In both cases, incremental aggregation allows us to obtain new results that were previously beyond reach.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1711.04563 Zobrazit plný text záznamu View this record from Arxiv