{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:54:28Z","timestamp":1743026068307,"version":"3.40.3"},"publisher-location":"Cham","reference-count":19,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031721991"},{"type":"electronic","value":"9783031722004"}],"license":[{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,9,19]],"date-time":"2024-09-19T00:00:00Z","timestamp":1726704000000},"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":[[2025]]},"DOI":"10.1007\/978-3-031-72200-4_5","type":"book-chapter","created":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:01:50Z","timestamp":1726686110000},"page":"57-72","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generalization of\u00a0Repetitiveness Measures for\u00a0Two-Dimensional Strings"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-9591-057X","authenticated-orcid":false,"given":"Lorenzo","family":"Carfagna","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-0196","authenticated-orcid":false,"given":"Giovanni","family":"Manzini","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3489-0684","authenticated-orcid":false,"given":"Giuseppe","family":"Romana","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6928-0168","authenticated-orcid":false,"given":"Marinella","family":"Sciortino","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8979-9055","authenticated-orcid":false,"given":"Cristian","family":"Urbina","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,19]]},"reference":[{"issue":"1","key":"5_CR1","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1109\/TIT.2020.3038147","volume":"67","author":"H Bannai","year":"2021","unstructured":"Bannai, H., et al.: The smallest grammar problem revisited. IEEE Trans. Inf. Theory 67(1), 317\u2013328 (2021)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"5_CR2","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1006\/jcss.2002.1852","volume":"65","author":"P Berman","year":"2002","unstructured":"Berman, P., Karpinski, M., Larmore, L.L., Plandowski, W., Rytter, W.: On the complexity of pattern matching for highly compressed two-dimensional texts. J. Comput. Syst. Sci. 65(2), 332\u2013350 (2002)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"5_CR3","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1093\/comjnl\/bxac182","volume":"67","author":"NR Brisaboa","year":"2024","unstructured":"Brisaboa, N.R., Gagie, T., G\u00f3mez-Brand\u00f3n, A., Navarro, G.: Two-dimensional block trees. Comput. J. 67(1), 391\u2013406 (2024)","journal-title":"Comput. J."},{"key":"5_CR4","doi-asserted-by":"publisher","unstructured":"Carfagna, L., Manzini, G.: Compressibility measures for two-dimensional data. In: Proceedings of the 30th International Symposium on String Processing and Information Retrieval, SPIRE 2023. LNCS, vol. 14240, pp. 102\u2013113. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-43980-3_9","DOI":"10.1007\/978-3-031-43980-3_9"},{"key":"5_CR5","doi-asserted-by":"publisher","first-page":"87268","DOI":"10.1109\/ACCESS.2024.3417621","volume":"12","author":"L Carfagna","year":"2024","unstructured":"Carfagna, L., Manzini, G.: The landscape of compressibility measures for two-dimensional data. IEEE Access 12, 87268\u201387283 (2024)","journal-title":"IEEE Access"},{"issue":"7","key":"5_CR6","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., et al.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Christiansen, A.R., Ettienne, M.B., Kociumaka, T., Navarro, G., Prezza, N.: Optimal-time dictionary-compressed indexes. ACM Trans. Algor. 17(1), 8:1\u20138:39 (2021)","DOI":"10.1145\/3426473"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1007\/978-3-319-77404-6_36","volume-title":"LATIN 2018: Theoretical Informatics","author":"T Gagie","year":"2018","unstructured":"Gagie, T., Navarro, G., Prezza, N.: On the approximation ratio of\u00a0lempel-ziv parsing. In: Bender, M.A., Farach-Colton, M., Mosteiro, M.A. (eds.) LATIN 2018. LNCS, vol. 10807, pp. 490\u2013503. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-77404-6_36"},{"key":"5_CR9","unstructured":"Gallant, J.K.: String Compression Algorithms. Ph.D. thesis, Princeton University (1982)"},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"Ganardi, M., Jez, A., Lohrey, M.: Balancing straight-line programs. J. ACM 68(4), 27:1\u201327:40 (2021)","DOI":"10.1145\/3457389"},{"key":"5_CR11","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/978-3-642-59126-6_4","volume-title":"Handbook of Formal Languages","author":"D Giammarresi","year":"1997","unstructured":"Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 215\u2013267. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-642-59126-6_4"},{"issue":"3","key":"5_CR12","doi-asserted-by":"publisher","first-page":"520","DOI":"10.1137\/S0097539792231982","volume":"24","author":"R Giancarlo","year":"1995","unstructured":"Giancarlo, R.: A generalization of the suffix tree to square matrices, with applications. SIAM J. Comput. 24(3), 520\u2013562 (1995)","journal-title":"SIAM J. Comput."},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Kempa, D., Prezza, N.: At the roots of dictionary compression: string attractors. In: STOC, pp. 827\u2013840. ACM (2018)","DOI":"10.1145\/3188745.3188814"},{"issue":"4","key":"5_CR14","doi-asserted-by":"publisher","first-page":"2074","DOI":"10.1109\/TIT.2022.3224382","volume":"69","author":"T Kociumaka","year":"2023","unstructured":"Kociumaka, T., Navarro, G., Prezza, N.: Toward a definitive compressibility measure for repetitive sequences. IEEE Trans. Inf. Theory 69(4), 2074\u20132092 (2023)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"5_CR15","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1109\/TIT.1986.1057132","volume":"32","author":"A Lempel","year":"1986","unstructured":"Lempel, A., Ziv, J.: Compression of two-dimensional data. IEEE Trans. Inf. Theory 32(1), 2\u20138 (1986)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1016\/j.tcs.2020.11.006","volume":"850","author":"S Mantaci","year":"2021","unstructured":"Mantaci, S., Restivo, A., Romana, G., Rosone, G., Sciortino, M.: A combinatorial view on string attractors. Theor. Comput. Sci. 850, 236\u2013248 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Indexing highly repetitive string collections, part II: compressed indexes. ACM Comput. Surv. 54(2), 26 (2021)","DOI":"10.1145\/3432999"},{"key":"5_CR18","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Indexing highly repetitive string collections, part I: repetitiveness measures. ACM Comput. Surv. 54(2), 29 (2021)","DOI":"10.1145\/3434399"},{"issue":"2","key":"5_CR19","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1109\/TIT.2020.3042746","volume":"67","author":"G Navarro","year":"2021","unstructured":"Navarro, G., Ochoa, C., Prezza, N.: On the approximation ratio of ordered parsings. IEEE Trans. Inf. Theory 67(2), 1008\u20131026 (2021)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-72200-4_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,18]],"date-time":"2024-09-18T19:02:11Z","timestamp":1726686131000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-72200-4_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,19]]},"ISBN":["9783031721991","9783031722004"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-72200-4_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024,9,19]]},"assertion":[{"value":"19 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Puerto Vallarta","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Mexico","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"31","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/computo.fismat.umich.mx\/spire2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}