{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T10:08:59Z","timestamp":1776074939236,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T00:00:00Z","timestamp":1776038400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T00:00:00Z","timestamp":1776038400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["22K11907"],"award-info":[{"award-number":["22K11907"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"publisher","award":["JPMJCR24U4"],"award-info":[{"award-number":["JPMJCR24U4"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2026,6]]},"abstract":"Abstract<\/jats:title>\n \n A Straight-Line Program (SLP)\n \n \n $$\\mathcal {G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for a string\n \n \n $$\\mathcal {T}$$<\/jats:tex-math>\n \n T<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is a context-free grammar (CFG) that derives\n \n \n $$\\mathcal {T}$$<\/jats:tex-math>\n \n T<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n only, which can be considered as a compressed representation of\n \n \n $$\\mathcal {T}$$<\/jats:tex-math>\n \n T<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . In this paper, we show how to encode\n \n \n $$\\mathcal {G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n in\n \n \n $$n \\lceil \\lg N \\rceil + (n + n') \\lceil \\lg (n+\\sigma ) \\rceil + 4n - 2n' + o(n)$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \n \u2308<\/mml:mo>\n lg<\/mml:mo>\n N<\/mml:mi>\n \u2309<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \n (<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n \n n<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \u2308<\/mml:mo>\n lg<\/mml:mo>\n \n (<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n \u03c3<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2309<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n 4<\/mml:mn>\n n<\/mml:mi>\n -<\/mml:mo>\n 2<\/mml:mn>\n \n n<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n +<\/mml:mo>\n o<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n bits to support random access queries of extracting\n \n \n $$\\mathcal {T}[p..q]$$<\/jats:tex-math>\n \n \n T<\/mml:mi>\n [<\/mml:mo>\n p<\/mml:mi>\n .<\/mml:mo>\n .<\/mml:mo>\n q<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n in worst-case\n \n \n $$O(\\log N + q - p)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n N<\/mml:mi>\n +<\/mml:mo>\n q<\/mml:mi>\n -<\/mml:mo>\n p<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n time, where\n N<\/jats:italic>\n is the length of\n \n \n $$\\mathcal {T}$$<\/jats:tex-math>\n \n T<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n ,\n \n \n $$\\sigma $$<\/jats:tex-math>\n \n \u03c3<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the alphabet size,\n n<\/jats:italic>\n is the number of variables in\n \n \n $$\\mathcal {G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $$n' \\le n$$<\/jats:tex-math>\n \n \n \n n<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n \u2264<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is the number of symmetric centroid paths in the DAG representation for\n \n \n $$\\mathcal {G}$$<\/jats:tex-math>\n \n G<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . The time complexity is almost optimal because Verbin and Yu [CPM 2013] proved that\n \n \n $$O(\\log N)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n N<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n term cannot be significantly improved in general with\n \n \n $$\\textrm{poly}(n)$$<\/jats:tex-math>\n \n \n poly<\/mml:mtext>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -space data structures. We also present alternative encodings that achieve the same random access time with\n \n \n $$n \\lceil \\lg N \\rceil + n \\lceil \\lg (n+\\sigma ) \\rceil + 5n + n' + o(n)$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \n \u2308<\/mml:mo>\n lg<\/mml:mo>\n N<\/mml:mi>\n \u2309<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n n<\/mml:mi>\n \n \u2308<\/mml:mo>\n lg<\/mml:mo>\n \n (<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n \u03c3<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2309<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n 5<\/mml:mn>\n n<\/mml:mi>\n +<\/mml:mo>\n \n n<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n +<\/mml:mo>\n o<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n or\n \n \n $$n \\lceil \\lg N \\rceil + n \\lceil \\lg (n+\\sigma ) \\rceil + 5n - n' + \\sigma + o(n+\\sigma )$$<\/jats:tex-math>\n \n \n n<\/mml:mi>\n \n \u2308<\/mml:mo>\n lg<\/mml:mo>\n N<\/mml:mi>\n \u2309<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n n<\/mml:mi>\n \n \u2308<\/mml:mo>\n lg<\/mml:mo>\n \n (<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n \u03c3<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2309<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n 5<\/mml:mn>\n n<\/mml:mi>\n -<\/mml:mo>\n \n n<\/mml:mi>\n \u2032<\/mml:mo>\n <\/mml:msup>\n +<\/mml:mo>\n \u03c3<\/mml:mi>\n +<\/mml:mo>\n o<\/mml:mi>\n \n (<\/mml:mo>\n n<\/mml:mi>\n +<\/mml:mo>\n \u03c3<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n bits of space.\n <\/jats:p>","DOI":"10.1007\/s00224-025-10243-w","type":"journal-article","created":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T09:35:35Z","timestamp":1776072935000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Space-Efficient SLP Encoding for $$O(\\log N)$$-Time Random Access"],"prefix":"10.1007","volume":"70","author":[{"given":"Akito","family":"Takasaka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tomohiro","family":"I","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,4,13]]},"reference":[{"key":"10243_CR1","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Cording, P.H., Puglisi, S.J., Tabei, Y.: Access, rank, and select in grammar-compressed strings. In: Proc. 23rd Annual European Symposium on Algorithms (ESA) 2015, pages 142\u2013154 (2015)","DOI":"10.1007\/978-3-662-48350-3_13"},{"issue":"3","key":"10243_CR2","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":"10243_CR3","doi-asserted-by":"crossref","unstructured":"Cleary, A. M., Winjum, J., Dood, J., Inenaga, S.: Revisiting the folklore algorithm for random access to grammar-compressed strings. In Zsuzsanna Lipt\u00e1k, Edleno\u00a0Silva de\u00a0Moura, Karina Figueroa, and Ricardo Baeza-Yates, editors, Proc. 31st International Symposium on String Processing and Information Retrieval (SPIRE) 2024, volume 14899 of Lecture Notes in Computer Science, pages 88\u2013101. Springer (2024)","DOI":"10.1007\/978-3-031-72200-4_7"},{"key":"10243_CR4","doi-asserted-by":"crossref","unstructured":"Gagie, T., I, T., Manzini, G., Navarro, G., Sakamoto, H., Seelbach Benkner, L., Takabatake, Y.: Practical random access to slp-compressed texts. In: Proc. 27th International Symposium on String Processing and Information Retrieval (SPIRE) 2020, volume 12303 of Lecture Notes in Computer Science, pages 221\u2013231. Springer (2020)","DOI":"10.1007\/978-3-030-59212-7_16"},{"key":"10243_CR5","unstructured":"Ganardi, M.: Compression by contracting straight-line programs. In: Petra Mutzel, Rasmus Pagh, and Grzegorz Herman, editors, Proc. 29th Annual European Symposium on Algorithms (ESA) 2021, volume 204 of LIPIcs, pages 45:1\u201345:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"4","key":"10243_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3457389","volume":"68","author":"M Ganardi","year":"2021","unstructured":"Ganardi, M., Jez, A., Lohrey, M.: Balancing straight-line programs. J. ACM 68(4), 1\u201340 (2021)","journal-title":"J. ACM"},{"key":"10243_CR7","doi-asserted-by":"crossref","unstructured":"Jacobson, G.: Space-efficient static trees and graphs. In Proc. 30th Annual Symposium on Foundations of Computer Science (FOCS) 1989, pages 549\u2013554. IEEE Computer Society (1989)","DOI":"10.1109\/SFCS.1989.63533"},{"key":"10243_CR8","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., Moffat, A.: Offline dictionary-based compression. In: Proc. Data Compression Conference (DCC) 1999, pages 296\u2013305 (1999)","DOI":"10.1109\/DCC.1999.755679"},{"issue":"1","key":"10243_CR9","doi-asserted-by":"publisher","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. Information Theory 22(1), 75\u201381 (1976)","journal-title":"IEEE Trans. Information Theory"},{"issue":"2","key":"10243_CR10","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1515\/gcc-2012-0016","volume":"4","author":"M Lohrey","year":"2012","unstructured":"Lohrey, M.: Algorithmics on slp-compressed strings: A survey. Groups Complexity Cryptology 4(2), 241\u2013299 (2012)","journal-title":"Groups Complexity Cryptology"},{"key":"10243_CR11","doi-asserted-by":"crossref","unstructured":"Maruyama, S., Tabei, Y., Sakamoto, H., Sadakane, K.: Fully-online grammar compression. In: Proc. 20th International Symposium on String Processing and Information Retrieval (SPIRE) 2013, pages 218\u2013229 (2013)","DOI":"10.1007\/978-3-319-02432-5_25"},{"issue":"4","key":"10243_CR12","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1145\/321479.321481","volume":"15","author":"DR Morrison","year":"1968","unstructured":"Morrison, D.R.: PATRICIA - practical algorithm to retrieve information coded in alphanumeric. J. ACM 15(4), 514\u2013534 (1968)","journal-title":"J. ACM"},{"issue":"3","key":"10243_CR13","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1145\/2601073","volume":"10","author":"G Navarro","year":"2014","unstructured":"Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"10243_CR14","doi-asserted-by":"crossref","unstructured":"Rajeev Raman, Venkatesh Raman, and Srinivasa\u00a0Rao Satti. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets. ACM Trans. Algorithms, 3(4), 2007","DOI":"10.1145\/1290672.1290680"},{"key":"10243_CR15","doi-asserted-by":"crossref","unstructured":"Tabei, Y., Takabatake, Y., Sakamoto, H.: A succinct grammar compression. In: Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM) 2013, volume 7922 of Lecture Notes in Computer Science, pages 235\u2013246. Springer (2013)","DOI":"10.1007\/978-3-642-38905-4_23"},{"key":"10243_CR16","unstructured":"Takabatake, Y., Tomohiro I, Sakamoto, H.: A space-optimal grammar compression. In: Proc. 25th Annual European Symposium on Algorithms (ESA) 2017, volume\u00a087 of LIPIcs, pages 67:1\u201367:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017)"},{"key":"10243_CR17","doi-asserted-by":"crossref","unstructured":"Takasaka, A., Tomohiro, I.: Space-efficient SLP encoding for o(log n)-time random access. In: Proc. 31st International Symposium on String Processing and Information Retrieval (SPIRE) 2024, volume 14899 of Lecture Notes in Computer Science, pages 336\u2013347. Springer (2024)","DOI":"10.1007\/978-3-031-72200-4_25"},{"key":"10243_CR18","doi-asserted-by":"crossref","unstructured":"Verbin, E., Yu, W.: Data structure lower bounds on random access to grammar-compressed strings. In: Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM) 2013, pages 247\u2013258 (2013)","DOI":"10.1007\/978-3-642-38905-4_24"},{"issue":"2","key":"10243_CR19","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"DE Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space theta(n). Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"10243_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23(3), 337\u2013343 (1977)","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-10243-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-025-10243-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-025-10243-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T09:35:47Z","timestamp":1776072947000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-025-10243-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,13]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["10243"],"URL":"https:\/\/doi.org\/10.1007\/s00224-025-10243-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,13]]},"assertion":[{"value":"16 February 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":"13 April 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":"28"}}