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

    Palindromes in circular words

    Access Status
    Fulltext not available
    Authors
    Simpson, Jamie
    Date
    2014
    Type
    Journal Article
    
    Metadata
    Show full item record
    Citation
    Simpson, J. 2014. Palindromes in circular words. Theoretical Computer Science. 550: pp. 66-78.
    Source Title
    Theoretical Computer Science
    DOI
    10.1016/j.tcs.2014.07.012
    ISSN
    0304-3975
    School
    Department of Mathematics and Statistics
    URI
    http://hdl.handle.net/20.500.11937/26621
    Collection
    • Curtin Research Publications
    Abstract

    There is a very short and beautiful proof that the number of distinct non-empty palindromes in a word of length n is at most n. In this paper we show, with a very complicated proof, that the number of distinct non-empty palindromes with length at most n in a circular word of length n is less than 5n/3. For n divisible by 3 we present circular words of length n containing 5n/3 -2 distinct palindromes, so the bound is almost sharp. The paper finishes with some open problems.

    Related items

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

    • The total run length of a word
      Glen, A.; Simpson, Jamie (2013)
      A run in a word is a periodic factor whose length is at least twice its period and which cannot be extended to the left or right (by a letter) to a factor with greater period. In recent years a great deal of work has been ...
    • Fast algorithms for approximate circular string matching
      Barton, C.; Iliopoulos, Costas; Pissis, S. (2014)
      Background: Circular string matching is a problem which naturally arises in many biological contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist ...
    • Transfer of prestress by pretensioned wire tendons
      Kong, Paul Y.L. (1993)
      Key words: End zone, prestress transfer, wire tendon, transmission length, pull-in, plain wire, indented wire, concrete strength, size of wire, gradual release, sudden release, shock release, time dependent effects.An ...
    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.