String factorization has long been at the heart of research on the combinatorics of words. It has attracted researchers from both theory and practice because not only is it inherently beautiful as a theoretical problem, but it has a lot of promising applications in different fields as well. In this paper, the author studies a relatively new factorization, which is referred to as equality-free factorization. He also investigates the converse problem to computing equality-free factorizations.

The main interesting results of this paper can be summarized as follows. Following up on the hardness results in [1,2], where the idea of equality-free factorization was first introduced, the author proves that computing equality-free factorizations with bounded width is fixed-parameter tractable. As for the converse problem to the equality-free factorization, the author has a number of interesting contributions. He has shown that the problem of “deciding on whether a word w has a factorization of width at most m and with at most k different factors is NP-complete, even if m=2.” But the problem becomes polynomial if the number of factors or the alphabet size is a constant.

Furthermore, the author has investigated the problem of deciding whether a given word has an equality-free factorization having factors drawn from a given finite set of words only, and has proved it to be NP-complete even for binary alphabets. However, it is shown to be fixed parameter tractable for some parameters and proves to be polynomial if the equality-freeness condition is dropped. Interestingly, this problem came into play as a tool for proving some of the above results.

Finally, the author discusses the significance of his results, along with identifying some interesting open problems that make this paper worth reading, especially for people working on the combinatorics of words and string algorithms.