On the number of alpha-power-free binary words for 2 < alpha <= 7/3
(2009) Theoretical Computer Science — Vol. 410, n° 30-32, p. 2823-2833 (2009)
Files
pdfdocument.pdf
Restricted Access - Adobe PDF
- 809.41 KB
Details
- Authors
- Abstract
- 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.
- Affiliations
Citations
Blondel, V., Cassaigne, J., & Jungers, R. (2009). On the number of alpha-power-free binary words for 2 < alpha <= 7/3. Theoretical Computer Science, 410(30-32), 2823-2833. https://doi.org/10.1016/j.tcs.2009.01.031 (Original work published 2009)