Computing equality-free and repetitive string factorisations

For a string w, a factorisation is any tuple (u1,u2,…,uk) of strings that satisfies w=u1⋅u2⋯uk. A factorisation is called equality-free if each two factors are different, its size is the number of factors (counting each occurrence of repeating factors) and its width is the maximum length of any fact...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2016-03, Vol.618, p.42-51
Main Author: Schmid, Markus L.
Format: Article
Language:English
Subjects:
[formula omitted]-hard string problems
Complexity
Computation
Counting
Multivariate algorithmics
Parameterised complexity
String factorisations
Strings
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For a string w, a factorisation is any tuple (u1,u2,…,uk) of strings that satisfies w=u1⋅u2⋯uk. A factorisation is called equality-free if each two factors are different, its size is the number of factors (counting each occurrence of repeating factors) and its width is the maximum length of any factor. To decide, for a string w and a number m, whether w has an equality-free factorisation with a size of at least (or a width of at most) m are NP-complete problems. We further investigate the complexity of these problems and we also study the converse problems of computing a factorisation that is to a large extent not equality-free, i.e., a factorisation of size at least (or width at most) m such that the total number of different factors does not exceed a given bound k.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2016.01.006