Algorithm

Philosophy

Pure mathematics

Discrete mathematics

Materials science

Monotonic function

Theoretical computer science

Set (abstract data type)

Computer science

Simple (philosophy)

Automaton

Physics

Nanotechnology

Mathematics

Cellular automaton

Optics

Image (mathematics)

Characterization (materials science)

Epistemology

Mathematical analysis

Artificial intelligence

Combinatorics

Programming language

Noise (video)

Class (philosophy)

State (computer science)

Theory of Computing Systems

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.

Stable Multi-Level Monotonic Eroders