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.

Learn more

A characterization of the squares in a Fibonacci string

Iliopoulos, C.S., Moore, D. and Smyth, W.F. (1997) A characterization of the squares in a Fibonacci string. Theoretical Computer Science, 172 (1-2). pp. 281-291.

PDF - Authors' Version
Download (257kB)
Link to Published Version:
*Subscription may be required


A (finite) Fibonacci stringFn is defined as follows: F0 = b, F1 = a; for every integer n ⩾ 2, Fn = Fn − 1Fn − 2. For n ⩾ 1, the length of Fn is denoted by . The infinite Fibonacci stringF is the string which contains every Fn, 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 Fn; this characterization naturally gives rise to a algorithm which specifies all the squares of Fn in an appropriate encoding. This encoding is made possible by the fact that the squares of Fn occur consecutively, in “runs”, the number of which is . By contrast, the known general algorithms for the computation of the repetitions in an arbitrary string require time (and produce outputs) when applied to a Fibonacci string Fn.

Item Type: Journal Article
Publisher: Elsevier BV
Copyright: © 1997 Published by Elsevier B.V.
Item Control Page Item Control Page


Downloads per month over past year