Computing Directional Galperin’s Rates

Abstract

Elements of the d-dimensional real space Rd are called points. Maps x : Rd M are called configurations, where M  {0, 1, 2}. Any configuration x is determined by its components xp for all points p  R d. The configuration all of whose components are zeros is called “all zeros”. Two configurations x and y are called close to each other if the set {p  Rd : xp 6 yp} is bounded. A configuration is called an island if it is close to “all zeros”. The set of configurations is denoted by Ω  MR d . Any map from Ω to Ω is called an operator. We say that an operator D erodes an island x if there is a natural t such that xDt (the result of t iterative applications of D to x) is “all zeros”. We call an operator D an eroder if it erodes all islands. Galperin have obtained an eroder criteria for one-dimensional cellular automata by using his left and right rates [1]. Galperin found a way of computing his rates [2] in the discrete space, but he presented no detailed routine or implementation for computing them. Later de Santana generalized these rates introducing the directinal Galperin’s rates. Directional Galperin’s rates were employed in studying erodicity of two-dimensional cellular automata [5]. Here we present an algoritm for computing Galperin’s rates. Furthermore, from this algorithm we can compute some directional Galperin’s rates.