Том 17, номер 5, 2010 г., Стр. 3-14

УДК 519.725
Батуева Ц. Ч.-Д.
Серия двумерных слов с максимальной оконной сложностью 2k

Аннотация:
Максимальная оконная сложность $p^*(k)$ – это одна из подсчитывающих функций, сопоставляемых бесконечному слову. Эта функция рассматривается над двумерными словами. Построена новая серия бесконечных двумерных слов, для которых достигается минимальный рост данной функции для слов, не являющихся периодическими по всем направлениям: $p^*(k)=2k$ для всех $k\in\mathbb N$.
Библиогр. 21.

Ключевые слова: сложность, максимальная оконная сложность, слово Тёплица, двумерное слово.

Батуева Цындыма Чимит-Доржиевна ¹
1. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: cendema@ngs.ru

Статья поступила 9 февраля 2009 г.
Исправленный вариант — 23 июня 2010 г.