Diverse Palindromic Factorization is NP-Complete

References

• 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, ISI, Google 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. Crossref, Google Scholar
• 8. A. E. Frid, S. Puzynina and L. Zamboni , On palindromic factorization of words, Adv. Appl. Math. 50(5) (2013) 737–748. Crossref, ISI, Google 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 , Pal^k 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, ISI, Google 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, ISI, Google 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, ISI, Google Scholar