|
Modelirovanie i Analiz Informatsionnykh Sistem, 2007, Volume 14, Number 2, Pages 12–16
(Mi mais128)
|
|
|
|
On the number of restrictions determining a periodical sequence
G. R. Chelnokov Yaroslavl State University
Abstract:
We consider sequences $W$ of the period $u$ over an alphabet consisting of $l$ letters. It is required to determine unambiguously the sequence $W$ picking out words which are not subwords of the sequence. For $n\in\mathbb N$ we denote by $U_n$ the set of words $u$ of length $n$, which are not powers (i.e. are not represented in form $u=v^k$, $k>1$).
Let $T(u^\infty)$ be the minimal number of restrictions determining the sequence $u^\infty$.
Denote
$$
m_n=\max_{u\in U_n}T(u^\infty), \quad r_n=\min_{u\in U_n}T(u^\infty).
$$
We prove that
1. $m_n\le n(l-1)$.
The estimate is precise for infinite values of $n$. For instance, it takes place for a period which contains all the words of some given length $t$ (i.e. $n=l^t$).
2. $r_n\ge\log_2 n+1$.
3. There exists an increasing sequence $n_i$ so that
$$
r_{n_i}\le\log_{\phi}n_i, \quad\text{where}\quad \phi=\frac{1+\sqrt5}{2}\,.
$$
Received: 29.04.2007
Citation:
G. R. Chelnokov, “On the number of restrictions determining a periodical sequence”, Model. Anal. Inform. Sist., 14:2 (2007), 12–16
Linking options:
https://www.mathnet.ru/eng/mais128 https://www.mathnet.ru/eng/mais/v14/i2/p12
|
|