Stable Multi-Level Monotonic Eroders

09/25/2018
by   Péter Gács, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset