TY - GEN

T1 - New and efficient approaches to the quasiperiodic characterisation of a string

AU - Flouri, Tomás

AU - Iliopoulos, Costas S.

AU - Kociumaka, Tomasz

AU - Pissis, Solon P.

AU - Puglisi, Simon J.

AU - Smyth, William F.

AU - Tyczyński, Wojciech

PY - 2012/12/10

Y1 - 2012/12/10

N2 - 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.

AB - 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.

KW - Covers

KW - Periodicity

KW - Quasiperiodicity

UR - http://www.scopus.com/inward/record.url?scp=84870516560&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84870516560&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84870516560

SN - 9788001050958

T3 - Proceedings of the Prague Stringology Conference, PSC 2012

SP - 75

EP - 88

BT - Proceedings of the Prague Stringology Conference, PSC 2012

T2 - Prague Stringology Conference, PSC 2012

Y2 - 27 August 2012 through 28 August 2012

ER -