Correlations of minimal forbidden factors of the Fibonacci word

Abstract

If $u$ and $v$ are two words, the correlation of $u$ over $v$ is a binary word that encodes all possible overlaps between $u$ and $v$. This concept was introduced by Guibas and Odlyzko as a key element of their method for enumerating the number of words of length $n$ over a given alphabet that avoid a given set of forbidden factors. In this paper we characterize the pairwise correlations between the minimal forbidden factors of the infinite Fibonacci word.

11 pages