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 unof overlap-free words of length n. We obtain explicit formulas for the minimal and maximal rates of growth of unin 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 unactually 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. © 2008 Springer-Verlag Berlin Heidelberg.

Computing the growth of the number of overlap-free words with spectra of matrices

Protasov, Vladimir;
2008-01-01

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 unof overlap-free words of length n. We obtain explicit formulas for the minimal and maximal rates of growth of unin 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 unactually 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. © 2008 Springer-Verlag Berlin Heidelberg.
2008
3540787720
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/123721
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact