New and efficient approaches to the quasiperiodic characterisation of a string

Tomás Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth, Wojciech Tyczyński

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

A factor u of a string y is a cover of y if every letter of y lies within some occurrence of u in y; thus every cover u is also a border - both prefix and suffix - of y. A string y covered by u thus generalises the idea of a repetition; that is, a string composed of exact concatenations of u. Even though a string is coverable somewhat more frequently than it is a repetition, still a string that can be covered by a single u is rare. As a result, seeking to find a more generally applicable and descriptive notion of cover, many articles were written on the computation of a minimum k-cover of y; that is, the minimum cardinality set of strings of length k that collectively cover y. Unfortunately, this computation turns out to be NP-hard. Therefore, in this article, we propose new, simple, easily-computed, and widely applicable notions of string covering that provide an intuitive and useful characterisation of a string and its prefixes: the enhanced cover and the enhanced cover array.

Original languageEnglish
Title of host publicationProceedings of the Prague Stringology Conference, PSC 2012
Pages75-88
Number of pages14
Publication statusPublished - 10 Dec 2012
Externally publishedYes
EventPrague Stringology Conference, PSC 2012 - Prague, Czech Republic
Duration: 27 Aug 201228 Aug 2012

Publication series

NameProceedings of the Prague Stringology Conference, PSC 2012

Conference

ConferencePrague Stringology Conference, PSC 2012
CountryCzech Republic
CityPrague
Period27/08/1228/08/12

Keywords

  • Covers
  • Periodicity
  • Quasiperiodicity

Fingerprint Dive into the research topics of 'New and efficient approaches to the quasiperiodic characterisation of a string'. Together they form a unique fingerprint.

Cite this