TY - JOUR
T1 - Dynamic of cyclic automata over ℤ2
AU - Matamala, Martín
AU - Moreno, Eduardo
N1 - Funding Information:
This work was partially supported by ECOS C00E03 (French–Chilean Cooperation), FONDAP on Applied Math and Fondecyt 1010442. ∗Corresponding author. Tel.: +56-2678-45-55; fax: +56-2688-38-21. E-mail addresses: [email protected] (M. Matamala), [email protected] (E. Moreno).
PY - 2004/8/30
Y1 - 2004/8/30
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=3843104627&partnerID=8YFLogxK
U2 - 10.1016/j.tcs.2004.03.018
DO - 10.1016/j.tcs.2004.03.018
M3 - Article
AN - SCOPUS:3843104627
SN - 0304-3975
VL - 322
SP - 369
EP - 381
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2
ER -