{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T04:14:02Z","timestamp":1743135242372,"version":"3.40.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T00:00:00Z","timestamp":1738627200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T00:00:00Z","timestamp":1738627200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["JP21K17705","JP23K18466"],"award-info":[{"award-number":["JP21K17705","JP23K18466"]}],"id":[{"id":"10.13039\/501100001691","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-00478-y","type":"journal-article","created":{"date-parts":[[2025,2,4]],"date-time":"2025-02-04T11:26:20Z","timestamp":1738668380000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Tight bounds for the sensitivity of CDAWGs with left-end edits"],"prefix":"10.1007","volume":"62","author":[{"given":"Hiroto","family":"Fujimaru","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuto","family":"Nakashima","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shunsuke","family":"Inenaga","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,2,4]]},"reference":[{"key":"478_CR1","doi-asserted-by":"crossref","first-page":"104999","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":"478_CR2","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Cunial, F.: Fast label extraction in the CDAWG. In: SPIRE 2017, pp. 161\u2013175 (2017)","DOI":"10.1007\/978-3-319-67428-5_14"},{"key":"478_CR3","doi-asserted-by":"crossref","unstructured":"Belazzougui, D., Cunial, F., Gagie, T., Prezza, N., Raffinot, M.: Composite repetition-aware data structures. In: CPM 2015, pp. 26\u201339 (2015)","DOI":"10.1007\/978-3-319-19929-0_3"},{"issue":"3","key":"478_CR4","doi-asserted-by":"crossref","first-page":"578","DOI":"10.1145\/28869.28873","volume":"34","author":"A Blumer","year":"1987","unstructured":"Blumer, A., Blumer, J., Haussler, D., McConnell, R., Ehrenfeucht, A.: Complete inverted files for efficient text retrieval and analysis. J. ACM 34(3), 578\u2013595 (1987)","journal-title":"J. ACM"},{"key":"478_CR5","unstructured":"Burrows, M., Wheeler, D.J.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"key":"478_CR6","doi-asserted-by":"crossref","unstructured":"Crochemore, M., V\u00e9rin, R.: On compact directed acyclic word graphs. In: Structures in Logic and Computer Science: A Selection of Essays in Honor of A. Ehrenfeucht, pp. 192\u2013211 (1997)","DOI":"10.1007\/3-540-63246-8_12"},{"key":"478_CR7","doi-asserted-by":"crossref","unstructured":"Fujimaru, H., Nakashima, Y., Inenaga, S.: On sensitivity of compact directed acyclic word graphs. In: WORDS 2023, pp. 168\u2013180 (2023)","DOI":"10.1007\/978-3-031-33180-0_13"},{"issue":"2","key":"478_CR8","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/j.dam.2004.04.012","volume":"146","author":"S Inenaga","year":"2005","unstructured":"Inenaga, S., Hoshino, H., Shinohara, A., Takeda, M., Arikawa, S., Mauri, G., Pavesi, G.: On-line construction of compact directed acyclic word graphs. Discrete Appl. Math. 146(2), 156\u2013179 (2005)","journal-title":"Discrete Appl. Math."},{"key":"478_CR9","doi-asserted-by":"crossref","unstructured":"Kempa, D., Prezza, N.: At the roots of dictionary compression: string attractors. In: STOC 2018, pp. 827\u2013840 (2018)","DOI":"10.1145\/3188745.3188814"},{"issue":"4","key":"478_CR10","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.: Toward a definitive compressibility measure for repetitive sequences. IEEE Trans. Inf. Theory 69(4), 2074\u20132092 (2023)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"478_CR11","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.jda.2011.01.001","volume":"11","author":"J Radoszewski","year":"2012","unstructured":"Radoszewski, J., Rytter, W.: On the structure of compacted subword graphs of Thue\u2013Morse words and their applications. J. Discrete Algor. 11, 15\u201324 (2012)","journal-title":"J. Discrete Algor."},{"key":"478_CR12","doi-asserted-by":"crossref","unstructured":"Senft, M., Dvor\u00e1k, T.: Sliding CDAWG perfection. In: SPIRE 2008, pp. 109\u2013120 (2008)","DOI":"10.1007\/978-3-540-89097-3_12"},{"key":"478_CR13","doi-asserted-by":"crossref","unstructured":"Takagi, T., Goto, K., Fujishige, Y., Inenaga, S., Arimura, H.: Linear-size CDAWG: new repetition-aware indexing and grammar compression. In: SPIRE 2017, pp. 304\u2013316 (2017)","DOI":"10.1007\/978-3-319-67428-5_26"},{"key":"478_CR14","doi-asserted-by":"crossref","unstructured":"Takeda, M., Matsumoto, T., Fukuda, T., Nanri, I.: Discovering characteristic expressions from literary works: a new text analysis method beyond n-gram statistics and KWIC. In: Discovery Science 2000, pp. 112\u2013126 (2000)","DOI":"10.1007\/3-540-44418-1_10"},{"key":"478_CR15","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: Proceedings of the 14th Annual Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"3","key":"478_CR16","doi-asserted-by":"crossref","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":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00478-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-025-00478-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-025-00478-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,28]],"date-time":"2025-03-28T01:48:31Z","timestamp":1743126511000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-025-00478-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,4]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["478"],"URL":"https:\/\/doi.org\/10.1007\/s00236-025-00478-y","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2025,2,4]]},"assertion":[{"value":"14 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 January 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 February 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"12"}}