CLR cover

Problem 56: Comparing Suffixes of a Fibonacci Word

The structure of Fibonacci words, like that of Thue-Morse words, is an example of a situation in which some algorithms can be optimised to run in logarithmic time with respect to the length of words. The problem is concerned with a fast lexicographic comparison between two suffixes of a finite Fibonacci word, which shows such a phenomenon.

We deal with a slightly shortened version of Fibonacci words to simplify arguments. Let $\gib_n$ be the $n$th Fibonacci word $\fib_n$ with the last two letters deleted, that is, $\gib_n = \fib_n\{\sa{a},\sa{b}\}^{-2}$, for $n \geq 2$. Let also $\suf(k,n)$ be the $k$th suffix $\gib_n[k\dd |\gib_n|-1]$ of $\gib_n$.

The comparison between suffixes of $\gib_n$ is efficiently reduced to the comparison of their compact representation of logarithmic length implied by their logarithmic-size decomposition (property below). Factors of the decomposition are the reverse $R_n=\fib_n^\mathrm{R}$ of Fibonacci words. The first factors are $R_0=\sa{a}$, $R_1=\sa{ba}$, $R_2=\sa{aba}$ and $R_3=\sa{baaba}$. Observe that $R_{n+2}=R_{n+1}R_n$ and $R_n$ starts with the letter $\sa{a}$ if and only if $n$ is even.

Property

For $n\gt 2$, $\suf(k,n)$ uniquely factorises as $R_{i_0}R_{i_1}\cdots R_{i_m}$, where $i_0\in \{0,1\}$ and $i_{t}\in \{i_{t-1}+1,\,i_{t-1}+2\}$ for $t=1,\dots,m$.

Related to the factorisation let $\mathcal{R}_n(k) = (i_0,i_1,\dots,i_m)$.

  1. Show how to compare any two suffixes of $\gib_n = \fib_n\{\sa{a},\sa{b}\}^{-2}$ in time $O((\log |\fib_n|)^2)$.
  2. Improve the running time to $O(\log |\fib_n|)$.
For (A) use the algorithm of Problem 6.

References

  • W. Rytter. The structure of subword graphs and suffix trees of Fibonacci words. Theor. Comput. Sci., 363(2):211-223, 2006.
  • B. Walczak. A simple representation of subwords of the Fibonacci word. Inf. Process. Lett., 110(21):956-960, 2010.