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
1.
Novosibirsk State University,
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: cendema@ngs.ru
|