A1 Refereed original research article in a scientific journal
Stable Multi-Level Monotonic Eroders
Authors: Gács Péter, Törmä Ilkka
Publisher: SPRINGER
Publication year: 2022
Journal: Theory of Computing Systems
Journal acronym: THEOR COMPUT SYST
Volume: 66
Issue: 1
First page : 322
Last page: 353
Number of pages: 32
ISSN: 1432-4350
eISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-021-10061-w
Web address : 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