2018/09/25 by Péter Gács, Gács, Péter, Ilkka Törmä +1 · 3 citations
Computer Science · Mathematics · #37B15 #60J05 #60K35 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR) #cs.DM #math.PR #msc:37B15 #msc:60J05 #msc:60K35
paper · pdf · doi:10.48550/arxiv.1809.09503
32 pages, 9 figures
arxiv created 2018/09/25 · arxiv updated 2018/09/26
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 multi-dimensional 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.