Geodesic
Growth rates of power-free languages
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 9 (2009), pp. 82-88.

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

We propose a new fast algorithm for calculating the growth rate of complexity for regular languages. Based on this algorithm, we develop an efficient universal method of estimating the upper bound of the growth rates for power-free languages. Through extensive computer-assisted studies we sufficiently improve all known upper bounds for growth rates of such languages, obtain a lot of new bounds, and discover some general regularities.
Keywords: power-free languages, regular languages, combinatorial complexity, growth rate. 
@article{IVM_2009_9_a8,
     author = {A. M. Shur},
     title = {Growth rates of power-free languages},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {82--88},
     publisher = {mathdoc},
     number = {9},
     year = {2009},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2009_9_a8/}
}
TY  - JOUR
AU  - A. M. Shur
TI  - Growth rates of power-free languages
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2009
SP  - 82
EP  - 88
IS  - 9
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2009_9_a8/
LA  - ru
ID  - IVM_2009_9_a8
ER  - 
%0 Journal Article
%A A. M. Shur
%T Growth rates of power-free languages
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2009
%P 82-88
%N 9
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2009_9_a8/
%G ru
%F IVM_2009_9_a8
A. M. Shur. Growth rates of power-free languages. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 9 (2009), pp. 82-88. http://geodesic.mathdoc.fr/item/IVM_2009_9_a8/

[1] Thue A., “Über unendliche Zeichenreihen”, Kra. Vidensk. Selsk. Skrifter. I. Mat. Nat. Kl., 7 (1906), 1–22

[2] Berstel J., Karhumäki J., “Combinatorics on words: a tutorial”, Bull. Eur. Assoc. Theor. Comput. Sci., 2003, no. 79, 178–228 | MR

[3] Brandenburg F.-J., “Uniformly growing $k$-th power free homomorphisms”, Theor. Comput. Sci., 23:1 (1983), 69–82 | DOI | MR | Zbl

[4] Restivo A., Salemi S., “Overlap-free words on two symbols”, Lect. Notes Comp. Sci., 192, 1985, 198–206 | MR | Zbl

[5] Edlin A., “The number of binary cube-free words of length up to 47 and their numerical analysis”, J. Diff. Eq. and Appl., 5:4–5 (1999), 153–154 | MR

[6] Karhumäki J., Shallit J., “Polynomial versus exponential growth in repetition-free binary words”, J. Combin. Theory. Ser. A, 105:2 (2004), 335–347 | DOI | MR | Zbl

[7] Kobayashi Y., “Enumeration of irreducible binary words”, Discr. Appl. Math., 20:3 (1988), 221–232 | DOI | MR | Zbl

[8] Kolpakov R., “On the number of repetition-free words”, Electron. proc. of Workshop on words and automata (WOWA' 06), St.-Petersburg, 2006, # 6

[9] Ochem P., Reix T., “Upper bound on the number of ternary square-free words”, Electron. proc. of Workshop on words and automata (WOWA' 06), St.-Petersburg, 2006, # 8

[10] Richard C., Grimm U., “On the entropy and letter frequencies of ternary square-free words”, Electronic J. Combinatorics, 11:1 (2004), RP14 | MR

[11] Kobayashi Y., “Repetition-free words”, Theor. Comp. Sci., 44:2 (1986), 175–197 | DOI | Zbl

[12] Shur A. M., “Growth rates of complexity of power-free languages”, Theor. Comp. Sci., 2008, (submitted) | MR

[13] Tsvetkovich D. M., Dub M., Zakhs Kh., Spektry grafov. Teoriya i primenenie, Nauk. dumka, Kiev, 1984, 384 pp. | MR

[14] Gantmakher F. R., Teoriya matrits, Nauka, M., 1988, 552 pp. | MR | Zbl

[15] Crochemore M., Mignosi F., Restivo A., “Automata and forbidden words”, Inform. Proc. Lett., 67:3 (1998), 111–117 | DOI | MR

[16] Godsil C. D., Algebraic combinatorics, Chapman and Hall, New York, 1993, 382 pp. | Zbl