{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T08:47:09Z","timestamp":1767430029997,"version":"3.48.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T00:00:00Z","timestamp":1767398400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T00:00:00Z","timestamp":1767398400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004913","name":"Universit\u00e0 degli Studi di Palermo","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004913","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    The problem of detecting and measuring the repetitiveness of one-dimensional strings has been extensively studied in data compression and text indexing. Our understanding of these issues has been significantly improved by the introduction of the notion of\n                    <jats:italic>string attractor<\/jats:italic>\n                    (Kempa and Prezza 2018) and by the results showing the relationship between attractors and other measures of compressibility. When the input data are structured in a non-linear way, as in two-dimensional strings, inherent redundancy often offers an even richer source for compression. However, systematic studies on repetitiveness measures for two-dimensional strings are still scarce. In this paper, we extend to two or more dimensions the main measures of complexity introduced for one-dimensional strings. We distinguish between the measures\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\delta $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b4<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    and\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\gamma $$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mi>\u03b3<\/mml:mi>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , defined in terms of the substrings of the input, and the measures\n                    <jats:italic>g<\/jats:italic>\n                    ,\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$g_{rl}$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:msub>\n                            <mml:mi>g<\/mml:mi>\n                            <mml:mrow>\n                              <mml:mi>rl<\/mml:mi>\n                            <\/mml:mrow>\n                          <\/mml:msub>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    , and\n                    <jats:italic>b<\/jats:italic>\n                    , which are based on copy-paste mechanisms. We study the properties and mutual relationships between these two classes and we show that the two classes become incomparable for\n                    <jats:italic>d<\/jats:italic>\n                    -dimensional inputs as soon as\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$d\\geqslant 2$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>d<\/mml:mi>\n                            <mml:mo>\u2a7e<\/mml:mo>\n                            <mml:mn>2<\/mml:mn>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . Moreover, we show that our grammar-based representation of a\n                    <jats:italic>d<\/jats:italic>\n                    -dimensional string of size\n                    <jats:italic>N<\/jats:italic>\n                    enables direct access to any symbol in\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$O(\\log N)$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mo>log<\/mml:mo>\n                            <mml:mi>N<\/mml:mi>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    time. We also compare our measures for two-dimensional strings with the 2D Block Tree data structure (Brisaboa et al., Comput. J.\n                    <jats:bold>67<\/jats:bold>\n                    (1), 391\u2013406, 2024) and provide some insights for the design of future effective two-dimensional compressors. A preliminary version of this paper appeared in the proceedings of the conference SPIRE 2024.\n                  <\/jats:p>","DOI":"10.1007\/s00224-025-10244-9","type":"journal-article","created":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T08:42:19Z","timestamp":1767429739000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generalization of Repetitiveness Measures for Two-Dimensional Strings"],"prefix":"10.1007","volume":"70","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":[[2026,1,3]]},"reference":[{"key":"10244_CR1","doi-asserted-by":"crossref","unstructured":"Kempa, D., Prezza, N.: At the roots of dictionary compression: string attractors. In: STOC, pp. 827\u2013840. ACM, New York (2018)","DOI":"10.1145\/3188745.3188814"},{"issue":"2","key":"10244_CR2","first-page":"29","volume":"54","author":"G Navarro","year":"2021","unstructured":"Navarro, G.: Indexing highly repetitive string collections, part I: repetitiveness measures. ACM Comput. Surv. 54(2), 29 (2021)","journal-title":"ACM Comput. Surv."},{"key":"10244_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.jcss.2020.11.002","volume":"117","author":"D Belazzougui","year":"2021","unstructured":"Belazzougui, D., C\u00e1ceres, M., Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Navarro, G., Ord\u00f3\u00f1ez, A., Puglisi, S.J., Tabei, Y.: Block trees. J. Comput. Syst. Sci. 117, 1\u201322 (2021)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"10244_CR4","first-page":"26","volume":"54","author":"G Navarro","year":"2021","unstructured":"Navarro, G.: Indexing highly repetitive string collections, part II: compressed indexes. ACM Comput. Surv. 54(2), 26 (2021)","journal-title":"ACM Comput. Surv."},{"key":"10244_CR5","doi-asserted-by":"crossref","unstructured":"Brisaboa, N., Gagie, T., G\u00f3mez-Brand\u00f3n, A., Navarro, G.: Two-dimensional block trees. In: Proceedings of the 28th Data Compression Conference (DCC), pp. 229\u2013238 (2018)","DOI":"10.1109\/DCC.2018.00031"},{"issue":"1","key":"10244_CR6","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":"10244_CR7","doi-asserted-by":"crossref","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, Cham (2023)","DOI":"10.1007\/978-3-031-43980-3_9"},{"issue":"3","key":"10244_CR8","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."},{"issue":"2","key":"10244_CR9","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s00453-009-9350-z","volume":"59","author":"DK Kim","year":"2011","unstructured":"Kim, D.K., Na, J.C., Sim, J.S., Park, K.: Linear-time construction of two-dimensional suffix trees. Algorithmica 59(2), 269\u2013297 (2011). https:\/\/doi.org\/10.1007\/s00453-009-9350-z","journal-title":"Algorithmica"},{"key":"10244_CR10","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":"2\u20133","key":"10244_CR11","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1093\/comjnl\/40.2_and_3.137","volume":"40","author":"JA Storer","year":"1997","unstructured":"Storer, J.A., Helfgott, H.: Lossless image compression by block matching. Comput. J. 40(2\u20133), 137\u2013145 (1997). https:\/\/doi.org\/10.1093\/comjnl\/40.2_and_3.137","journal-title":"Comput. J."},{"issue":"1","key":"10244_CR12","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1109\/TIT.2020.3038147","volume":"67","author":"H Bannai","year":"2021","unstructured":"Bannai, H., Hirayama, M., Hucke, D., Inenaga, S., Jez, A., Lohrey, M., Reh, C.P.: The smallest grammar problem revisited. IEEE Trans. Inf. Theory 67(1), 317\u2013328 (2021)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"2","key":"10244_CR13","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"},{"issue":"1\u20132","key":"10244_CR14","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/s0020-0255(01)00104-9","volume":"135","author":"F Rizzo","year":"2001","unstructured":"Rizzo, F., Storer, J.A., Carpentieri, B.: Lz-based image compression. Inf. Sci. 135(1\u20132), 107\u2013122 (2001). https:\/\/doi.org\/10.1016\/s0020-0255(01)00104-9","journal-title":"Inf. Sci."},{"key":"10244_CR15","doi-asserted-by":"crossref","unstructured":"Giammarresi, D., Restivo, A.: Two-dimensional languages. In: Handbook of formal languages (3), pp. 215\u2013267. Springer, Berlin, Heidelberg, New York (1997)","DOI":"10.1007\/978-3-642-59126-6_4"},{"issue":"2","key":"10244_CR16","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":"10244_CR17","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1145\/3426473","volume":"17","author":"AR Christiansen","year":"2021","unstructured":"Christiansen, A.R., Ettienne, M.B., Kociumaka, T., Navarro, G., Prezza, N.: Optimal-time dictionary-compressed indexes. ACM Trans. Algorithms 17(1), 8\u20131839 (2021)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"10244_CR18","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"},{"key":"10244_CR19","unstructured":"Prezza, N.: On string attractors. In: Proceedings of the 19th Italian Conference on Theoretical Computer Science. ICTCS (2018). https:\/\/ceur-ws.org\/Vol-2243\/award1.pdf"},{"key":"10244_CR20","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":"10244_CR21","unstructured":"Bernardini, G., Fici, G., Gawrychowski, P., Pissis, S.P.: Substring Complexity in Sublinear Space. In: 34th Int. Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), vol. 283, pp. 12\u201311219 (2023)"},{"issue":"7","key":"10244_CR22","doi-asserted-by":"publisher","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"10244_CR23","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2015","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44(3), 513\u2013539 (2015)","journal-title":"SIAM J. Comput."},{"key":"10244_CR24","doi-asserted-by":"crossref","unstructured":"Farach, M., Muthukrishnan, S.: Perfect hashing for strings: Formalization and algorithms. In: Combinatorial pattern matching, pp. 130\u2013140. Springer, Berlin, Heidelberg (1996)","DOI":"10.1007\/3-540-61258-0_11"},{"issue":"4","key":"10244_CR25","doi-asserted-by":"publisher","first-page":"928","DOI":"10.1145\/322344.322346","volume":"29","author":"JA Storer","year":"1982","unstructured":"Storer, J.A., Szymanski, T.G.: Data compression via textual substitution. J. ACM 29(4), 928\u2013951 (1982). https:\/\/doi.org\/10.1145\/322344.322346","journal-title":"J. ACM"},{"key":"10244_CR26","unstructured":"Gallant, J.K.: String compression algorithms. PhD thesis, Princeton University (1982)"},{"key":"10244_CR27","doi-asserted-by":"crossref","unstructured":"Gagie, T., Navarro, G., Prezza, N.: On the approximation ratio of lempel-ziv parsing. In: Proceedings LATIN 2018. LNCS, vol. 10807, pp. 490\u2013503. Springer, Cham (2018)","DOI":"10.1007\/978-3-319-77404-6_36"},{"issue":"1","key":"10244_CR28","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"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10244-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10244-9","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10244-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,3]],"date-time":"2026-01-03T08:42:21Z","timestamp":1767429741000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10244-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1,3]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["10244"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10244-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,1,3]]},"assertion":[{"value":"17 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 January 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"2"}}