On the number of restrictions determining a periodical sequence

G. R. Chelnokov

Modelirovanie i analiz informacionnyh sistem, Tome 14 (2007) no. 2, pp. 12-16

Résumé

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}\,. $$