Logo image
Back
A characterization of the squares in a Fibonacci string
Journal article   Open access   Peer reviewed

A characterization of the squares in a Fibonacci string

C.S. Iliopoulos, D. Moore and W.F. Smyth
Theoretical Computer Science, Vol.172(1-2), pp.281-291
1997
DOI: https://doi.org/10.1016/S0304-3975(96)00141-7
pdf
fibonnachi_string.pdfDownloadView
Author’s Version Open Access
url
Link to Published Version *Subscription may be requiredView

Abstract

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.

Details

Metrics

138 File views/ downloads
99 Record Views
66 Times Cited - Web of Science

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types
Domestic collaboration
International collaboration
Citation topics
4 Electrical Engineering, Electronics & Computer Science
4.182 Data Structures, Algorithms & Complexity
4.182.1103 Efficient Algorithms
Web Of Science research areas
Computer Science, Theory & Methods
ESI research areas
Computer Science
Logo image