Geodesic
On the number of restrictions determining a periodical sequence
Modelirovanie i analiz informacionnyh sistem, Tome 14 (2007) no. 2, pp. 12-16 
G. R. Chelnokov. On the number of restrictions determining a periodical sequence. Modelirovanie i analiz informacionnyh sistem, Tome 14 (2007) no. 2, pp. 12-16. http://geodesic.mathdoc.fr/item/MAIS_2007_14_2_a2/
@article{MAIS_2007_14_2_a2,
     author = {G. R. Chelnokov},
     title = {On the number of restrictions determining a periodical sequence},
     journal = {Modelirovanie i analiz informacionnyh sistem},
     pages = {12--16},
     year = {2007},
     volume = {14},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MAIS_2007_14_2_a2/}
}
TY  - JOUR
AU  - G. R. Chelnokov
TI  - On the number of restrictions determining a periodical sequence
JO  - Modelirovanie i analiz informacionnyh sistem
PY  - 2007
SP  - 12
EP  - 16
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MAIS_2007_14_2_a2/
LA  - ru
ID  - MAIS_2007_14_2_a2
ER  - 
%0 Journal Article
%A G. R. Chelnokov
%T On the number of restrictions determining a periodical sequence
%J Modelirovanie i analiz informacionnyh sistem
%D 2007
%P 12-16
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/MAIS_2007_14_2_a2/
%G ru
%F MAIS_2007_14_2_a2

Voir la notice de l'article provenant de la source Math-Net.Ru

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

[1] V. A. Ufnarovskii, “Kombinatornye i asimptoticheskie metody v algebre”, Itogi nauki i tekhniki. Ser. Sovr. probl. matematiki. Fundamentalnye napravleniya, 57, VINITI, M., 1990, 5–177 | MR

[2] A. G. Kurosh, “Problemy teorii kolets, svyazannye s problemmoi Bernsaida o periodicheskikh gruppakh”, Izv. AN SSSR ser. mat., 5 (1941), 233–240

[3] A. Ya. Belov, V. V. Borisenko, V. N. Latyshev, “Monomialnye algebry”, Itogi nauki i tekhniki. Ser. Sovremennaya matematika i ee prilozheniya. Tematicheskie obzory, 26, VINITI, M., 2002, 35–214

[4] R. Uilson, Vvedenie v teoriyu grafov, Mir, M., 1977, 208 pp. | MR

[5] J.-P. Allouche, J. Shallit, Automatic sequences. Theory, applications, generalizations, Cambridge Univercity Press, Cambridge, 2003, 571 pp. | MR | Zbl

[6] J. P. Bell, “Examples in finite Gel'fand-Kirilov dimension”, J. Algebra, 263:1 (2003), 159–175 | DOI | MR | Zbl