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

    How many runs can a string contain?

    Access Status
    Open access via publisher
    Authors
    Puglisi, S.
    Simpson, Jamie
    Smyth, William
    Date
    2008
    Type
    Journal Article
    
    Metadata
    Show full item record
    Citation
    Puglisi, Simon and Simpson, Jamie and Smyth, William F. 2008. How many runs can a string contain?. Theoretical Computer Science. 401 (1-3): pp. 165-171.
    Source Title
    Theoretical Computer Science
    DOI
    10.1016/j.tcs.2008.04.020
    ISSN
    03043975
    Faculty
    Department of Mathematics and Statistics
    School of Science
    Faculty of Science and Engineering
    Remarks

    The link to the journal’s home page is: http://www.elsevier.com/wps/find/journaldescription.cws_home/505625/description#description

    Copyright © 2008 Elsevier Ltd. All rights reserved

    URI
    http://hdl.handle.net/20.500.11937/47398
    Collection
    • Curtin Research Publications
    Abstract

    In 2000 Kolpakov and Kucherov showed that the maximum number ρ(n) of runs in any string x[1..n] is O(n), but their proof was nonconstructive and provided no specific constant of proportionality. At the same time, they presented experimental data to prompt the conjecture: ρ(n)<n. Recently, Rytter [Wojciech Rytter, The number of runs in a string: Improved analysis of the linear upper bound, in: B. Durand, W. Thomas (Eds.), STACS 2006, in: Lecture Notes in Computer Science, vol. 3884, Springer-Verlag, Berlin, 2006, pp. 184–195] made a significant step toward proving this conjecture by showing that ρ(n)<5n. In this paper we improve Rytter’s approach and press the bound on ρ(n) further, proving ρ(n)≤3.48n.

    Related items

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

    • Torque and drag modelling for Redhill South-1 in Northern Perth Basin, Australia
      Smith, S.; Rasouli, Vamegh (2012)
      Drilling deviated and horizontal wells is commonly used in oil and gas industry for different purposes. In particular in unconventional reservoirs such as gas shales or tight formations horizontal wellbores provide a ...
    • Selected Physical Characteristics and Playing-Related Musculoskeletal Problems in Adolescent String Instrumentalists
      Vinci, S.; Smith, A.; Ranelli, Sonia (2015)
      PURPOSE: Music research has investigated the prevalence of playing-related musculoskeletal problems in adults and children, but the prevalence in adolescents has not been established. String instrumentalists report high ...
    • Sorting suffixes of two-pattern strings
      Franek, F.; Smyth, Bill (2004)
      Recently, several authors presented linear recursive algorithms for sorting suffixes of a string. All these algorithms employ a similar three-step approach, based on an initial division of the suffixes of x into two sets: ...
    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.