Volume: 410 • Number: 30-32 • Pages: 2823-2833

We study the number u(alpha)(n) of alpha-power-free binary words of length n, and the asymptotics of this number when n tends to infinity, for a fixed rational number alpha in (2, 7/3]. For any such alpha, we prove a structure result that allows us to describe constructively the sequence u(alpha)(n) as a 2-regular sequence. This provides an algorithm that computes the number u(alpha)(n) in logarithmic time, for fixed alpha. Then, generalizing recent results on 2(+)-free words, we describe the asymptotic behaviour of u(alpha)(n) in terms of joint spectral quantities of a pair of matrices that one can efficiently construct, given a rational number alpha. For alpha = 7/3, we compute the automaton and give sharp estimates for the asymptotic behaviour of u(alpha) (n). (C) 2009 Elsevier B.V. All rights reserved.