Quasiperiodicities in Fibonacci Strings

Abstract

We consider the problem of finding quasiperiodicities in Fibonacci strings. A factor $u$ of a string $y$ is a cover of $y$ if every letter of $y$ falls within some occurrence of $u$ in $y$. A string $v$ is a seed of $y$ if it is a cover of a superstring of $y$. A left seed of a string $y$ is a prefix of $y$ that is a cover of a superstring of $y$. Similarly, a right seed of a string $y$ is a suffix of $y$ that is a cover of a superstring of $y$. In this paper, we present some interesting results regarding quasiperiodicities in Fibonacci strings; we identify all covers, left/right seeds, and seeds of a Fibonacci string and all covers of a circular Fibonacci string.