Search
Computing equality-free and repetitive string factorisations
Schmid M. Theoretical Computer Science618 42-51,2016.Type:Article
 Date Reviewed: Sep 1 2016
 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. Reviewer:  M. Sohel Rahman Review #: CR144723 (1611-0828)
 1) Condon, A.; Manuch, J.; Thachuk, C. Complexity of a collision-aware string partition problem and its relation to oligo design for gene synthesis. In Proc. 14th Annual International Computing and Combinatorics Conference (COCOON 2008). Springer, 2008, 265–275.
 2) Condon, A.; Manuch, J.; Thachuk, C. The complexity of string partitioning. J. Discrete Algorithms 32 (2015), 24–43.
 Would you recommend this review? yes no
 Other reviews under "Nonnumerical Algorithms And Problems": Date Improving the performance guarantee for approximate graph coloringWigderson A. Journal of the ACM 30(4): 729-735, 1983. Type: Article Feb 1 1985 Fast algorithms constructing minimal subalgebras, congruences, and ideals in a finite algebraDemel J., Demlová M., Koubek V. Theoretical Computer Science 36(2-3): 203-216, 1985. Type: Article Jan 1 1986 Complexity of the word problem for commutative semigroups of fixed dimensionHuynh D. Acta Informatica 22(4): 421-432, 1985. Type: Article May 1 1986 more...

E-Mail This Printer-Friendly
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®