## Abstract

Let K be the two-dimensional grid. Let q be an integer greater than 1 and let Q={0,...,q-1}. Let s:Q→Q be defined by s(α)=(α+1)modq, ∀αQ. In this work we study the following dynamic F on Q ^{Z2}. For xQ^{Z2} we define F_{v}(x)=s(x_{v}) if the state s(x_{v}) appears in one of the four neighbors of v in K and F_{v}(x)=x_{v} otherwise. For xQ^{Z2}, such that {vZ^{2}:x_{v}≠0} is finite we prove that there exists a finite family of cycles such that the period of every vertex of K divides the lcm of their lengths. This is a generalization of the same result known for finite graphs. Moreover, we show that this upper bound is sharp. We prove that for every n≥1 and every collection k_{1},...,k_{n} of non-negative integers there exists y^{n}Q^{Z2} such that |{vZ^{2}:y^{n}_{v}≠0}|=O(k_{1} ^{2}+...+k_{n}^{2}) and the period of the vertex (0,0) is p·lcm{k_{1},...,k_{n}}, for some even integer p.

Original language | English |
---|---|

Pages (from-to) | 369-381 |

Number of pages | 13 |

Journal | Theoretical Computer Science |

Volume | 322 |

Issue number | 2 |

DOIs | |

State | Published - 30 Aug 2004 |

## Fingerprint

Dive into the research topics of 'Dynamic of cyclic automata over ℤ^{2}'. Together they form a unique fingerprint.