{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:17:14Z","timestamp":1786979834442,"version":"build-2736575974"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T00:00:00Z","timestamp":1739404800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["FB0001"],"award-info":[{"award-number":["FB0001"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["FB0001"],"award-info":[{"award-number":["FB0001"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["FB0001"],"award-info":[{"award-number":["FB0001"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2025,3]]},"DOI":"10.1007\/s00236-025-00481-3","type":"journal-article","created":{"date-parts":[[2025,2,13]],"date-time":"2025-02-13T17:17:21Z","timestamp":1739467041000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Generalized straight-line programs"],"prefix":"10.1007","volume":"62","author":[{"given":"Gonzalo","family":"Navarro","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Francisco","family":"Olivares","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cristian","family":"Urbina","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,2,13]]},"reference":[{"key":"481_CR1","doi-asserted-by":"crossref","DOI":"10.1016\/j.ic.2022.104999","volume":"291","author":"T Akagi","year":"2023","unstructured":"Akagi, T., Funakoshi, M., Inenaga, S.: Sensitivity of string compressors and repetitiveness measures. Inf. Comput. 291, 104999 (2023)","journal-title":"Inf. Comput."},{"key":"481_CR2","first-page":"1","volume-title":"Sequences and their Applications","author":"JP Allouche","year":"1999","unstructured":"Allouche, J.P., Shallit, J.: The ubiquitous prouhet-thue-morse sequence. In: Ding, C., Helleseth, T., Niederreiter, H. (eds.) Sequences and their Applications, pp. 1\u201316. Springer, London (1999)"},{"key":"481_CR3","doi-asserted-by":"crossref","unstructured":"Bannai, H., Funakoshi, M., I, T., et\u00a0al.: A separation of $$\\gamma $$ and b via Thue-Morse words. In: Proceedings of the 28th International Symposium on String Processing and Information Retrieval (SPIRE), pp. 167\u2013178 (2021)","DOI":"10.1007\/978-3-030-86692-1_14"},{"key":"481_CR4","first-page":"08209","volume":"2403","author":"H Bannai","year":"2024","unstructured":"Bannai, H., Funakoshi, M., Hendrian, D., et al.: Height-bounded lempel-ziv encodings. CoRR 2403, 08209 (2024)","journal-title":"CoRR"},{"issue":"3","key":"481_CR5","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/130936889","volume":"44","author":"P Bille","year":"2015","unstructured":"Bille, P., Landau, G.M., Raman, R., et al.: Random access to grammar-compressed strings and trees. SIAM J. Comput. 44(3), 513\u2013539 (2015)","journal-title":"SIAM J. Comput."},{"key":"481_CR6","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.jcss.2017.01.002","volume":"86","author":"P Bille","year":"2017","unstructured":"Bille, P., G\u00f8rtz, I.L., Cording, P.H., et al.: Fingerprints in compressed strings. J. Comput. Syst. Sci. 86, 171\u2013180 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"481_CR7","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.jda.2018.09.002","volume":"50","author":"P Bille","year":"2018","unstructured":"Bille, P., Gagie, T., G\u00f8rtz, I.L., et al.: A separation between RLSLPs and LZ77. J. Discrete Algorithms 50, 36\u201339 (2018)","journal-title":"J. Discrete Algorithms"},{"key":"481_CR8","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Tech. Rep. 124, Digital Equipment Corporation (1994)"},{"issue":"7","key":"481_CR9","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., et al.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"481_CR10","first-page":"8","volume":"17","author":"AR Christiansen","year":"2020","unstructured":"Christiansen, A.R., Ettienne, M.B., Kociumaka, T., et al.: Optimal-time dictionary-compressed indexes. ACM Trans. Algorithms 17(1), 8 (2020)","journal-title":"ACM Trans. Algorithms"},{"key":"481_CR11","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.jcss.2020.12.001","volume":"118","author":"F Claude","year":"2021","unstructured":"Claude, F., Navarro, G., Pacheco, A.: Grammar-compressed indexes with logarithmic search time. J. Comput. Syst. Sci. 118, 53\u201374 (2021)","journal-title":"J. Comput. Syst. Sci."},{"key":"481_CR12","unstructured":"Fici, G., Romana, G., Sciortino, M., et\u00a0al.: On the impact of morphisms on BWT-runs. In: Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching (CPM), pp 10:1\u201310:18 (2023)"},{"issue":"2","key":"481_CR13","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"issue":"51","key":"481_CR14","doi-asserted-by":"crossref","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","volume":"410","author":"J Fischer","year":"2009","unstructured":"Fischer, J., M\u00e4kinen, V., Navarro, G.: Faster entropy-bounded compressed suffix trees. Theoret. Comput. Sci. 410(51), 5354\u20135364 (2009)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"481_CR15","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/3375890","volume":"67","author":"T Gagie","year":"2020","unstructured":"Gagie, T., Navarro, G., Prezza, N.: Fully-functional suffix trees and optimal text searching in BWT-runs bounded space. J. ACM 67(1), 2 (2020)","journal-title":"J. ACM"},{"key":"481_CR16","unstructured":"Gallant, J.K.: String Compression Algorithms. PhD thesis, Princeton University (1982)"},{"issue":"4","key":"481_CR17","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1145\/3457389","volume":"68","author":"M Ganardi","year":"2021","unstructured":"Ganardi, M., Je\u017c, A., Lohrey, M.: Balancing straight-line programs. J. ACM 68(4), 27 (2021)","journal-title":"J. ACM"},{"key":"481_CR18","doi-asserted-by":"crossref","unstructured":"Giuliani, S., Inenaga, S., Lipt\u00e1k, Z., et\u00a0al.: Novel results on the number of runs of the Burrows-Wheeler-transform. In: Proceedings of the Theory and Practice of Computer Science (SOFSEM), pp. 249\u2013262 (2021)","DOI":"10.1007\/978-3-030-67731-2_18"},{"key":"481_CR19","doi-asserted-by":"crossref","unstructured":"Giuliani, S., Inenaga, S., Lipt\u00e1k Z, et\u00a0al.: Bit catastrophes for the burrows-wheeler transform. In: Proceedings of the Developments in Language Theory (DLT), pp. 86\u2013 99 (2023)","DOI":"10.1007\/978-3-031-33264-7_8"},{"issue":"3","key":"481_CR20","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1016\/0166-218X(83)90002-1","volume":"5","author":"J Karhum\u00e4ki","year":"1983","unstructured":"Karhum\u00e4ki, J.: On cube-free $$\\omega $$-words generated by binary morphisms. Discret. Appl. Math. 5(3), 279\u2013297 (1983)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"481_CR21","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"481_CR22","doi-asserted-by":"crossref","unstructured":"Kawamoto, A. I. T., K\u00f6ppl, D., et\u00a0al.: On the hardness of smallest RLSLPs and collage systems. In: Proceedings of the Data Compression Conference (DCC), pp. 243\u2013252 (2024)","DOI":"10.1109\/DCC58796.2024.00032"},{"key":"481_CR23","doi-asserted-by":"crossref","unstructured":"Kempa, D., Kociumaka, T.: Resolution of the Burrows-Wheeler transform conjecture. In: Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 1002\u20131013 (2020)","DOI":"10.1109\/FOCS46700.2020.00097"},{"key":"481_CR24","doi-asserted-by":"crossref","unstructured":"Kempa, D., Kociumaka, T.: Collapsing the hierarchy of compressed data structures: Suffix arrays in optimal compressed space. In: Proceedings of the IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pp. 1877\u20131886 (2023)","DOI":"10.1109\/FOCS57990.2023.00114"},{"key":"481_CR25","doi-asserted-by":"crossref","unstructured":"Kempa, D., Prezza, N.: At the roots of dictionary compression: String attractors. In: Proceedings of the 50th Annual ACM Symposium on the Theory of Computing (STOC), pp. 827\u2013840 (2018)","DOI":"10.1145\/3188745.3188814"},{"key":"481_CR26","doi-asserted-by":"crossref","unstructured":"Kempa, D., Saha, B.: An upper bound and linear-space queries on the LZ-End parsing. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2847\u20132866 (2022)","DOI":"10.1137\/1.9781611977073.111"},{"key":"481_CR27","unstructured":"Knuth, D.E.: Johann Faulhaber and sums of powers. In: Selected Papers on Discrete Mathematics. Cambridge University Press (2001)"},{"issue":"4","key":"481_CR28","doi-asserted-by":"crossref","first-page":"2074","DOI":"10.1109\/TIT.2022.3224382","volume":"69","author":"T Kociumaka","year":"2023","unstructured":"Kociumaka, T., Navarro, G., Prezza, N.: Towards a definitive compressibility measure for repetitive sequences. IEEE Trans. Inf. Theory 69(4), 2074\u20132092 (2023)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"481_CR29","doi-asserted-by":"crossref","first-page":"1031","DOI":"10.1007\/s00453-023-01186-0","volume":"86","author":"T Kociumaka","year":"2024","unstructured":"Kociumaka, T., Navarro, G., Olivares, F.: Near-optimal search time in $$\\delta $$-optimal space, and vice versa. Algorithmica 86(4), 1031\u20131056 (2024)","journal-title":"Algorithmica"},{"key":"481_CR30","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","volume":"483","author":"S Kreft","year":"2013","unstructured":"Kreft, S., Navarro, G.: On compressing and indexing repetitive sequences. Theoret. Comput. Sci. 483, 115\u2013133 (2013)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"481_CR31","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/TIT.1976.1055501","volume":"22","author":"A Lempel","year":"1976","unstructured":"Lempel, A., Ziv, J.: On the complexity of finite sequences. IEEE Trans. Inf. Theory 22(1), 75\u201381 (1976)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"481_CR32","doi-asserted-by":"crossref","unstructured":"Lindenmayer, A.: Mathematical models for cellular interactions in development I. Filaments with one-sided inputs. J. Theoret. Biol. 18(3):280\u2013299 (1968a)","DOI":"10.1016\/0022-5193(68)90079-9"},{"issue":"3","key":"481_CR33","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1016\/0022-5193(68)90080-5","volume":"18","author":"A Lindenmayer","year":"1968","unstructured":"Lindenmayer, A.: Mathematical models for cellular interactions in development II. Simple and branching filaments with two-sided inputs. J. Theoret. Biol. 18(3), 300\u2013315 (1968)","journal-title":"J. Theoret. Biol."},{"issue":"5","key":"481_CR34","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/S0020-0190(02)00512-4","volume":"86","author":"S Mantaci","year":"2003","unstructured":"Mantaci, S., Restivo, A., Sciortino, M.: Burrows-Wheeler transform and Sturmian words. Inf. Process. Lett. 86(5), 241\u2013246 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"481_CR35","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."},{"issue":"2","key":"481_CR36","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":"481_CR37","doi-asserted-by":"crossref","unstructured":"Navarro, G., Urbina., C.: On stricter reachable repetitiveness measures. In: Proceedings of the 28th International Symposium on String Processing and Information Retrieval (SPIRE), pp. 193\u2013206 (2021)","DOI":"10.1007\/978-3-030-86692-1_16"},{"key":"481_CR38","unstructured":"Navarro, G., Urbina, C.: L-systems for measuring repetitiveness. In: Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching (CPM), p. 14 (2023)"},{"key":"481_CR39","doi-asserted-by":"crossref","unstructured":"Navarro, G., Urbina, C.: Iterated straight-line programs. In: Proceedings of the 16th Latin American Theoretical Informatics (LATIN), pp. 66\u201380 (2024)","DOI":"10.1007\/978-3-031-55598-5_5"},{"issue":"2","key":"481_CR40","doi-asserted-by":"crossref","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"},{"key":"481_CR41","doi-asserted-by":"crossref","unstructured":"Navarro, G., Olivares, F., Urbina, C.: Balancing run-length straight-line programs. In: Proceedings of the 29th International Symposium on String Processing and Information Retrieval (SPIRE), pp. 117\u2013131 (2022)","DOI":"10.1007\/978-3-031-20643-6_9"},{"key":"481_CR42","doi-asserted-by":"crossref","unstructured":"Nekrich, Y., Navarro, G.: Sorted range reporting. In: Proceedings of the 13th Scandinavian Symposium on Algorithmic Theory (SWAT), LNCS 7357, pp. 271\u2013282 (2012)","DOI":"10.1007\/978-3-642-31155-0_24"},{"issue":"3","key":"481_CR43","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1007\/s00453-012-9618-6","volume":"65","author":"S Raskhodnikova","year":"2013","unstructured":"Raskhodnikova, S., Ron, D., Rubinfeld, R., et al.: Sublinear algorithms for approximating string compressibility. Algorithmica 65(3), 685\u2013709 (2013)","journal-title":"Algorithmica"},{"key":"481_CR44","volume-title":"Introduction to the Theory of Computation","author":"M Sipser","year":"2012","unstructured":"Sipser, M.: Introduction to the Theory of Computation. Cengage Learning, Boston (2012)"},{"issue":"4","key":"481_CR45","doi-asserted-by":"crossref","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)","journal-title":"J. ACM"},{"key":"481_CR46","doi-asserted-by":"crossref","unstructured":"Verbin, E., Yu, W.: Data structure lower bounds on random access to grammar-compressed strings. In: Proceedings of the 24th Annual Symposium on Combinatorial Pattern Matching (CPM), pp. 247\u2013258 (2013)","DOI":"10.1007\/978-3-642-38905-4_24"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00481-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00481-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00481-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T21:50:51Z","timestamp":1743112251000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00481-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,13]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["481"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00481-3","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,13]]},"assertion":[{"value":"1 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval"}},{"value":"All authors agreed to participate in this work.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent to participate"}},{"value":"All authors agree for the publication of this work.","order":5,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}],"article-number":"14"}}