Volume 17, No 5, 2010, P. 3-14

UDC 519.725
Ts. Ch.-D. Batueva
A family of two-dimensional words with maximal pattern complexity 2k

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.

Batueva Tsyndyma Chimit-Dordjievna ¹
1. Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: cendema@ngs.ru