A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Stable Multi-Level Monotonic Eroders
Tekijät: Gács Péter, Törmä Ilkka
Kustantaja: SPRINGER
Julkaisuvuosi: 2022
Journal: Theory of Computing Systems
Lehden akronyymi: THEOR COMPUT SYST
Vuosikerta: 66
Numero: 1
Aloitussivu: 322
Lopetussivu: 353
Sivujen määrä: 32
ISSN: 1432-4350
eISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-021-10061-w
Verkko-osoite: https://link.springer.com/article/10.1007%2Fs00224-021-10061-w
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/68004308
Tiivistelmä
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.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali