A characterization of the squares in a Fibonacci string

✍ Scribed by Costas S. Iliopoulos; Dennis Moore; W.F. Smyth

• Book ID: 104326195
• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 675 KB
• Volume: 172
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00141-7

✦ Synopsis

A (finite) Fibonacci string F, is defined as follows: FO = b, FI = a; for every integer n 2 2, F,, = Fn_~Fn--2. For n > 1, the length of F,, is denoted by fn = IF,I. The injinite Fibonacci string F is the string which contains every F ,,, n > 1, as a prefix. Apart from their general theoretical importance, Fibonacci strings are often cited as worst-case examples for algorithms which compute all the repetitions or all the "Abelian squares" in a given string. In this paper we provide a characterization of all the squares in F, hence in every prefix F,,; this characterization naturally gives rise to a O(fn) algorithm which specifies all the squares of F,, in an appropriate encoding. This encoding is made possible by the fact that the squares of F, occur consecutively, in "runs", the number of which is O(fn). By contrast, the known general algorithms for the computation of the repetitions in an arbitrary string require O(fn log fn) time (and produce O(fn log fn) outputs) when applied to a Fibonacci string F,,.