Computer Science – Discrete Mathematics
Scientific paper
2007-09-12
Computer Science
Discrete Mathematics
26 pages, 2 figures
Scientific paper
Overlap-free words are words over the binary alphabet $A=\{a, b\}$ that do not contain factors of the form $xvxvx$, where $x \in A$ and $v \in A^*$. We analyze the asymptotic growth of the number $u_n$ of overlap-free words of length $n$ as $ n \to \infty$. We obtain explicit formulas for the minimal and maximal rates of growth of $u_n$ in terms of spectral characteristics (the lower spectral radius and the joint spectral radius) of certain sets of matrices of dimension $20 \times 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 $u_n$ 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 spectral characteristics of sets of matrices. These algorithms can be used in other contexts and are of independent interest.
Blondel Vincent D.
Jungers Raphael M.
Protasov Vladimir Y.
No associations
LandOfFree
Overlap-free words and spectra of matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Overlap-free words and spectra of matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Overlap-free words and spectra of matrices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-22061