Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Computing equality-free and repetitive string factorisations
Schmid M.  Theoretical Computer Science 618 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?
yes
no
Other reviews under "Nonnumerical Algorithms And Problems": Date
Graph isomorphism in quasipolynomial time [extended abstract]
Babai L.  STOC 2016 (Proceedings of the 48th Annual ACM SIGACT Symposium on the Theory of Computing, Cambridge, MA,  Jun 19-21, 2016) 684-697, 2016. Type: Proceedings
Jun 27 2017
Parameterized algorithms
Cygan M., Fomin F., Kowalik Ł., Lokshtanov D., Marx D., Pilipczuk M., Pilipczuk M., Saurabh S.,  Springer International Publishing, New York, NY, 2015. 613 pp. Type: Book (978-3-319212-74-6), Reviews: (2 of 2)
Apr 13 2017
Algorithms (4th ed.)
Sedgewick R., Wayne K.,  Addison-Wesley Professional, Upper Saddle River, NJ, 2015. 984 pp. Type: Book (978-0-134384-68-9)
Mar 29 2017
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright © 2000-2017 ThinkLoud, Inc.
Terms of Use
| Privacy Policy