World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue: Developments in Language Theory (DLT 2015)No Access

Diverse Palindromic Factorization is NP-Complete

    We prove that it is NP-complete to decide whether a given string can be factored into palindromes that are each unique in the factorization.

    Communicated by Igor Potapov and Pavel Semukhin


    • 1. A. Alitabbi, C. S. Iliopoulos and M. S. Rahman , Maximal palindromic factorization, Proceedings of the Prague Stringology Conference (PSC) (2013), pp. 70–77. Google Scholar
    • 2. H. Bannai, T. Gagie, S. Inenaga, J. Kärkkäinen, D. Kempa, M. Piątkowski, S. J. Puglisi and S. Sugimoto , Diverse palindromic factorization is NP-complete, Proceedings of the 19th Conference on Developments in Language Theory (DLT) (2015), pp. 85–96. Google Scholar
    • 3. K. Borozdin, D. Kosolobov, M. Rubinchik and A. M. Shur , Palindromic length in linear time, Proceedings of the 28th Symposium on Combinatorial Pattern Matching (CPM) (2017), pp. 23:1–23:12. Google Scholar
    • 4. S. Buss and M. Soltys , Unshuffling a square is NP-hard, J. Comput. Syst. Sci. 80(4) (2014) 766–776. Crossref, ISIGoogle Scholar
    • 5. K. Casel, H. Fernau, S. Gaspers, B. Gras and M. L. Schmid , On the complexity of grammar-based compression over fixed alphabets, Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP) (2016), pp. 122:1–122:14. Google Scholar
    • 6. H. Fernau, F. Manea, R. Mercaş and M. L. Schmid , Pattern matching with variables: Fast algorithms and new hardness results, Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS) (2015), pp. 302–315. Google Scholar
    • 7. G. Fici, T. Gagie, J. Kärkkäinen and D. Kempa , A subquadratic algorithm for minimum palindromic factorization, J. Discr. Algorithms 28 (2014) 41–48. CrossrefGoogle Scholar
    • 8. A. E. Frid, S. Puzynina and L. Zamboni , On palindromic factorization of words, Adv. Appl. Math. 50(5) (2013) 737–748. Crossref, ISIGoogle Scholar
    • 9. M. R. Garey and D. S. Johnson , Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman and Co., 1979). Google Scholar
    • 10. P. Gawrychowski, O. Merkurev, A. M. Shur and P. Uznanski , Tight tradeoffs for real-time approximation of longest palindromes in streams, Proceedings of the 27th Symposium on Combinatorial Pattern Matching (CPM) (2016), pp. 18:1–18:13. Google Scholar
    • 11. D. Hucke, M. Lohrey and C. P. Reh , The smallest grammar problem revisited, Proceedings of the 23rd Symposium on String Processing and Information Retrieval (SPIRE) (2016), pp. 35–49. Google Scholar
    • 12. T. I, S. Sugimoto, S. Inenaga, H. Bannai and M. Takeda , Computing palindromic factorizations and palindromic covers on-line, Proceedings of the 25th Symposium on Combinatorial Pattern Matching (CPM) (2014), pp. 150–161. Google Scholar
    • 13. D. Kosolobov, M. Rubinchik and A. M. Shur , Palk is linear recognizable online, Proceedings of the 41st Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) (2015), pp. 289–301. Google Scholar
    • 14. L. Levin , Universal search problems, Problems of Information Transmission 9(3) (1973) 115–116. Google Scholar
    • 15. O. Ravsky , On the palindromic decomposition of binary words, Journal of Automata, Languages and Combinatorics 8(1) (2003) 75–83. Google Scholar
    • 16. M. Rubinchik and A. M. Shur , EERTREE: An efficient data structure for processing palindromes in strings, Proceedings of the 26th International Workshop on Combinatorial Algorithms (IWOCA) (2015), pp. 321–333. Google Scholar
    • 17. M. L. Schmid , Computing equality-free and repetitive string factorizations, Theoretical Computer Science 618(7) (2016) 42–51. Crossref, ISIGoogle Scholar
    • 18. G. S. Tseitin , On the complexity of derivation in propositional calculus, Structures in Constructive Mathematics and Mathematical Logic, Part II, ed. A. O. Slisenko (1968), pp. 115–125. Google Scholar
    • 19. J. Ziv and A. Lempel , A universal algorithm for sequential data compression, IEEE Trans. Inf. Theory 22(3) (1977) 337–343. Crossref, ISIGoogle Scholar
    • 20. J. Ziv and A. Lempel , Compression of individual sequences via variable-rate coding, IEEE Trans. Inf. Theory 24(5) (1978) 530–536. Crossref, ISIGoogle Scholar
    Remember to check out the Most Cited Articles!

    Check out these Handbooks in Computer Science