×
Karhumäki, Juhani; Shallit, Jeffrey

Polynomial versus exponential growth in repetition-free binary words. (English) Zbl 1065.68080

J. Comb. Theory, Ser. A 105, No. 2, 335-347 (2004).
Summary: It is known that the number of overlap-free binary words of length \(n\) grows polynomially, while the number of cubefree binary words grows exponentially. We show that the dividing line between polynomial and exponential growth is \(\frac{7}{3}\). More precisely, there are only polynomially many binary words of length \(n\) that avoid \(\frac{7}{3}\)-powers, but there are exponentially many binary words of length \(n\) that avoid \(\frac{7}{3}^{+}\)-powers. This answers an open question of Kobayashi from 1986.

Cited in 1 Review
Cited in 30 Documents

MSC:

68R15 Combinatorics on words

Keywords:

Repetition-free; Cubefree; Polynomial growth; Exponential growth; Fractional power
PDF BibTeX XML Cite
\textit{J. Karhumäki} and \textit{J. Shallit}, J. Comb. Theory, Ser. A 105, No. 2, 335--347 (2004; Zbl 1065.68080)
Full Text: DOI arXiv
  • logo of hbz
  • logo of WorldCat

Online Encyclopedia of Integer Sequences:

Number of 7/3+-power-free words over the alphabet {0,1}.

References:

[1] Allouche, J.-P.; Shallit, J., Automatic sequences: theory, applications, generalizations, (2003), Cambridge University Press Cambridge · Zbl 1086.11015
[2] Brandenburg, F.-J., Uniformly growing k-th power-free homomorphisms, Theoret. comput. sci, 23, 69-82, (1983) · Zbl 0508.68051
[3] Carpi, A., Overlap-free words and finite automata, Theoret. comput. sci, 115, 243-260, (1993) · Zbl 0784.68049
[4] Cassaigne, J., Counting overlap-free binary words, (), 216-225 · Zbl 0799.68153
[5] Dejean, F., Sur un théorème de thue, J. combin. theory. ser. A, 13, 90-99, (1972) · Zbl 0245.20052
[6] Dekking, F.M., On repetitions of blocks in binary sequences, J. combin. theory. ser. A, 20, 292-299, (1976) · Zbl 0325.05010
[7] Edlin, A.E., The number of binary cube-free words of length up to 47 and their numerical analysis, J. differential equations appl, 5, 353-354, (1999) · Zbl 0939.05007
[8] U. Grimm, Counting power-free words in two letters, Poster Presentation at Oberwohlfach Meeting on Aperiodic Order, May, 2001.
[9] Harju, T.; Karhumäki, J., Morphisms, (), 439-510
[10] Kfoury, A.-J., A linear-time algorithm to decide whether a binary word contains an overlap, RAIRO inform. théory appl, 22, 135-145, (1988) · Zbl 0645.68087
[11] Kobayashi, Y., Repetition-free words, Theoret. comput. sci, 44, 175-197, (1986) · Zbl 0596.20058
[12] Kobayashi, Y., Enumeration of irreducible binary words, Discrete appl. math, 20, 221-232, (1988) · Zbl 0673.68046
[13] Kolpakov, R.; Kucherov, G., Minimal letter frequency in n-th power-free binary words, (), 347-357 · Zbl 0941.68103
[14] Kolpakov, R.; Kucherov, G.; Tarannikov, Y., On repetition-free binary words of minimal density, Theoret. comput. sci, 218, 161-175, (1999) · Zbl 0916.68118
[15] A. Lepistö, A characterization of 2^{+}-free words over a binary alphabet, Master’s Thesis, University of Turku, Finland, 1995.
[16] Lothaire, M., Combinatorics on words, Encyclopedia of mathematics and its applications, Vol. 17, (1983), Addison-Wesley Reading, MA · Zbl 0514.20045
[17] Lothaire, M., Algebraic combinatorics on words, Encyclopedia of mathematics and its applications, Vol. 90, (2002), Cambridge University Press Cambridge · Zbl 1001.68093
[18] Noonan, J.; Zeilberger, D., The goulden – jackson cluster methodextensions, applications and implementations, J. differential equations appl, 5, 355-377, (1999) · Zbl 0935.05003
[19] Restivo, A.; Salemi, S., On weakly square free words, Bull. European assoc. theoret. comput. sci. no, 21, 49-56, (1983)
[20] Restivo, A.; Salemi, S., Overlap free words on two symbols, (), 198-206
[21] J. Shallit, Simultaneous avoidance of large squares and fractional powers in infinite binary words, Internat. J. Found. Comput. Sci., to appear, preprint, available at , 2003. · Zbl 1067.68119
[22] Shur, A.M., The structure of the set of cube-free Z-words in a two-letter alphabet, Izv. ross. akad. nauk ser. mat, 64, 4, 201-224, (2000), (in Russian) (English trans.: Izv. Math. 64 (2000) 847-871) · Zbl 0972.68131
[23] Y. Tarannikov, The minimal density of a letter in an infinite ternary square-free word is 0.2746⋯ . J. Integer Sequences 5 (2002) 02.2.2 (electronic). · Zbl 1121.11303
[24] A. Thue, Über unendliche Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906) 1-22 (Reprinted in: T. Nagell (Ed.), Selected Mathematical Papers of Axel Thue, Universitetsforlaget, Oslo, 1977, pp. 139-158).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.