A new approach to the periodicity lemma on strings with holes
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 divi...
| Main Authors: | , |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2009
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/39052 |
| _version_ | 1848755485726998528 |
|---|---|
| author | Smyth, Bill Wang, S. |
| author_facet | Smyth, Bill Wang, S. |
| author_sort | Smyth, Bill |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T08:57:04Z |
| format | Journal Article |
| id | curtin-20.500.11937-39052 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:57:04Z |
| publishDate | 2009 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-390522017-09-13T16:01:26Z A new approach to the periodicity lemma on strings with holes Smyth, Bill Wang, S. Periodicity lemma Indeterminate string Periodicity Hole 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. 2009 Journal Article http://hdl.handle.net/20.500.11937/39052 10.1016/j.tcs.2009.07.010 Elsevier fulltext |
| spellingShingle | Periodicity lemma Indeterminate string Periodicity Hole Smyth, Bill Wang, S. A new approach to the periodicity lemma on strings with holes |
| title | A new approach to the periodicity lemma on strings with holes |
| title_full | A new approach to the periodicity lemma on strings with holes |
| title_fullStr | A new approach to the periodicity lemma on strings with holes |
| title_full_unstemmed | A new approach to the periodicity lemma on strings with holes |
| title_short | A new approach to the periodicity lemma on strings with holes |
| title_sort | new approach to the periodicity lemma on strings with holes |
| topic | Periodicity lemma Indeterminate string Periodicity Hole |
| url | http://hdl.handle.net/20.500.11937/39052 |