Name
Abstract | ||
|---|---|---|
Overlap-free words are words over the alphabet A = {a, b} that do not contain factors of the form xvxvx, where x ∈ A and v ∈ A*. We analyze the asymptotic growth of the number un of overlapfree words of length n. We obtain explicit formulas for the minimal and maximal rates of growth of un in terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of one set of matrices of dimension 20. Using these descriptions we provide estimates of the rates of growth that are within 0.4% and 0.03% of their exact value. The best previously known bounds were within 11% and 3% respectively. We prove that un actually has the same growth for "almost all" n. This "average" growth is distinct from the maximal and minimal rates and can also be expressed in terms of a spectral quantity (the Lyapunov exponent). We use this expression to estimate it. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-3-540-78773-0_8 | LATIN |
Keywords | Field | DocType |
number un,asymptotic growth,overlap-free word,spectral characteristic,lower spectral radius,joint spectral radius,spectral quantity,lyapunov exponent,maximal rate,minimal rate,spectral radius | Discrete mathematics,Combinatorics,Spectral radius,Of the form,Matrix (mathematics),Joint spectral radius,Spectral line,Lyapunov exponent,Mathematics,Binary number,Alphabet | Conference |
Volume | ISSN | ISBN |
4957 | 0302-9743 | 3-540-78772-0 |
Citations | PageRank | References |
2 | 0.41 | 10 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Raphaël M. Jungers | 1 | 222 | 39.39 |
| Vladimir Yu. Protasov | 2 | 16 | 5.72 |
| Vincent D. Blondel | 3 | 1880 | 184.86 |