{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,11]],"date-time":"2026-09-11T23:13:41Z","timestamp":1789168421688,"version":"build-2803163510"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2022,5,20]],"date-time":"2022-05-20T00:00:00Z","timestamp":1653004800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018364"],"award-info":[{"award-number":["2018364"]}],"id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1652303, 1934846"],"award-info":[{"award-number":["1652303, 1934846"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1278\/16, 1926\/19"],"award-info":[{"award-number":["1278\/16, 1926\/19"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["683064"],"award-info":[{"award-number":["683064"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1145\/3531445","type":"journal-article","created":{"date-parts":[[2022,5,20]],"date-time":"2022-05-20T10:56:52Z","timestamp":1653044212000},"page":"91-98","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Resolution of the burrows-wheeler transform conjecture"],"prefix":"10.1145","volume":"65","author":[{"given":"Dominik","family":"Kempa","sequence":"first","affiliation":[{"name":"Johns Hopkins University, Baltimore, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,5,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.08.005"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19929-0_3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2018.09.002"},{"key":"e_1_2_1_5_1","volume-title":"Fully-functional suffix trees and optimal text searching in BWT-runs bounded space. arXiv","author":"Gagie T.","year":"1809","unstructured":"Gagie , T. , Navarro , G. , Prezza , N. Fully-functional suffix trees and optimal text searching in BWT-runs bounded space. arXiv 1809 .02792 (2018). Gagie, T., Navarro, G., Prezza, N. Fully-functional suffix trees and optimal text searching in BWT-runs bounded space. arXiv 1809.02792 (2018)."},{"key":"e_1_2_1_6_1","volume-title":"LATIN","author":"Gagie T.","year":"2018","unstructured":"Gagie , T. , Navarro , G. , Prezza , N. On the approximation ratio of Lempel--Ziv parsing . In LATIN ( 2018 ), Springer , Cham, Switzerland , 490--503. Gagie, T., Navarro, G., Prezza, N. On the approximation ratio of Lempel--Ziv parsing. In LATIN (2018), Springer, Cham, Switzerland, 490--503."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375890"},{"key":"e_1_2_1_8_1","volume-title":"SODA","author":"Grossi R.","year":"2003","unstructured":"Grossi , R. , Gupta , A. , Vitter , J.S. High-order entropy-compressed text indexes . In SODA ( 2003 ), ACM\/SIAM , Philadelphia, PA, USA , 841--850. Grossi, R., Gupta, A., Vitter, J.S. High-order entropy-compressed text indexes. In SODA (2003), ACM\/SIAM, Philadelphia, PA, USA, 841--850."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.12.009"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.82"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316368"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188814"},{"key":"e_1_2_1_13_1","volume-title":"LATIN","author":"Kociumaka T.","year":"2020","unstructured":"Kociumaka , T. , Navarro , G. , Prezza , N. Towards a definitive measure of repetitiveness . In LATIN ( 2020 ), Springer , Cham, Switzerland , 207--219. Kociumaka, T., Navarro, G., Prezza, N. Towards a definitive measure of repetitiveness. In LATIN (2020), Springer, Cham, Switzerland, 207--219."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.006"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139940023"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382782"},{"key":"e_1_2_1_17_1","first-page":"2","article-title":"Indexing highly repetitive string collections, part I: Repetitiveness measures","volume":"54","author":"Navarro G","year":"2021","unstructured":"Navarro , G . Indexing highly repetitive string collections, part I: Repetitiveness measures . ACM Comput. Surv. 54 , 2 ( 2021 ), 1--31. Navarro, G. Indexing highly repetitive string collections, part I: Repetitiveness measures. ACM Comput. Surv. 54, 2 (2021), 1--31.","journal-title":"ACM Comput. Surv."},{"key":"e_1_2_1_18_1","first-page":"2","article-title":"Indexing highly repetitive string collections, part II: Compressed indexes","volume":"54","author":"Navarro G","year":"2021","unstructured":"Navarro , G . Indexing highly repetitive string collections, part II: Compressed indexes . ACM Comput. Surv. 54 , 2 ( 2021 ), 1--32. Navarro, G. Indexing highly repetitive string collections, part II: Compressed indexes. ACM Comput. Surv. 54, 2 (2021), 1--32.","journal-title":"ACM Comput. Surv."},{"key":"e_1_2_1_19_1","volume-title":"Genome Rearrangements, and Phylogenetic Reconstruction","author":"Ohlebusch E.","year":"2013","unstructured":"Ohlebusch , E. Bioinformatics Algorithms: Sequence Analysis , Genome Rearrangements, and Phylogenetic Reconstruction . Oldenbusch Verlag, Bremen , Germany , 2013 . Ohlebusch, E. Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag, Bremen, Germany, 2013."},{"key":"e_1_2_1_20_1","first-page":"52","article-title":"A faster implementation of online RLBWT and its application to LZ77 parsing","author":"Ohno T.","year":"2018","unstructured":"Ohno , T. , Sakai , K. , Takabatake , Y. , Tomohiro , I , Sakamoto , H . A faster implementation of online RLBWT and its application to LZ77 parsing . J. Discrete Algorithms, ( 2018 ), 52 - 53 :18--28. Ohno, T., Sakai, K., Takabatake, Y., Tomohiro, I, Sakamoto, H. A faster implementation of online RLBWT and its application to LZ77 parsing. J. Discrete Algorithms, (2018), 52-53:18--28.","journal-title":"J. Discrete Algorithms, ("},{"key":"e_1_2_1_21_1","volume-title":"Bioinformatics and Functional Genomics","author":"Pevsner J.","year":"2015","unstructured":"Pevsner , J. Bioinformatics and Functional Genomics , 3 rd edn. Wiley-Blackwell , Chichester, UK , 2015 . Pevsner, J. Bioinformatics and Functional Genomics, 3rd edn. Wiley-Blackwell, Chichester, UK, 2015.","edition":"3"},{"key":"e_1_2_1_22_1","first-page":"1","article-title":"to the run-length encoded Burrows-Wheeler transform, and back. In CPM (2017), Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl","volume":"17","author":"Policriti A.","unstructured":"Policriti , A. , Prezza , N. From LZ77 to the run-length encoded Burrows-Wheeler transform, and back. In CPM (2017), Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl , Germany , 17 : 1 -- 17 :10. Policriti, A., Prezza, N. From LZ77 to the run-length encoded Burrows-Wheeler transform, and back. In CPM (2017), Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 17:1--17:10.","journal-title":"Germany"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0327-z"},{"key":"e_1_2_1_24_1","volume-title":"SPIRE","author":"Sir\u00e9n J.","year":"2008","unstructured":"Sir\u00e9n , J. , V\u00e4lim\u00e4ki , N. , M\u00e4kinen , V. , Navarro , G. Run-length compressed indexes are superior for highly repetitive sequence collections . In SPIRE ( 2008 ), Springer , Berlin, Heidelberg , Germany, 164--175. Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V., Navarro, G. Run-length compressed indexes are superior for highly repetitive sequence collections. In SPIRE (2008), Springer, Berlin, Heidelberg, Germany, 164--175."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1977.1055714"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531445","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531445","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3531445","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T14:09:21Z","timestamp":1750169361000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3531445"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,20]]},"references-count":24,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["10.1145\/3531445"],"URL":"https:\/\/doi.org\/10.1145\/3531445","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,20]]},"assertion":[{"value":"2022-05-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}