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 new approach to the periodicity lemma on strings with holes

Smyth, W.F. and Wang, Shu (2009) A new approach to the periodicity lemma on strings with holes. Theoretical Computer Science, 410 (43). pp. 4295-4302.

[img]
Preview
PDF - Authors' Version
Download (285kB) | Preview
Link to Published Version: http://dx.doi.org/10.1016/j.tcs.2009.07.010
*Subscription may be required

Abstract

We first give an elementary proof of the periodicity lemma for strings containing one hole (variously called a “wild card”, a “don’t-care” or an “indeterminate letter” in the literature). The proof is modelled on Euclid’s algorithm for the greatest common divisor and is simpler than the original proof given in [J. Berstel, L. Boasson, Partial words and a theorem of Fine and Wilf, Theoret. Comput. Sci. 218 (1999) 135–141]. We then study the two-hole case, where our result agrees with the one given in [F. Blanchet-Sadri, Robert A. Hegstrom, Partial words and a theorem of Fine and Wilf revisited, Theoret. Comput. Sci. 270 (1-2) (2002) 401–419] but is more easily proved and enables us to identify a maximum-length prefix or suffix of the string to which the periodicity lemma does apply. Finally, we extend our result to three or more holes using elementary methods, and state a version of the periodicity lemma that applies to all strings with or without holes. We describe an algorithm that, given the locations of the holes in a string, computes maximum-length substrings to which the periodicity lemma applies, in time proportional to the number of holes. Our approach is quite different from that used by Blanchet-Sadri and Hegstrom, and also simpler.

Item Type: Journal Article
Publisher: Elsevier BV
Copyright: © 2009 Elsevier B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/28087
Item Control Page Item Control Page

Downloads

Downloads per month over past year