Refereed journal article or data article (A1)
Stable Multi-Level Monotonic Eroders
List of Authors: Gács Péter, Törmä Ilkka
Publisher: SPRINGER
Publication year: 2022
Journal: Theory of Computing Systems
Journal acronym: THEOR COMPUT SYST
Volume number: 66
Issue number: 1
Start page: 322
End page: 353
Number of pages: 32
ISSN: 1432-4350
eISSN: 1433-0490
DOI: http://dx.doi.org/10.1007/s00224-021-10061-w
URL: https://link.springer.com/article/10.1007%2Fs00224-021-10061-w
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/68004308
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 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.
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.
Downloadable publication This is an electronic reprint of the original article. |  |
UTU Research Portal