Dynamic of cyclic automata over ℤ2

Martín Matamala, Eduardo Moreno

Research output: Contribution to journalArticlepeer-review

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 xQZ2 we define Fv(x)=s(xv) if the state s(xv) appears in one of the four neighbors of v in K and Fv(x)=xv otherwise. For xQZ2, such that {vZ2:xv≠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 k1,...,kn of non-negative integers there exists ynQZ2 such that |{vZ2:ynv≠0}|=O(k1 2+...+kn2) and the period of the vertex (0,0) is p·lcm{k1,...,kn}, for some even integer p.

Original languageEnglish
Pages (from-to)369-381
Number of pages13
JournalTheoretical Computer Science
Volume322
Issue number2
DOIs
StatePublished - 30 Aug 2004

Fingerprint

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

Cite this