Stable Multi-Level Monotonic Eroders



: Gács Péter, Törmä Ilkka

Publisher: SPRINGER

: 2022

: Theory of Computing Systems

: THEOR COMPUT SYST

: 66

: 1

: 322

: 353

: 32

: 1432-4350

: 1433-0490

DOI: https://doi.org/10.1007/s00224-021-10061-w

: https://link.springer.com/article/10.1007%2Fs00224-021-10061-w

: https://research.utu.fi/converis/portal/detail/Publication/68004308


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.

Last updated on 2024-26-11 at 20:10