{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T08:58:47Z","timestamp":1743152327953,"version":"3.40.3"},"publisher-location":"Cham","reference-count":11,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319214993"},{"type":"electronic","value":"9783319215006"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-21500-6_6","type":"book-chapter","created":{"date-parts":[[2015,7,17]],"date-time":"2015-07-17T08:07:44Z","timestamp":1437120464000},"page":"85-96","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Diverse Palindromic Factorization Is NP-complete"],"prefix":"10.1007","author":[{"given":"Hideo","family":"Bannai","sequence":"first","affiliation":[]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"additional","affiliation":[]},{"given":"Dominik","family":"Kempa","sequence":"additional","affiliation":[]},{"given":"Marcin","family":"Pi\u0105tkowski","sequence":"additional","affiliation":[]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[]},{"given":"Shiho","family":"Sugimoto","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,7,18]]},"reference":[{"unstructured":"Alitabbi, A., Iliopoulos, C.S., Rahman, M.S.: Maximal palindromic factorization. In: Proceedings of the Prague Stringology Conference (PSC), pp. 70\u201377 (2013)","key":"6_CR1"},{"unstructured":"Fernau, H., Manea, F., Merca\u015f, R., Schmid, M.L.: Pattern matching with variables: fast algorithms and new hardness results. In: Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS), pp. 302\u2013315 (2015)","key":"6_CR2"},{"key":"6_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.jda.2014.08.001","volume":"28","author":"G Fici","year":"2014","unstructured":"Fici, G., Gagie, T., K\u00e4rkk\u00e4inen, J., Kempa, D.: A subquadratic algorithm for minimum palindromic factorization. Journal of Discrete Algorithms 28, 41\u201348 (2014)","journal-title":"Journal of Discrete Algorithms"},{"issue":"5","key":"6_CR4","doi-asserted-by":"publisher","first-page":"737","DOI":"10.1016\/j.aam.2013.01.002","volume":"50","author":"AE Frid","year":"2013","unstructured":"Frid, A.E., Puzynina, S., Zamboni, L.: On palindromic factorization of words. Advances in Applied Mathematics 50(5), 737\u2013748 (2013)","journal-title":"Advances in Applied Mathematics"},{"unstructured":"Gawrychowski, P., Uzna\u0144ski, P.: Tight tradeoffs for approximating palindromes in streams. Technical Report 1410.6433, arxiv.org (2014)","key":"6_CR5"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","first-page":"150","volume-title":"Combinatorial Pattern Matching","author":"T I","year":"2014","unstructured":"I, T., Sugimoto, S., Inenaga, S., Bannai, H., Takeda, M.: Computing palindromic factorizations and palindromic covers on-line. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 150\u2013161. Springer, Heidelberg (2014)"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/978-3-662-46078-8_24","volume-title":"SOFSEM 2015: Theory and Practice of Computer Science-Testing","author":"D Kosolobov","year":"2015","unstructured":"Kosolobov, D., Rubinchik, M., Shur, A.M.: Pal$$^\\text{ k }$$ is linear recognizable online. In: Italiano, G.F., Margaria-Steffen, T., Pokorn\u00fd, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015-Testing. LNCS, vol. 8939, pp. 289\u2013301. Springer, Heidelberg (2015)"},{"issue":"1","key":"6_CR8","first-page":"75","volume":"8","author":"O Ravsky","year":"2003","unstructured":"Ravsky, O.: On the palindromic decomposition of binary words. Journal of Automata, Languages and Combinatorics 8(1), 75\u201383 (2003)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"doi-asserted-by":"crossref","unstructured":"Tseitin, G.S.: On the complexity of derivation in propositional calculus. In: Slisenko, A.O. (ed.) Structures in Constructive Mathematics and Mathematical Logic, Part II, pp. 115\u2013125 (1968)","key":"6_CR9","DOI":"10.1007\/978-1-4899-5327-8_25"},{"issue":"3","key":"6_CR10","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"22","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory 22(3), 337\u2013343 (1977)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"6_CR11","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory 24(5), 530\u2013536 (1978)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-21500-6_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T10:44:07Z","timestamp":1676025847000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-21500-6_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319214993","9783319215006"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-21500-6_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"18 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}