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.