TWiki> CoWiki Web>AdditionalOpenProblems>GrowthRateofPowerFree (2011-07-20, JeffreyShallit) EditAttach

Dejean's conjecture (now a theorem) states that the largest power avoidable over a k-letter alphabet is given by RT(k), and RT(2) = 2, RT(3) = 7/4, RT(4) = 7/5, and RT(k) = k/(k-1) for k ≥ 5.

How many words of length n are there that avoid RT(k)^{+} powers? For k = 2 it is known that this number is bounded by a polynomial in n, and the same is true for exponents ≤ 7/3. For k = 3, 4 Ochem has proven that there are exponentially many words avoiding RT(k)^{+} powers. Kolpakov and Rao have announced a proof for 5 ≤ k ≤ 10. The cases k ≥ 11 seem to be open.

References:

A. M. Shur, Growth properties of power-free languages, in G. Mauri and A. Leporati, eds., *Developments in Language Theory*, 15th International Conference, DLT 2011, Lect. Notes in Comp. Sci., Vol. 6795, Springer, 2011, pp. 28-43.

-- JeffreyShallit - 20 Jul 2011

Edit | Attach | ~~Watch~~ | Print version | History: r1 | Backlinks | Raw View | Raw edit | More topic actions

Topic revision: r1 - 2011-07-20 - JeffreyShallit

Copyright © 2008-2023 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback