{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T00:03:44Z","timestamp":1780704224644,"version":"3.54.1"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032284037","type":"print"},{"value":"9783032284044","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-28404-4_17","type":"book-chapter","created":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T23:19:07Z","timestamp":1780701547000},"page":"223-237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Efficient Computation of\u00a0Discriminative Absent Words for\u00a0String Collections"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1838-9785","authenticated-orcid":false,"given":"Giuseppa","family":"Castigione","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9200-0520","authenticated-orcid":false,"given":"Sabrina","family":"Mantaci","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1972-6931","authenticated-orcid":false,"given":"Antonio","family":"Restivo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3489-0684","authenticated-orcid":false,"given":"Giuseppe","family":"Romana","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6928-0168","authenticated-orcid":false,"given":"Marinella","family":"Sciortino","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,6]]},"reference":[{"key":"17_CR1","doi-asserted-by":"publisher","unstructured":"B\u00e9al, M., Crochemore, M.: Fast detection of specific fragments against a set of sequences. In: DLT, volume 13911 of Lecture Notes in Computer Science, pp. 51\u201360. Springer (2023). https:\/\/doi.org\/10.1007\/978-3-031-33264-7_5","DOI":"10.1007\/978-3-031-33264-7_5"},{"key":"17_CR2","doi-asserted-by":"publisher","unstructured":"B\u00e9al, M., Crochemore, M.: Specific patterns against reference sequences. In: From Strings to Graphs, and Back Again, volume 132 of OASIcs, pp. 14:1\u201314:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/OASICS.GROSSI.14","DOI":"10.4230\/OASICS.GROSSI.14"},{"issue":"1\u20132","key":"17_CR3","first-page":"121","volume":"56","author":"M-P B\u00e9al","year":"2003","unstructured":"B\u00e9al, M.-P., Crochemore, M., Mignosi, F., Restivo, A., Sciortino, M.: Computing forbidden words of regular languages. Fund. Inform. 56(1\u20132), 121\u2013135 (2003)","journal-title":"Fund. Inform."},{"issue":"2","key":"17_CR4","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1006\/AAMA.2000.0682","volume":"25","author":"M-P B\u00e9al","year":"2000","unstructured":"B\u00e9al, M.-P., Mignosi, F., Restivo, A., Sciortino, M.: Forbidden words in symbolic dynamics. Adv. Appl. Math. 25(2), 163\u2013193 (2000). https:\/\/doi.org\/10.1006\/AAMA.2000.0682","journal-title":"Adv. Appl. Math."},{"key":"17_CR5","doi-asserted-by":"publisher","unstructured":"Bonizzoni, P., De Felice, C., Pirola, Y., Rizzi, R., Zaccagnino, R., Zizza, R.: Can formal languages help pangenomics to represent and analyze multiple genomes? In: DLT, volume 13257 of Lecture Notes in Computer Science, pp. 3\u201312. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-05578-2_1","DOI":"10.1007\/978-3-031-05578-2_1"},{"key":"17_CR6","doi-asserted-by":"publisher","unstructured":"Brown, N.K., Gagie, T., Manzini, G., Navarro, G., Sciortino, M.: Faster run-length compressed suffix arrays. In: From Strings to Graphs, and Back Again, volume 132 of OASIcs, pp. 10:1\u201310:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/OASICS.GROSSI.10","DOI":"10.4230\/OASICS.GROSSI.10"},{"key":"17_CR7","unstructured":"Castiglione, G., Mantaci, S., Pizzuto, S.L., Restivo, A.: A comparison between similarity measures based on minimal absent words: an experimental approach. In: ICTCS, volume 3811 of CEUR Workshop Proceedings, pp. 95\u2013105. CEUR-WS.org (2024). https:\/\/ceur-ws.org\/Vol-3811\/paper140.pdf"},{"issue":"1\u20134","key":"17_CR8","doi-asserted-by":"publisher","first-page":"97","DOI":"10.3233\/FI-2020-1874","volume":"171","author":"G Castiglione","year":"2020","unstructured":"Castiglione, G., Mantaci, S., Restivo, A.: Some investigations on similarity measures based on absent words. Fundam. Informaticae 171(1\u20134), 97\u2013112 (2020). https:\/\/doi.org\/10.3233\/FI-2020-1874","journal-title":"Fundam. Informaticae"},{"key":"17_CR9","doi-asserted-by":"publisher","unstructured":"Cenzato, D., Lipt\u00e1k, Z.: A survey of BWT variants for string collections. Bioinform. 40(6) (2024). https:\/\/doi.org\/10.1093\/BIOINFORMATICS\/BTAE333","DOI":"10.1093\/BIOINFORMATICS\/BTAE333"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.tcs.2012.04.031","volume":"450","author":"S Chairungsee","year":"2012","unstructured":"Chairungsee, S., Crochemore, M.: Using minimal absent words to build phylogeny. Theor. Comput. Sci. 450, 109\u2013116 (2012). https:\/\/doi.org\/10.1016\/j.tcs.2012.04.031","journal-title":"Theor. Comput. Sci."},{"key":"17_CR11","doi-asserted-by":"publisher","unstructured":"Charalampopoulos, P., Crochemore, M., Fici, G., Mercas, R., Pissis, S.P.: Alignment-free sequence comparison using absent words. Inf. Comput. 262(Part), 57\u201368 (2018). https:\/\/doi.org\/10.1016\/j.ic.2018.06.002","DOI":"10.1016\/j.ic.2018.06.002"},{"issue":"1\u20133","key":"17_CR12","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/J.TCS.2004.11.014","volume":"332","author":"M Crochemore","year":"2005","unstructured":"Crochemore, M., D\u00e9sarm\u00e9nien, J., Perrin, D.: A note on the burrows - wheeler transformation. Theor. Comput. Sci. 332(1\u20133), 567\u2013572 (2005). https:\/\/doi.org\/10.1016\/J.TCS.2004.11.014","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"17_CR13","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0020-0190(98)00104-5","volume":"67","author":"M Crochemore","year":"1998","unstructured":"Crochemore, M., Mignosi, F., Restivo, A.: Automata and forbidden words. Inf. Process. Lett. 67(3), 111\u2013117 (1998). https:\/\/doi.org\/10.1016\/S0020-0190(98)00104-5","journal-title":"Inf. Process. Lett."},{"issue":"11","key":"17_CR14","doi-asserted-by":"publisher","first-page":"1756","DOI":"10.1109\/5.892711","volume":"88","author":"M Crochemore","year":"2000","unstructured":"Crochemore, M., Mignosi, F., Restivo, A., Salemi, S.: Data compression using antidictionaries. Proc. IEEE 88(11), 1756\u20131768 (2000). https:\/\/doi.org\/10.1109\/5.892711","journal-title":"Proc. IEEE"},{"key":"17_CR15","doi-asserted-by":"publisher","unstructured":"Ferragina, P., Lari, F.: FL-RMQ: a learned approach to range minimum queries. In: CPM, volume 331 of LIPIcs, pp. 7:1\u20137:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/LIPICS.CPM.2025.7","DOI":"10.4230\/LIPICS.CPM.2025.7"},{"key":"17_CR16","doi-asserted-by":"publisher","unstructured":"Fici, G., Mantaci, S., Restivo, A., Romana, G., Rosone, G., Sciortino, M.: BWT and combinatorics on words. In: The Expanding World of Compressed Data, volume 131 of OASIcs, pp. 1:1\u20131:23. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/OASICS.MANZINI.1","DOI":"10.4230\/OASICS.MANZINI.1"},{"issue":"2","key":"17_CR17","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/090779759","journal-title":"SIAM J. Comput."},{"key":"17_CR18","doi-asserted-by":"publisher","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:1\u20132:54 (2020). https:\/\/doi.org\/10.1145\/3375890","DOI":"10.1145\/3375890"},{"key":"17_CR19","doi-asserted-by":"publisher","unstructured":"Garofalo, F., Rosone, G., Sciortino, M., Verzotto, D.: The colored longest common prefix array computed via sequential scans. In: SPIRE, volume 11147 of Lecture Notes in Computer Science, pp. 153\u2013167. Springer (2018). https:\/\/doi.org\/10.1007\/978-3-030-00479-8_13","DOI":"10.1007\/978-3-030-00479-8_13"},{"key":"17_CR20","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/J.TCS.2019.07.002","volume":"812","author":"P Gawrychowski","year":"2020","unstructured":"Gawrychowski, P., Jo, S., Mozes, S., Weimann, O.: Compressed range minimum queries. Theor. Comput. Sci. 812, 39\u201348 (2020). https:\/\/doi.org\/10.1016\/J.TCS.2019.07.002","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"17_CR21","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0097-3165(93)90095-P","volume":"64","author":"IM Gessel","year":"1993","unstructured":"Gessel, I.M., Reutenauer, C.: Counting permutations with given cycle structure and descent set. J. Comb. Theory A 64(2), 189\u2013215 (1993)","journal-title":"J. Comb. Theory A"},{"key":"17_CR22","doi-asserted-by":"publisher","unstructured":"Jo, S., Rao Satti, S.: Encoding data structures for range queries on arrays. In: From Strings to Graphs, and Back Again, volume 132 of OASIcs, pp. 12:1\u201312:12. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2025). https:\/\/doi.org\/10.4230\/OASICS.GROSSI.12","DOI":"10.4230\/OASICS.GROSSI.12"},{"issue":"14","key":"17_CR23","doi-asserted-by":"publisher","first-page":"1838","DOI":"10.1093\/BIOINFORMATICS\/BTS280","volume":"28","author":"H Li","year":"2012","unstructured":"Li, H.: Exploring single-sample SNP and indel calling with whole-genome de novo assembly. Bioinformatics 28(14), 1838\u20131844 (2012). https:\/\/doi.org\/10.1093\/BIOINFORMATICS\/BTS280","journal-title":"Bioinformatics"},{"issue":"1","key":"17_CR24","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1186\/S13015-020-00177-Y","volume":"15","author":"FA Louza","year":"2020","unstructured":"Louza, F.A., Telles, G.P., Gog, S., Prezza, N., Rosone, G.: GSUFSORT: constructing suffix arrays, LCP arrays and BWTs for string collections. Algorithms Mol. Biol. 15(1), 18 (2020). https:\/\/doi.org\/10.1186\/S13015-020-00177-Y","journal-title":"Algorithms Mol. Biol."},{"issue":"3","key":"17_CR25","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). https:\/\/doi.org\/10.1016\/J.TCS.2007.07.014","journal-title":"Theor. Comput. Sci."},{"key":"17_CR26","doi-asserted-by":"crossref","unstructured":"Mignosi, F., Restivo, A., Sciortino, M.: Forbidden factors in finite and infinite words. In: Karhum\u00e4ki, J., Maurer, H.A., P\u0103un, G., Rozenberg, G., (eds.), Jewels Are Forever: Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pp. 339\u2013350. Springer (1999)","DOI":"10.1007\/978-3-642-60207-8_30"},{"issue":"6","key":"17_CR27","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1051\/ITA:2001132","volume":"35","author":"F Mignosi","year":"2001","unstructured":"Mignosi, F., Restivo, A., Sciortino, M.: Forbidden factors and fragment assembly. RAIRO Theor. Inf. Appl. 35(6), 565\u2013577 (2001). https:\/\/doi.org\/10.1051\/ITA:2001132","journal-title":"RAIRO Theor. Inf. Appl."},{"key":"17_CR28","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Compact Data Structures - A Practical Approach, Cambridge University Press (2016)","DOI":"10.1017\/CBO9781316588284"},{"key":"17_CR29","doi-asserted-by":"publisher","unstructured":"Nishimoto, T., Tabei, Y.: Optimal-time queries on bwt-runs compressed indexes. In ICALP, volume 198 of LIPIcs, pp. 101:1\u2013101:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021). https:\/\/doi.org\/10.4230\/LIPICS.ICALP.2021.101","DOI":"10.4230\/LIPICS.ICALP.2021.101"},{"key":"17_CR30","unstructured":"Ohlebusch, E.: Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction, Oldenbusch Verlag (2013)"},{"key":"17_CR31","unstructured":"Perrin, D., Restivo, A.: Words. In: B\u00f3na, M. (ed.) Handbook of Enumerative Combinatorics. CRC Press, Boca Raton, FL (2015)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-28404-4_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,5]],"date-time":"2026-06-05T23:19:10Z","timestamp":1780701550000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-28404-4_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032284037","9783032284044"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-28404-4_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"6 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Rouen","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 July 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/dlt-ncma-2026.sciencesconf.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}