Show simple item record

dc.contributor.authorSmyth, Bill
dc.contributor.authorWang, S.
dc.date.accessioned2017-01-30T14:29:49Z
dc.date.available2017-01-30T14:29:49Z
dc.date.created2010-03-30T20:02:20Z
dc.date.issued2009
dc.identifier.citationSmyth, 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.
dc.identifier.urihttp://hdl.handle.net/20.500.11937/39052
dc.identifier.doi10.1016/j.tcs.2009.07.010
dc.description.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.

dc.publisherElsevier
dc.subjectPeriodicity lemma
dc.subjectIndeterminate string
dc.subjectPeriodicity
dc.subjectHole
dc.titleA new approach to the periodicity lemma on strings with holes
dc.typeJournal Article
dcterms.source.volume410
dcterms.source.number43
dcterms.source.startPage4295
dcterms.source.endPage4302
dcterms.source.issn03043975
dcterms.source.titleTheoretical Computer Science
curtin.note

The link to the journal’s home page is: http://www.elsevier.com/wps/find/journaldescription.cws_home/505625/description#description. Copyright © 2009 Elsevier B.V. All rights reserved

curtin.departmentDigital Ecosystems and Business Intelligence Institute (DEBII)
curtin.accessStatusOpen access
curtin.facultyCurtin Business School
curtin.facultyThe Digital Ecosystems and Business Intelligence Institute (DEBII)


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record