Curtin University Homepage
  • Library
  • Help
    • Admin

    espace - Curtin’s institutional repository

    JavaScript is disabled for your browser. Some features of this site may not work without it.
    View Item 
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item
    • espace Home
    • espace
    • Curtin Research Publications
    • View Item

    A new approach to the periodicity lemma on strings with holes

    135233_135233.pdf (206.8Kb)
    Access Status
    Open access
    Authors
    Smyth, Bill
    Wang, S.
    Date
    2009
    Type
    Journal Article
    
    Metadata
    Show full item record
    Citation
    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.
    Source Title
    Theoretical Computer Science
    DOI
    10.1016/j.tcs.2009.07.010
    ISSN
    03043975
    Faculty
    Curtin Business School
    The Digital Ecosystems and Business Intelligence Institute (DEBII)
    School
    Digital Ecosystems and Business Intelligence Institute (DEBII)
    Remarks

    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

    URI
    http://hdl.handle.net/20.500.11937/39052
    Collection
    • Curtin Research Publications
    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.

    Related items

    Showing items related by title, author, creator and subject.

    • ASSESSING THE POSSIBILITIES FOR THE NATURAL SETTLEMENT OF WESTERN ROCK LOBSTER
      Phillips, Bruce; Melville-Smith, R.; Thomson, A.; Rossbach, M. (2007)
      Previous studies have shown that western rock lobster pueruli and post-pueruli shelter in small holes and crevices and that suitable shelter in the inshore environment is limited. It is considered that by providing ...
    • Utilizing Coiled tube rig for mineral exploration application
      Roufail, R.; Rasouli, Vamegh; Mokaramian, A.; Kamyab, Mohammadreza; Lagat, C.; Cavanough, G. (2013)
      Mineral exploration is in a race to employ drilling technology that can perform the exploration and drilling investigation in a fast and inexpensive manner. After an extensive study of the available drilling technologies ...
    • Cover array string reconstruction
      Crochemore, M.; Iliopoulos, Costas; Pissis, S.; Tischler, G. (2010)
      A proper fact or u of a string y is a cover of y if every letter of y is within some occurrence of u in y. The concept generalises the notion of periods of a string. An integer array C is the minimal-cover (resp. ...
    Advanced search

    Browse

    Communities & CollectionsIssue DateAuthorTitleSubjectDocument TypeThis CollectionIssue DateAuthorTitleSubjectDocument Type

    My Account

    Admin

    Statistics

    Most Popular ItemsStatistics by CountryMost Popular Authors

    Follow Curtin

    • 
    • 
    • 
    • 
    • 

    CRICOS Provider Code: 00301JABN: 99 143 842 569TEQSA: PRV12158

    Copyright | Disclaimer | Privacy statement | Accessibility

    Curtin would like to pay respect to the Aboriginal and Torres Strait Islander members of our community by acknowledging the traditional owners of the land on which the Perth campus is located, the Whadjuk people of the Nyungar Nation; and on our Kalgoorlie campus, the Wongutha people of the North-Eastern Goldfields.