Geodesic
Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits
Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2016), pp. 12-18 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The problem of complexity of word assembly is studied. The complexity of a word means the minimal number of concatenation operations sufficient to obtain this word in the basis of one-letter words over a finite alphabet $A$ (repeated use of obtained words is permitted). Let $L_A^c(n)$ be the maximum complexity of words of length $n$ over a finite alphabet $A$. In this paper we prove that $ L_A^c(n) = \frac n {\log_{|A|} n} \left( 1 + (2+o(1)) \frac {\log_2 \log_2 n}{\log_2 n} \right). $ 
@article{VMUMM_2016_2_a1,
     author = {V. V. Kochergin and D. V. Kochergin},
     title = {Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits},
     journal = {Vestnik Moskovskogo universiteta. Matematika, mehanika},
     pages = {12--18},
     year = {2016},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a1/}
}
TY  - JOUR
AU  - V. V. Kochergin
AU  - D. V. Kochergin
TI  - Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits
JO  - Vestnik Moskovskogo universiteta. Matematika, mehanika
PY  - 2016
SP  - 12
EP  - 18
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a1/
LA  - ru
ID  - VMUMM_2016_2_a1
ER  - 
%0 Journal Article
%A V. V. Kochergin
%A D. V. Kochergin
%T Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits
%J Vestnik Moskovskogo universiteta. Matematika, mehanika
%D 2016
%P 12-18
%N 2
%U http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a1/
%G ru
%F VMUMM_2016_2_a1
V. V. Kochergin; D. V. Kochergin. Revision of asymptotic behavior of the complexity of word assembly by concatenation circuits. Vestnik Moskovskogo universiteta. Matematika, mehanika, no. 2 (2016), pp. 12-18. http://geodesic.mathdoc.fr/item/VMUMM_2016_2_a1/

[1] Lupanov O.B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo MGU, M., 1984

[2] Lupanov O.B., “Ob odnom metode sinteza skhem”, Izv. vuzov. Radiofizika, 1:1 (1958), 120–140

[3] Lupanov O.B., “O sinteze kontaktnykh skhem”, Dokl. AN SSSR, 119:1 (1958), 23–26 | Zbl

[4] Lupanov O.B., “O slozhnosti realizatsii funktsii algebry logiki formulami”, Problemy kibernetiki, 3, Fizmatlit, M., 1960, 61–80

[5] Lozhkin S.A., “Otsenki vysokoi stepeni tochnosti dlya slozhnosti upravlyayuschikh sistem iz nekotorykh klassov”, Matematicheskie voprosy kibernetiki, 6, Nauka, M., 1996, 189–214 | MR

[6] Arnold A., Brlek S., “Optimal word chains for the Thue–Morse word”, Inform. and Comput., 83:2 (1989), 140–151 | DOI | MR | Zbl

[7] Merekin Yu.V., “Nizhnyaya otsenka slozhnosti dlya skhem konkatenatsii slov”, Diskretnyi analiz i issledovanie operatsii, 3:1 (1996), 52–56 | MR | Zbl

[8] Kochergin V.V., “O multiplikativnoi slozhnosti dvoichnykh slov s zadannym chislom edinits”, Matematicheskie voprosy kibernetiki, 8, Nauka, M., 1999, 63–76 | MR

[9] Potapov V.N., “Additivnaya slozhnost slov s ogranicheniyami na sostav podslov”, Diskretnyi analiz i issledovanie operatsii. Ser. 1, 11:1 (2004), 52–78 | MR | Zbl

[10] Strassen V., “Berechnungen in partiellen Algebren endlichen Typs”, Computing, 11 (1973), 181–196 | DOI | MR | Zbl

[11] Lupanov O.B., “Ob odnom podkhode k sintezu upravlyayuschikh sistem — printsipe lokalnogo kodirovaniya”, Problemy kibernetiki, 14, Nauka, M., 1965, 31–110

[12] Kholl M., Kombinatorika, Mir, M., 1970 | MR

[13] de Bruijn N.G., “A combinatorial problem”, Ned. Akad. Wetensch. Proc., 49 (1946), 758–764 | MR

[14] A. B. Ugolnikov (otv. red.), Konspekt lektsii O. B. Lupanova po kursu “Vvedenie v matematicheskuyu logiku”, Izd-vo TsPI pri mekh.-mat. f-te MGU, M., 2007