A generalized two-dimensional word is a function on Z2 with a finite number of values. The main problem we are interested in is periodicity of two-dimensional words satisfying some local conditions. Let A be a matrix of order n. The function φ : Z2 → Rn is a generalized centered function of radius r with the matrix A ifunder(∑, y ∈ Z2 : 0 < | y - x | ≤ r) - 35 pt φ (y) = φ (x) Afor every x ∈ Z2, where for x = (x1, x2), y = (y1, y2) we have | y - x | = | y1 - x1 | + | y2 - x2 |. We prove that every generalized centered function of radius r > 1 with a finite number of values is periodic. For r = 1 the existence of non-periodic generalized centered functions depends on the spectrum of the matrix A. Similar results are obtained for the infinite triangular and hexagonal grids.
| Original language | English |
|---|---|
| Pages (from-to) | 1315-1328 |
| Number of pages | 14 |
| Journal | Information and Computation |
| Volume | 207 |
| Issue number | 11 |
| DOIs | |
| State | Published - 1 Nov 2009 |
| Externally published | Yes |
ID: 41131335