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

The covers of a circular Fibonacci string

Iliopoulos, C.S., Moore, D. and Smyth, W.F. (1998) The covers of a circular Fibonacci string. Journal of Combinatorial Mathematics and Combinatorial Computing, 26 . pp. 227-236.

[img]
Preview
PDF - Authors' Version
Download (168kB)

Abstract

Fibonacci strings turn out to constitute worst cases for a number of computer algorithms which find generic patterns in strings. Examples of such patterns are repetitions, Abelian squares, and "covers". In particular, we characterize in this paper the covers of a circular Fibonacci string C(F k ) and show that they are \Theta(jF k j 2 ) in number. We show also that, by making use of an appropriate encoding, these covers can be reported in \Theta(jF k j) time. By contrast, the fastest known algorithm for computing the covers of an arbitrary circular string of length n requires time O(n log n).

Item Type: Journal Article
Publisher: Charles Babbage Research Centre
Publishers Website: http://www.combinatorialmath.ca/jcmcc/
URI: http://researchrepository.murdoch.edu.au/id/eprint/27561
Item Control Page Item Control Page

Downloads

Downloads per month over past year