Overlap-free words are words over the binary alphabet A = a, b that do not contain factors of the form x v x v x, where x ∈ A and v ∈ A*. We analyze the asymptotic growth of the number un of overlap-free words of length n as n → ∞. We obtain explicit formulas for the minimal and maximal rates of growth of un in terms of spectral characteristics (the joint spectral subradius and the joint spectral radius) of certain sets of matrices of dimension 20 × 20. Using these descriptions we provide new estimates of the rates of growth that are within 0.4 % and 0.03 % of their exact values. The best previously known bounds were within 11 % and 3 %, respectively. We then prove that the value of un actually has the same rate of growth for "almost all" natural numbers 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. In order to obtain our estimates, we introduce new algorithms to compute the spectral characteristics of sets of matrices. These algorithms can be used in other contexts and are of independent interest. © 2009 Elsevier B.V. All rights reserved.

Overlap-free words and spectra of matrices

Protasov, Vladimir;
2009-01-01

Abstract

Overlap-free words are words over the binary alphabet A = a, b that do not contain factors of the form x v x v x, where x ∈ A and v ∈ A*. We analyze the asymptotic growth of the number un of overlap-free words of length n as n → ∞. We obtain explicit formulas for the minimal and maximal rates of growth of un in terms of spectral characteristics (the joint spectral subradius and the joint spectral radius) of certain sets of matrices of dimension 20 × 20. Using these descriptions we provide new estimates of the rates of growth that are within 0.4 % and 0.03 % of their exact values. The best previously known bounds were within 11 % and 3 %, respectively. We then prove that the value of un actually has the same rate of growth for "almost all" natural numbers 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. In order to obtain our estimates, we introduce new algorithms to compute the spectral characteristics of sets of matrices. These algorithms can be used in other contexts and are of independent interest. © 2009 Elsevier B.V. All rights reserved.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/123637
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 32
  • ???jsp.display-item.citation.isi??? 26
social impact