Journal article
A new approach to the periodicity lemma on strings with holes
Theoretical Computer Science, Vol.410(43), pp.4295-4302
2009
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.
Details
- Title
- A new approach to the periodicity lemma on strings with holes
- Authors/Creators
- W.F. Smyth (Author/Creator)Shu Wang (Author/Creator)
- Publication Details
- Theoretical Computer Science, Vol.410(43), pp.4295-4302
- Publisher
- Elsevier BV
- Identifiers
- 991005543787807891
- Copyright
- © 2009 Elsevier B.V.
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
104 File views/ downloads
87 Record Views
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.61 Artificial Intelligence & Machine Learning
- 4.61.1988 Formal Languages
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science