{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:30Z","timestamp":1760202750604,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662557501"},{"type":"electronic","value":"9783662557518"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-662-55751-8_14","type":"book-chapter","created":{"date-parts":[[2017,8,15]],"date-time":"2017-08-15T15:32:49Z","timestamp":1502811169000},"page":"164-176","source":"Crossref","is-referenced-by-count":6,"title":["Minimal Absent Words in a Sliding Window and Applications to On-Line Pattern Matching"],"prefix":"10.1007","author":[{"given":"Maxime","family":"Crochemore","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alice","family":"H\u00e9liou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory","family":"Kucherov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laurent","family":"Mouchard","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yann","family":"Ramusat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,16]]},"reference":[{"key":"14_CR1","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18, 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Almirantis, Y., Charalampopoulos, P., Gao, J., Iliopoulos, C.S., Mohamed, M., Pissis, S.P., Polychronopoulos, D.: On avoided words, absent words, and their application to biological sequence analysis. Algorithms Mol. Biol. 12(1), 5:1\u20135:12 (2017)","DOI":"10.1186\/s13015-017-0094-z"},{"key":"14_CR3","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1186\/s12859-014-0388-9","volume":"15","author":"C Barton","year":"2014","unstructured":"Barton, C., Heliou, A., Mouchard, L., Pissis, S.P.: Linear-time computation of minimal absent words using suffix array. BMC Bioinform. 15, 11 (2014)","journal-title":"BMC Bioinform."},{"key":"14_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/978-3-319-32152-3_23","volume-title":"Parallel Processing and Applied Mathematics","author":"C Barton","year":"2016","unstructured":"Barton, C., Heliou, A., Mouchard, L., Pissis, S.P.: Parallelising the computation of minimal absent words. In: Wyrzykowski, R., Deelman, E., Dongarra, J., Karczewski, K., Kitowski, J., Wiatr, K. (eds.) PPAM 2015. LNCS, vol. 9574, pp. 243\u2013253. Springer, Cham (2016). doi: 10.1007\/978-3-319-32152-3_23"},{"key":"14_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/3-540-60922-9_45","volume-title":"STACS 96","author":"M-P B\u00e9al","year":"1996","unstructured":"B\u00e9al, M.-P., Mignosi, F., Restivo, A.: Minimal forbidden words and symbolic dynamics. In: Puech, C., Reischuk, R. (eds.) STACS 1996. LNCS, vol. 1046, pp. 555\u2013566. Springer, Heidelberg (1996). doi: 10.1007\/3-540-60922-9_45"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-642-40450-4_12","volume-title":"Algorithms \u2013 ESA 2013","author":"D Belazzougui","year":"2013","unstructured":"Belazzougui, D., Cunial, F., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V.: Versatile succinct representations of the bidirectional Burrows-wheeler transform. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 133\u2013144. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40450-4_12"},{"key":"14_CR7","doi-asserted-by":"crossref","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. Theoret. Comput. Sci. 450, 109\u2013116 (2012)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR8","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1007\/978-3-662-49529-2_25","volume-title":"LATIN 2016","author":"M Crochemore","year":"2016","unstructured":"Crochemore, M., Fici, G., Mercas, R., Pissis, S.P.: Linear-time sequence comparison using minimal absent words. In: Kranakis, E., Navarro, G., Ch\u00e1vez, E. (eds.) LATIN 2016. LNCS, vol. 9644, pp. 334\u2013346. Springer, Heidelberg (2016). doi: 10.1007\/978-3-662-49529-2_25"},{"key":"14_CR9","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press, Cambridge (2007)","DOI":"10.1017\/CBO9780511546853"},{"issue":"3","key":"14_CR10","doi-asserted-by":"crossref","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)","journal-title":"Inf. Process. Lett."},{"issue":"11","key":"14_CR11","doi-asserted-by":"crossref","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 antidictonaries. Proc. IEEE 88(11), 1756\u20131768 (2000)","journal-title":"Proc. IEEE"},{"key":"14_CR12","first-page":"29","volume":"3","author":"B D\u00f6m\u00f6lki","year":"1964","unstructured":"D\u00f6m\u00f6lki, B.: An algorithm for syntactical analysis. Comput. Linguist. 3, 29\u201346 (1964)","journal-title":"Comput. Linguist."},{"key":"14_CR13","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: FOCS, pp. 390\u2013398. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"14_CR14","unstructured":"Fici, G.: Minimal Forbidden Words and Applications. Th\u00e8se, Universit\u00e9 de Marne la Vall\u00e9e (2006)"},{"key":"14_CR15","unstructured":"Fujishige, Y., Tsujimaru, Y., Inenaga, S., Bannai, H., Takeda, M.: Computing DAWGs and minimal absent words in linear time for integer alphabets. In: MFCS. LIPIcs, vol. 58, pp. 38:1\u201338:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"key":"14_CR16","doi-asserted-by":"crossref","unstructured":"Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)","DOI":"10.1017\/CBO9780511574931"},{"key":"14_CR17","doi-asserted-by":"crossref","unstructured":"Hampikian, G., Andersen, T.L.: Absent sequences: nullomers and primes. In: PSB, pp. 355\u2013366. World Scientific (2007)","DOI":"10.1142\/9789812772435_0034"},{"key":"14_CR18","doi-asserted-by":"crossref","unstructured":"Heliou, A., Pissis, S.P., Puglisi, S.J.: emMAW: computing minimal absent words in external memory. Bioinformatics (2017)","DOI":"10.1093\/bioinformatics\/btx209"},{"key":"14_CR19","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1186\/1471-2105-9-167","volume":"9","author":"J Herold","year":"2008","unstructured":"Herold, J., Kurtz, S., Giegerich, R.: Efficient computation of absent words in genomic sequences. BMC Bioinform. 9, 167 (2008)","journal-title":"BMC Bioinform."},{"issue":"2","key":"14_CR20","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"14_CR21","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/j.tcs.2015.10.043","volume":"638","author":"G Kucherov","year":"2016","unstructured":"Kucherov, G., Salikhov, K., Tsur, D.: Approximate string matching using a bidirectional index. Theoret. Comput. Sci. 638, 145\u2013158 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"14_CR22","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1137\/S0097539794264810","volume":"27\u20132","author":"GM Landau","year":"1998","unstructured":"Landau, G.M., Myers, E.W., Schmidt, J.P.: Incremental string comparison. SIAM J. Comput. 27\u20132, 557\u2013582 (1998)","journal-title":"SIAM J. Comput."},{"issue":"1\u20132","key":"14_CR23","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0304-3975(00)00436-9","volume":"273","author":"F Mignosi","year":"2002","unstructured":"Mignosi, F., Restivo, A., Sciortino, M.: Words and forbidden factors. Theoret. Comput. Sci. 273(1\u20132), 99\u2013117 (2002)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"14_CR24","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1145\/316542.316550","volume":"46","author":"G Myers","year":"1999","unstructured":"Myers, G.: A fast bit-vector algorithm for approximate string matching based on dynamic programming. J. ACM 46(3), 395\u2013415 (1999)","journal-title":"J. ACM"},{"issue":"1","key":"14_CR25","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Comput. Surv. 33(1), 31\u201388 (2001)","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"14_CR26","first-page":"19","volume":"24","author":"G Navarro","year":"2001","unstructured":"Navarro, G., Baeza-Yates, R.A., Sutinen, E., Tarhio, J.: Indexing methods for approximate string matching. IEEE Data Eng. Bull. 24(4), 19\u201327 (2001)","journal-title":"IEEE Data Eng. Bull."},{"key":"14_CR27","unstructured":"Navarro, G., Raffinot, M.: Flexible Pattern Matching in Strings: Practical On-line Search Algorithms for Texts and Biological Sequences. Cambridge University Press, Cambridge (2008)"},{"key":"14_CR28","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/j.tcs.2014.01.021","volume":"526","author":"T Ota","year":"2014","unstructured":"Ota, T., Fukae, H., Morita, H.: Dynamic construction of an antidictionary with linear complexity. Theor. Comput. Sci. 526, 108\u2013119 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"14_CR29","unstructured":"Ota, T., Morita, H.: On a universal antidictionary coding for stationary ergodic sources with finite alphabet. In: ISITA, pp. 294\u2013298. IEEE (2014)"},{"issue":"1","key":"14_CR30","first-page":"1","volume":"9","author":"MS Rahman","year":"2016","unstructured":"Rahman, M.S., Alatabbi, A., Athar, T., Crochemore, M., Rahman, M.S.: Absent words and the (dis)similarity analysis of DNA sequences: an experimental study. BMC Bioinform. Notes 9(1), 1\u20138 (2016)","journal-title":"BMC Bioinform. Notes"},{"key":"14_CR31","unstructured":"Senft, M.: Suffix tree for a sliding window: an overview. In: WDS, pp. 41\u201346. Matfyzpress (2005)"},{"issue":"15","key":"14_CR32","doi-asserted-by":"crossref","first-page":"2421","DOI":"10.1093\/bioinformatics\/btv189","volume":"31","author":"RM Silva","year":"2015","unstructured":"Silva, R.M., Pratas, D., Castro, L., Pinho, A.J., Ferreira, P.J.S.G.: Three minimal sequences found in Ebola virus genomes and absent from human DNA. Bioinformatics 31(15), 2421\u20132425 (2015)","journal-title":"Bioinformatics"},{"issue":"3","key":"14_CR33","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249\u2013260 (1995)","journal-title":"Algorithmica"},{"issue":"14\u201315","key":"14_CR34","doi-asserted-by":"crossref","first-page":"596","DOI":"10.1016\/j.ipl.2010.05.008","volume":"110","author":"Z Wu","year":"2010","unstructured":"Wu, Z., Jiang, T., Su, W.: Efficient computation of shortest absent words in a genomic sequence. Inf. Process. Lett. 110(14\u201315), 596\u2013601 (2010)","journal-title":"Inf. Process. Lett."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-55751-8_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T22:55:48Z","timestamp":1750805748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-55751-8_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783662557501","9783662557518"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-55751-8_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}