DOI

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 languageEnglish
Pages (from-to)1315-1328
Number of pages14
JournalInformation and Computation
Volume207
Issue number11
DOIs
StatePublished - 1 Nov 2009
Externally publishedYes

    Research areas

  • Bidimensional word, Equitable partition, Nivat's conjecture, Perfect coloring, Periodicity

    Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

ID: 41131335