A non-linear eroder in presence of one-sided noise

We study a class of cellular automata, that is random operators acting on normed measures on the space ${\{ 0,...,m\} ^{{Z^d}}}$ which can be presented as superpositions FrD, where D is a monotonie deterministe operator with uniform local interaction and Fr turns every component into the maximal sta...

Full description

Saved in:
Bibliographic Details
Published in:Brazilian journal of probability and statistics 2006-06, Vol.20 (1), p.1-12
Main Authors: de Menezes, Moisés Lima, Toom, André
Format: Article
Language:English
Subjects:
Cellular automata
Ergodic theory
Integers
Mathematical monotonicity
Mathematical vectors
Probabilities
Rectangles
Uniformity
Unsolvability
Zero
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study a class of cellular automata, that is random operators acting on normed measures on the space ${\{ 0,...,m\} ^{{Z^d}}}$ which can be presented as superpositions FrD, where D is a monotonie deterministe operator with uniform local interaction and Fr turns every component into the maximal state m with probability r independently from fate of other components. We call an island any configuration, whose set of components with non-zero state is finite, but not empty. We assume that D transforms the configuration "all zeros" into itself and say that D erodes an island x if there is t such that Dtx="all zeros". We say that D is an eroder if it erodes all islands. We say that D is a linear eroder if D erodes any island in a time which does not exceed a linear function of diameter of this island. Two special cases have been studied before: one with m = 1 and another with d = 1. In both cases necessary and sufficient conditions for an eroder have been presented and all eroders are linear. We find that as soon as m > 1 and d > 1, there are non-linear eroders. We concentrate our attention on one cellular automaton G with m = d = 2 and show that FrG is ergodic for all r > 0.
ISSN:0103-0752
2317-6199