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.

Язык оригиналаанглийский
Страницы (с-по)1315-1328
Число страниц14
ЖурналInformation and Computation
Том207
Номер выпуска11
DOI
СостояниеОпубликовано - 1 ноя 2009
Опубликовано для внешнего пользованияДа

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Информационные системы
  • Прикладные компьютерные науки
  • Математика и теория расчета

ID: 41131335