Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
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.
Bookmark and Share
  Editor Recommended
Nonnumerical Algorithms And Problems (F.2.2 )
Combinatorics (G.2.1 )
Would you recommend this review?
Other reviews under "Nonnumerical Algorithms And Problems": Date
Improving the performance guarantee for approximate graph coloring
Wigderson 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 algebra
Demel 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 dimension
Huynh D. Acta Informatica 22(4): 421-432, 1985. Type: Article
May 1 1986

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy