Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

A linear algorithm for computing all the squares of a Fibonacci string

Iliopoulos, C.S., Moore, D. and Smyth, W.F. (1996) A linear algorithm for computing all the squares of a Fibonacci string. In: Computing: The Australasian Theory Symposium (CATS '96), 29 - 30 January 1996, Melbourne, Australia  Preview

Abstract

A (finite) Fibonacci string $F_n$ is defined as follows: $F_0 = b$, $F_1 = a$; for every integer $n \ge 2$, $F_n = F_{n-1}F_{n- 2}$. For $n \ge 1$, the length of $F_n$ is denoted by $f_n = |F_n|$, while it is convenient to define $f_0 \equiv 0$. The infinite Fibonacci string $F$ is the string which contains every $F_n$, $n \ge 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_n$; this characterization naturally gives rise to a $\Theta(f_n)$ algorithm which specifies all the squares of $F_n$ in an appropriate encoding. This encoding is made possible by the fact that the squares of $F_n$ occur consecutively, in runs'', the number of which is $\Theta(f_n)$. By contrast, the known general algorithms for the computation of the repetitions in an arbitrary string require $\Theta(f_n\log f_n)$ time (and produce $\Theta(f_n\log f_n)$ outputs) when applied to a Fibonacci string $F_n$.

Item Type: Conference Paper http://researchrepository.murdoch.edu.au/id/eprint/27530 Item Control Page