Dynamic of cyclic automata over Z(2)

Matamala M.; Moreno E.

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(k12+...+kn2) and the period of the vertex (0,0) is p·lcm{k1,...,kn}, for some even integer p. © 2004 Elsevier B.V. All rights reserved.

Más información

Título según WOS: Dynamic of cyclic automata over Z(2)
Título según SCOPUS: Dynamic of cyclic automata over ?2
Título de la Revista: THEORETICAL COMPUTER SCIENCE
Volumen: 322
Número: 2
Editorial: Elsevier
Fecha de publicación: 2004
Página de inicio: 369
Página final: 381
Idioma: English
DOI:

10.1016/j.tcs.2004.03.018

Notas: ISI, SCOPUS