Geodesic
Exact approximation of average subword complexity of finite random words over finite alphabet
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 14 (2008) no. 4, pp. 185-189
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

One of the ways to measure the random nature of a word is to evaluate the quantity of different subwords in it. Such a measure is called the subword complexity or complexity index. Direct interdependence between subword complexity and the state of chaos is intuitively obvious. In this article we develop an explicit formula suitable for approximation of the average subword complexity of the most chaotic–random–words. 
@article{TIMM_2008_14_4_a13,
     author = {E. E. Ivanko},
     title = {Exact approximation of average subword complexity of finite random words over finite alphabet},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {185--189},
     year = {2008},
     volume = {14},
     number = {4},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2008_14_4_a13/}
}
TY  - JOUR
AU  - E. E. Ivanko
TI  - Exact approximation of average subword complexity of finite random words over finite alphabet
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2008
SP  - 185
EP  - 189
VL  - 14
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/TIMM_2008_14_4_a13/
LA  - en
ID  - TIMM_2008_14_4_a13
ER  - 
%0 Journal Article
%A E. E. Ivanko
%T Exact approximation of average subword complexity of finite random words over finite alphabet
%J Trudy Instituta matematiki i mehaniki
%D 2008
%P 185-189
%V 14
%N 4
%U http://geodesic.mathdoc.fr/item/TIMM_2008_14_4_a13/
%G en
%F TIMM_2008_14_4_a13
E. E. Ivanko. Exact approximation of average subword complexity of finite random words over finite alphabet. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 14 (2008) no. 4, pp. 185-189. http://geodesic.mathdoc.fr/item/TIMM_2008_14_4_a13/

[1] Ilie L., Yu S., Zhang K., “Repetition complexity of words”, Computing and combinatorics, Lecture Notes in Comput. Sci., 2387, Springer, Berlin, 2002, 320–329 | MR | Zbl

[2] Janson S., Lonardi S., Szpankowski W., “On Average Sequence Complexity”, Theoret. Comput. Sci., 326:1–3 (2004), 213–227 | DOI | MR | Zbl

[3] Li M., Vitanyi P., An introduction to Kolmogorov complexity and its applications, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1993, 546 pp. | MR | Zbl

[4] Niederreiter H., “Some computable complexity measures for binary sequences”, Sequences and their appl., Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, 1999, 67–78 | MR | Zbl