RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2010, том 17, выпуск 5, страницы 3–14 (Mi da620)

Серия двумерных слов с максимальной оконной сложностью $2k$

Ц. Ч.-Д. Батуева

Новосибирский гос. университет, Новосибирск, Россия

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

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

УДК: 519.725

Статья поступила: 09.02.2009
Переработанный вариант: 23.06.2010



Реферативные базы данных:


© МИАН, 2024