{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T06:40:08Z","timestamp":1770532808103,"version":"3.49.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T00:00:00Z","timestamp":1744675200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T00:00:00Z","timestamp":1744675200000},"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":["JP20H05964"],"award-info":[{"award-number":["JP20H05964"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["2022YRB97K"],"award-info":[{"award-number":["2022YRB97K"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["2022YRB97K"],"award-info":[{"award-number":["2022YRB97K"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100021856","name":"Ministero dell'Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["2022YRB97K"],"award-info":[{"award-number":["2022YRB97K"]}],"id":[{"id":"10.13039\/501100021856","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100017142","name":"Gruppo Nazionale per il Calcolo Scientifico","doi-asserted-by":"publisher","award":["CUP E53C2300167001"],"award-info":[{"award-number":["CUP E53C2300167001"]}],"id":[{"id":"10.13039\/100017142","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100017142","name":"Gruppo Nazionale per il Calcolo Scientifico","doi-asserted-by":"publisher","award":["CUP E53C2300167001"],"award-info":[{"award-number":["CUP E53C2300167001"]}],"id":[{"id":"10.13039\/100017142","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100017142","name":"Gruppo Nazionale per il Calcolo Scientifico","doi-asserted-by":"publisher","award":["CUP E53C2300167001"],"award-info":[{"award-number":["CUP E53C2300167001"]}],"id":[{"id":"10.13039\/100017142","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100012990","name":"Universit\u00e0 degli Studi di Siena","doi-asserted-by":"publisher","award":["CUP B73C24001050001"],"award-info":[{"award-number":["CUP B73C24001050001"]}],"id":[{"id":"10.13039\/100012990","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020884","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["2021-21210580"],"award-info":[{"award-number":["2021-21210580"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"publisher"}]},{"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":[[2025,6]]},"abstract":"Abstract<\/jats:title>\n A bit catastrophe, loosely defined, is when a change in just one character of a string causes a significant change in the size of the compressed string. We study this phenomenon for the Burrows-Wheeler Transform (BWT), a string transform at the heart of several of the most popular compressors and aligners today. The parameter determining the size of the compressed data is the number of equal-letter runs of the BWT, commonly denoted r<\/jats:italic>. We exhibit infinite families of strings in which insertion, deletion, resp. substitution of one character increases r<\/jats:italic> from constant to \n \n $$\\Theta (\\log n)$$<\/jats:tex-math>\n \n \n \u0398<\/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>, where n<\/jats:italic> is the length of the string. These strings can be interpreted both as examples for an increase by a multiplicative or an additive \n \n $$\\Theta (\\log n)$$<\/jats:tex-math>\n \n \n \u0398<\/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>-factor. As regards the multiplicative factor, they attain the upper bound given by Akagi, Funakoshi, and Inenaga [Inf & Comput. 2023] of \n \n $$\\mathcal{O}(\\log n \\log r)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n r<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, since here \n \n $$r=\\mathcal{O}(1)$$<\/jats:tex-math>\n \n \n r<\/mml:mi>\n =<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. We then give examples of strings in which insertion, deletion, resp. substitution of a character increases r<\/jats:italic> by a \n \n $$\\Theta (\\sqrt{n})$$<\/jats:tex-math>\n \n \n \u0398<\/mml:mi>\n (<\/mml:mo>\n \n n<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> additive factor. These strings significantly improve the best known lower bound for an additive factor of \n \n $$\\Omega (\\log n)$$<\/jats:tex-math>\n \n \n \u03a9<\/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> [Giuliani et al., SOFSEM 2021].<\/jats:p>","DOI":"10.1007\/s00224-024-10212-9","type":"journal-article","created":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T07:13:16Z","timestamp":1744701196000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Bit Catastrophes for the Burrows-Wheeler Transform"],"prefix":"10.1007","volume":"69","author":[{"given":"Sara","family":"Giuliani","sequence":"first","affiliation":[]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[]},{"given":"Zsuzsanna","family":"Lipt\u00e1k","sequence":"additional","affiliation":[]},{"given":"Giuseppe","family":"Romana","sequence":"additional","affiliation":[]},{"given":"Marinella","family":"Sciortino","sequence":"additional","affiliation":[]},{"given":"Cristian","family":"Urbina","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,4,15]]},"reference":[{"key":"10212_CR1","doi-asserted-by":"publisher","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":"10212_CR2","doi-asserted-by":"crossref","unstructured":"Badkobeh, G.,\u00a0Bannai, H.,\u00a0K\u00f6ppl, D.: Bijective BWT based compression schemes. In: Proc. of 31st International Symposium on String Processing and Information Retrieval (SPIRE 2024), Volume 14899 of Lecture Notes in Computer Science, Cham, pp. 16\u201325. Springer (2024)","DOI":"10.1007\/978-3-031-72200-4_2"},{"key":"10212_CR3","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.tcs.2019.08.005","volume":"812","author":"H Bannai","year":"2020","unstructured":"Bannai, H., Gagie, T., Tomohiro, I.: Refining the r-index. Theor. Comput. Sci. 812, 96\u2013108 (2020)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"10212_CR4","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1016\/S0304-3975(96)00101-6","volume":"178","author":"J Berstel","year":"1997","unstructured":"Berstel, J., de Luca, A.: Sturmian words, Lyndon words and trees. Theor. Comput. Sci. 178(1\u20132), 171\u2013203 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"10212_CR5","unstructured":"Biagi, E.,\u00a0Cenzato, D.,\u00a0Lipt\u00e1k, Zs.,\u00a0Romana, G.: On the number of equal-letter runs of the bijective burrows-wheeler transform. In: G.\u00a0Castiglione and M.\u00a0Sciortino (Eds.), Proceedings of the 24th Italian Conference on Theoretical Computer Science, Palermo, Italy, September 13-15, 2023, Volume 3587 of CEUR Workshop Proceedings, Aachen, pp. 129\u2013142. CEUR-WS.org. (2023)"},{"key":"10212_CR6","doi-asserted-by":"crossref","unstructured":"Boucher, C.,\u00a0Cenzato, D.,\u00a0Lipt\u00e1k, Zs.,\u00a0Rossi, M.,\u00a0Sciortino, M.: Computing the original ebwt faster, simpler, and with less memory. In: Proc. of 28th International Symposium on String Processing and Information Retrieval (SPIRE 2021), Volume 12944 of Lecture Notes in Computer Science, Cham, pp. 129\u2013142. Springer. (2021)","DOI":"10.1007\/978-3-030-86692-1_11"},{"key":"10212_CR7","doi-asserted-by":"crossref","unstructured":"Boucher, C.,\u00a0Cenzato, D.,\u00a0Lipt\u00e1k, Zs.,\u00a0Rossi, M.,\u00a0Sciortino, M.: $$r$$-indexing the eBWT. Inf. Comput.\u00a0298, 105155 (2024)","DOI":"10.1016\/j.ic.2024.105155"},{"key":"10212_CR8","doi-asserted-by":"crossref","unstructured":"Brlek, S.,\u00a0Frosini, A.,\u00a0Mancini, I.,\u00a0Pergola, E.,\u00a0Rinaldi, S.: Burrows-Wheeler Transform of words defined by morphisms. In: IWOCA, Volume 11638 of Lecture Notes in Computer Science, Cham, pp. 393\u2013404. Springer (2019)","DOI":"10.1007\/978-3-030-25005-8_32"},{"key":"10212_CR9","volume-title":"A block-sorting lossless data compression algorithm","author":"M Burrows","year":"1994","unstructured":"Burrows, M., Wheeler, D.J.: A block-sorting lossless data compression algorithm. Technical report, DIGITAL System Research Center (1994)"},{"issue":"43","key":"10212_CR10","doi-asserted-by":"publisher","first-page":"4372","DOI":"10.1016\/j.tcs.2009.07.018","volume":"410","author":"G Castiglione","year":"2009","unstructured":"Castiglione, G., Restivo, A., Sciortino, M.: Circular sturmian words and Hopcroft\u2019s algorithm. Theor. Comput. Sci. 410(43), 4372\u20134381 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"38\u201339","key":"10212_CR11","doi-asserted-by":"publisher","first-page":"3414","DOI":"10.1016\/j.tcs.2010.05.025","volume":"411","author":"G Castiglione","year":"2010","unstructured":"Castiglione, G., Restivo, A., Sciortino, M.: On extremal cases of Hopcroft\u2019s algorithm. Theor. Comput. Sci. 411(38\u201339), 3414\u20133422 (2010)","journal-title":"Theor. Comput. Sci."},{"key":"10212_CR12","doi-asserted-by":"crossref","unstructured":"Cenzato, D., Lipt\u00e1k, Zs.: A survey of BWT variants for string collections. Bioinformatics.\u00a040(7), btae333 (2024)","DOI":"10.1093\/bioinformatics\/btae333"},{"issue":"1","key":"10212_CR13","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/S0304-3975(96)00310-6","volume":"183","author":"A de Luca","year":"1997","unstructured":"de Luca, A.: Sturmian words: structure, combinatorics, and their arithmetics. Theor. Comput. Sci. 183(1), 45\u201382 (1997)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10212_CR14","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/0304-3975(94)00035-H","volume":"136","author":"A de Luca","year":"1994","unstructured":"de Luca, A., Mignosi, F.: Some combinatorial properties of Sturmian words. Theor. Comput. Sci. 136(2), 361\u2013285 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"10212_CR15","doi-asserted-by":"crossref","unstructured":"Ferragina, P.,\u00a0Manzini, G.: Opportunistic data structures with applications. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA, Los Alamitos, CA, pp. 390\u2013398. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"10212_CR16","doi-asserted-by":"crossref","unstructured":"Frosini, A.,\u00a0Mancini, I.,\u00a0Rinaldi, S.,\u00a0Romana, G.,\u00a0Sciortino, M.: Logarithmic equal-letter runs for BWT of purely morphic words. In: Developments in Language Theory - 26th International Conference, DLT 2022, Tampa, FL, USA, May 9-13, 2022, Proceedings, Volume 13257 of Lecture Notes in Computer Science, Cham, pp. 139\u2013151. Springer (2022)","DOI":"10.1007\/978-3-031-05578-2_11"},{"key":"10212_CR17","doi-asserted-by":"crossref","unstructured":"Gagie, T.,\u00a0Navarro, G.,\u00a0Prezza, N.: Optimal-time text indexing in BWT-runs bounded space. In: A.\u00a0Czumaj (Ed.), Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, Philadelphia, PA, pp. 1459\u20131477. SIAM (2018)","DOI":"10.1137\/1.9781611975031.96"},{"key":"10212_CR18","doi-asserted-by":"crossref","unstructured":"Gagie, T.,\u00a0Navarro, G.,\u00a0Prezza, N.: Fully functional suffix trees and optimal text searching in BWT-runs bounded space. J. ACM\u00a067(1), 2:1\u20132:54 (2020)","DOI":"10.1145\/3375890"},{"key":"10212_CR19","doi-asserted-by":"crossref","unstructured":"Giuliani, S.,\u00a0Inenaga, S.,\u00a0Lipt\u00e1k, Zs.,\u00a0Prezza, N.,\u00a0Sciortino, M.,\u00a0Toffanello, A.: Novel results on the number of runs of the Burrows-Wheeler-Transform. In:\u00a0Bures, T.,\u00a0Dondi, R.,\u00a0Gamper, J.,\u00a0Guerrini, G.,\u00a0Jurdzinski, T.,\u00a0Pahl, C.,\u00a0Sikora, F., and Wong, P.W.H. (Eds.), SOFSEM 2021: Theory and Practice of Computer Science - 47th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2021, Bolzano-Bozen, Italy, January 25-29, 2021, Proceedings, Volume 12607 of Lecture Notes in Computer Science, Cham, pp. 249\u2013262. Springer (2021)","DOI":"10.1007\/978-3-030-67731-2_18"},{"key":"10212_CR20","doi-asserted-by":"crossref","unstructured":"Giuliani, S.,\u00a0Inenaga, S.,\u00a0Lipt\u00e1k, Zs.,\u00a0Romana, G.,\u00a0Sciortino, M.,\u00a0Urbina, C.: Bit catastrophes for the Burrows-Wheeler Transform. In:\u00a0Drewes, F. and M.\u00a0Volkov (Eds.), Developments in Language Theory - 27th International Conference, DLT 2023, Ume\u00e5, Sweden, June 12-16, 2023, Proceedings, Volume 13911 of Lecture Notes in Computer Science, Cham, pp. 86\u201399. Springer (2023)","DOI":"10.1007\/978-3-031-33264-7_8"},{"issue":"6","key":"10212_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1145\/3531445","volume":"65","author":"D Kempa","year":"2022","unstructured":"Kempa, D., Kociumaka, T.: Resolution of the Burrows-Wheeler transform conjecture. Commun. ACM 65(6), 91\u201398 (2022)","journal-title":"Commun. ACM"},{"issue":"2","key":"10212_CR22","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10212_CR23","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":"10212_CR24","doi-asserted-by":"crossref","unstructured":"Lagarde, G.,\u00a0Perifel, S.: Lempel-Ziv: a \u201cone-bit catastrophe\u201d but not a tragedy. In A.\u00a0Czumaj (Ed.), Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, Philadelphia, PA, pp. 1478\u20131495. SIAM (2018)","DOI":"10.1137\/1.9781611975031.97"},{"key":"10212_CR25","doi-asserted-by":"crossref","unstructured":"Lam, T.W.,\u00a0Li, R.,\u00a0Tam, A., Wong, S.C.K.,\u00a0Wu, E.,\u00a0Yiu, S.: High throughput short read alignment via bi-directional BWT. In: 2009 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2009, Washington, DC, USA, November 1-4, 2009, Proceedings, Los Alamitos, CA, pp. 31\u201336. IEEE Computer Society (2009)","DOI":"10.1109\/BIBM.2009.42"},{"issue":"4","key":"10212_CR26","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead, B., Salzberg, S.L.: Fast gapped-read alignment with Bowtie 2. Nature Methods 9(4), 357\u2013359 (2012)","journal-title":"Nature Methods"},{"issue":"3","key":"10212_CR27","doi-asserted-by":"publisher","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B Langmead","year":"2009","unstructured":"Langmead, B., Trapnell, C., Pop, M., Salzberg, S.L.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biol. 10(3), R25 (2009)","journal-title":"Genome Biol."},{"issue":"5","key":"10212_CR28","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","volume":"26","author":"H Li","year":"2010","unstructured":"Li, H., Durbin, R.: Fast and accurate long-read alignment with Burrows-Wheeler transform. Bioinform. 26(5), 589\u2013595 (2010)","journal-title":"Bioinform."},{"key":"10212_CR29","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107326019","volume-title":"Algebraic Combinatorics on Words","author":"M Lothaire","year":"2002","unstructured":"Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002)"},{"key":"10212_CR30","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V.,\u00a0Navarro, G.: Succinct Suffix Arrays based on Run-Length Encoding. In:\u00a0Apostolico, A.,\u00a0Crochemore, M., and\u00a0Park, K. (Eds.), Combinatorial Pattern Matching, 16th Annual Symposium, CPM 2005, June 19-22, 2005, Jeju Island, Korea, Proceedings, Volume 3537 of Lecture Notes in Computer Science, Cham, pp. 45\u201356. Springer (2005a)","DOI":"10.1007\/11496656_5"},{"issue":"1","key":"10212_CR31","first-page":"40","volume":"12","author":"V M\u00e4kinen","year":"2005","unstructured":"M\u00e4kinen, V., Navarro, G.: Succinct suffix arrays based on run-length encoding. Nord. J. Comput. 12(1), 40\u201366 (2005)","journal-title":"Nord. J. Comput."},{"issue":"3","key":"10212_CR32","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.tcs.2007.07.014","volume":"387","author":"S Mantaci","year":"2007","unstructured":"Mantaci, S., Restivo, A., Rosone, G., Sciortino, M.: An extension of the Burrows-Wheeler Transform. Theor. Comput. Sci. 387(3), 298\u2013312 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"10212_CR33","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/j.tcs.2017.07.015","volume":"698","author":"S Mantaci","year":"2017","unstructured":"Mantaci, S., Restivo, A., Rosone, G., Sciortino, M., Versari, L.: Measuring the clustering effect of BWT via RLE. Theor. Comput. Sci. 698, 79\u201387 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"10212_CR34","doi-asserted-by":"publisher","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."},{"key":"10212_CR35","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Indexing highly repetitive string collections, part I: repetitiveness measures. ACM Comput. Surv.\u00a054(2), 29:1\u201329:31 (2022)","DOI":"10.1145\/3434399"},{"key":"10212_CR36","doi-asserted-by":"crossref","unstructured":"Rosone, G.,\u00a0Sciortino, M.: The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words. In: P.\u00a0Bonizzoni, V.\u00a0Brattka, and B.\u00a0L\u00f6we (Eds.), The Nature of Computation. Logic, Algorithms, Applications - 9th Conference on Computability in Europe, CiE 2013, Milan, Italy, July 1-5, 2013. Proceedings, Volume 7921 of Lecture Notes in Computer Science, Cham, pp. 353\u2013364. Springer (2013)","DOI":"10.1007\/978-3-642-39053-1_42"},{"key":"10212_CR37","unstructured":"Sciortino, M., Zamboni, L.Q.: Suffix Automata and Standard Sturmian Words. In:\u00a0Harju, T.,\u00a0Karhum\u00e4ki, J., and\u00a0Lepist\u00f6, A. (Eds.), Developments in Language Theory, 11th International Conference, DLT 2007, Turku, Finland, July 3-6, 2007, Proceedings, Volume 4588 of Lecture Notes in Computer Science, Cham, pp. 382\u2013398. Springer (2007)"},{"key":"10212_CR38","unstructured":"Seward, J.: (1996). https:\/\/sourceware.org\/bzip2\/manual\/manual.html"},{"key":"10212_CR39","doi-asserted-by":"crossref","unstructured":"Vasimuddin, M.,\u00a0Misra, S.,\u00a0Li, H.,\u00a0Aluru, S.: Efficient architecture-aware acceleration of BWA-MEM for multicore systems. In: 2019 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2019, Rio de Janeiro, Brazil, May 20-24, 2019, Los Alamitos, CA, pp. 314\u2013324. IEEE Computer Society (2019)","DOI":"10.1109\/IPDPS.2019.00041"},{"issue":"3","key":"10212_CR40","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"},{"issue":"5","key":"10212_CR41","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 Trans. Inf. Theory. 24(5), 530\u2013536 (1978)","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-024-10212-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10212-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10212-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,15]],"date-time":"2025-04-15T07:13:24Z","timestamp":1744701204000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10212-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,15]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10212"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10212-9","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,15]]},"assertion":[{"value":"29 December 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"19"}}