Standard

On periodicity of generalized two-dimensional infinite words. / Puzynina, S. A.

In: Information and Computation, Vol. 207, No. 11, 01.11.2009, p. 1315-1328.

Research output: Contribution to journal › Article › peer-review

Harvard

Puzynina, SA 2009, 'On periodicity of generalized two-dimensional infinite words', Information and Computation, vol. 207, no. 11, pp. 1315-1328. https://doi.org/10.1016/j.ic.2009.03.005

APA

Puzynina, S. A. (2009). On periodicity of generalized two-dimensional infinite words. Information and Computation, 207(11), 1315-1328. https://doi.org/10.1016/j.ic.2009.03.005

Vancouver

Puzynina SA. On periodicity of generalized two-dimensional infinite words. Information and Computation. 2009 Nov 1;207(11):1315-1328. https://doi.org/10.1016/j.ic.2009.03.005

Author

Puzynina, S. A. / On periodicity of generalized two-dimensional infinite words. In: Information and Computation. 2009 ; Vol. 207, No. 11. pp. 1315-1328.

BibTeX

@article{7af703f5d87b414e98a9a34c2aff4092,
title = "On periodicity of generalized two-dimensional infinite words",
abstract = "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.",
keywords = "Bidimensional word, Equitable partition, Nivat's conjecture, Perfect coloring, Periodicity",
author = "Puzynina, {S. A.}",
year = "2009",
month = nov,
day = "1",
doi = "10.1016/j.ic.2009.03.005",
language = "English",
volume = "207",
pages = "1315--1328",
journal = "Information and Computation",
issn = "0890-5401",
publisher = "Elsevier",
number = "11",

}

RIS

TY - JOUR

T1 - On periodicity of generalized two-dimensional infinite words

AU - Puzynina, S. A.

PY - 2009/11/1

Y1 - 2009/11/1

N2 - 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.

AB - 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.

KW - Bidimensional word

KW - Equitable partition

KW - Nivat's conjecture

KW - Perfect coloring

KW - Periodicity

UR - http://www.scopus.com/inward/record.url?scp=70349729979&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2009.03.005

DO - 10.1016/j.ic.2009.03.005

M3 - Article

AN - SCOPUS:70349729979

VL - 207

SP - 1315

EP - 1328

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

IS - 11

ER -

ID: 41131335