Stable multi-level monotonic eroders
Files
First author draft
Date
2018
DOI
Authors
Gács, Péter
Törmä, Ilkka
Version
First author draft
OA Version
Citation
Péter Gács, Ilkka Törmä. 2018. "Stable Multi-Level Monotonic Eroders.." CoRR, Volume abs/1809.09503
Abstract
Eroders are monotonic cellular automata with a linearly ordered state set that eventually wipe out any finite island of nonzero states. One-dimensional eroders were studied by Gal’perin in the 1970s, who presented a simple combinatorial characterization of the class. The multidimensional case has been studied by Toom and others, but no such characterization has been found. We prove a similar characterization for those one-dimensional monotonic cellular automata that are eroders even in the presence of random noise.