RUS  ENG
Full version
JOURNALS // Diskretnyi Analiz i Issledovanie Operatsii // Archive

Diskretn. Anal. Issled. Oper., 2010 Volume 17, Issue 5, Pages 3–14 (Mi da620)

A family of two-dimensional words with maximal pattern complexity $2k$

Ts. Ch.-D. Batueva

Novosibirsk State University, Novosibirsk, Russia

Abstract: Maximal pattern complexity $p^*(k)$ is one of the counting functions over infinite words. In this paper we consider it over two-dimensional words. We construct an infinite family of two-dimensional words with the maximal pattern complexity $p^*(k)=2k$ for $k\in\mathbb N$. It is the minimum of maximal pattern complexity over two-dimensional and not two-periodic words. Bibliogr. 21.

Keywords: complexity, maximal pattern complexity, two-dimensional word, Toeplitz word.

UDC: 519.725

Received: 09.02.2009
Revised: 23.06.2010



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025