|
Diskretnyi Analiz i Issledovanie Operatsii, 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.
Received: 09.02.2009 Revised: 23.06.2010
Citation:
Ts. Ch.-D. Batueva, “A family of two-dimensional words with maximal pattern complexity $2k$”, Diskretn. Anal. Issled. Oper., 17:5 (2010), 3–14
Linking options:
https://www.mathnet.ru/eng/da620 https://www.mathnet.ru/eng/da/v17/i5/p3
|
Statistics & downloads: |
Abstract page: | 257 | Full-text PDF : | 66 | References: | 40 | First page: | 2 |
|