For a string w, a factorisation is any tuple ( u 1 , u 2 , ? , u k ) of strings that satisfies w = u 1 ? u 2 ? u k . 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.
['Markus L. Schmid']
Computing equality-free and repetitive string factorisations