{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:05Z","timestamp":1759638065251,"version":"3.40.3"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030326852"},{"type":"electronic","value":"9783030326869"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-32686-9_11","type":"book-chapter","created":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T22:02:27Z","timestamp":1570226547000},"page":"152-161","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Minimal Absent Words in Rooted and Unrooted Trees"],"prefix":"10.1007","author":[{"given":"Gabriele","family":"Fici","sequence":"first","affiliation":[]},{"given":"Pawe\u0142","family":"Gawrychowski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,3]]},"reference":[{"issue":"1","key":"11_CR1","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1186\/s13015-017-0094-z","volume":"12","author":"Y Almirantis","year":"2017","unstructured":"Almirantis, Y., et al.: On avoided words, absent words, and their application to biological sequence analysis. Algorithms Mol. Biol. 12(1), 51\u2013512 (2017)","journal-title":"Algorithms Mol. Biol."},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1186\/s12859-014-0388-9","volume":"15","author":"C Barton","year":"2014","unstructured":"Barton, C., H\u00e9liou, A., Mouchard, L., Pissis, S.P.: Linear-time computation of minimal absent words using suffix array. BMC Bioinform. 15, 388 (2014)","journal-title":"BMC Bioinform."},{"issue":"1\u20132","key":"11_CR3","first-page":"121","volume":"56","author":"M B\u00e9al","year":"2003","unstructured":"B\u00e9al, M., Crochemore, M., Mignosi, F., Restivo, A., Sciortino, M.: Computing forbidden words of regular languages. Fundam. Inform. 56(1\u20132), 121\u2013135 (2003)","journal-title":"Fundam. Inform."},{"issue":"1","key":"11_CR4","first-page":"73","volume":"15","author":"M B\u00e9al","year":"2005","unstructured":"B\u00e9al, M., Fiorenzi, F., Mignosi, F.: Minimal forbidden patterns of multi-dimensional shifts. IJAC 15(1), 73\u201393 (2005)","journal-title":"IJAC"},{"key":"11_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). https:\/\/doi.org\/10.1007\/3-540-60922-9_45"},{"issue":"3","key":"11_CR6","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1007\/s00453-017-0286-4","volume":"79","author":"D Belazzougui","year":"2017","unstructured":"Belazzougui, D., Cunial, F.: A framework for space-efficient string kernels. Algorithmica 79(3), 857\u2013883 (2017)","journal-title":"Algorithmica"},{"key":"11_CR7","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). https:\/\/doi.org\/10.1007\/978-3-642-40450-4_12"},{"key":"11_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88\u201394. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10719839_9"},{"key":"11_CR9","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. Theoret. Comput. Sci. 450, 109\u2013116 (2012)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"11_CR10","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ic.2018.06.002","volume":"262","author":"P Charalampopoulos","year":"2018","unstructured":"Charalampopoulos, P., Crochemore, M., Fici, G., Merca\u015f, R., Pissis, S.P.: Alignment-free sequence comparison using absent words. Inf. Comput. 262(1), 57\u201368 (2018)","journal-title":"Inf. Comput."},{"key":"11_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-030-00479-8_11","volume-title":"String Processing and Information Retrieval","author":"P Charalampopoulos","year":"2018","unstructured":"Charalampopoulos, P., Crochemore, M., Pissis, S.P.: On extended special factors of a word. In: Gagie, T., Moffat, A., Navarro, G., Cuadros-Vargas, E. (eds.) SPIRE 2018. LNCS, vol. 11147, pp. 131\u2013138. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-030-00479-8_11"},{"key":"11_CR12","unstructured":"Crawford, T., Badkobeh, G., Lewis, D.: Searching page-images of early music scanned with OMR: a scalable solution using minimal absent words. In: ISMIR, pp. 233\u2013239 (2018)"},{"key":"11_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-662-55751-8_14","volume-title":"Fundamentals of Computation Theory","author":"M Crochemore","year":"2017","unstructured":"Crochemore, M., H\u00e9liou, A., Kucherov, G., Mouchard, L., Pissis, S.P., Ramusat, Y.: Minimal absent words in a sliding window and applications to on-line pattern matching. In: Klasing, R., Zeitoun, M. (eds.) FCT 2017. LNCS, vol. 10472, pp. 164\u2013176. Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-55751-8_14"},{"issue":"3","key":"11_CR14","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)","journal-title":"Inf. Process. Lett."},{"issue":"11","key":"11_CR15","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)","journal-title":"Proc. IEEE"},{"key":"11_CR16","unstructured":"Crochemore, M., Navarro, G.: Improved antidictionary based compression. In: 22nd International Conference of the Chilean Computer Science Society (SCCC 2002), 6\u20138 November 2002, Copiapo, Chile, pp. 7\u201313 (2002)"},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Fiala, M., Holub, J.: DCA using suffix arrays. In: 2008 Data Compression Conference (DCC 2008), 25\u201327 March 2008, Snowbird, UT, USA, p. 516. IEEE Computer Society (2008)","DOI":"10.1109\/DCC.2008.95"},{"key":"11_CR18","unstructured":"Fici, G.: Minimal Forbidden Words and Applications. Ph.D. thesis, Universit\u00e9 de Marne-la-Vall\u00e9e (2006)"},{"issue":"1","key":"11_CR19","doi-asserted-by":"publisher","first-page":"23","DOI":"10.3934\/medsci.2018.1.23","volume":"5","author":"G Fici","year":"2018","unstructured":"Fici, G., Langiu, A., Lo Bosco, G., Rizzo, R.: Bacteria classification using minimal absent words. AIMS Med. Sci. 5(1), 23\u201332 (2018)","journal-title":"AIMS Med. Sci."},{"issue":"1","key":"11_CR20","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1016\/j.tcs.2006.03.006","volume":"359","author":"G Fici","year":"2006","unstructured":"Fici, G., Mignosi, F., Restivo, A., Sciortino, M.: Word assembly through minimal forbidden words. Theoret. Comput. Sci. 359(1), 214\u2013230 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"11_CR21","unstructured":"Fici, G., Restivo, A., Rizzo, L.: Minimal forbidden factors of circular words. Theoret. Comput. Sci., to appear"},{"key":"11_CR22","unstructured":"Fujishige, Y., Tsujimaru, Y., Inenaga, S., Bannai, H., Takeda, M.: Computing DAWGs and minimal absent words in linear time for integer alphabets. In: Faliszewski, P., Muscholl, A., Niedermeier, R. (eds.) 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22\u201326, 2016 - Krak\u00f3w, Poland. LIPIcs, vol. 58, pp. 38:1\u201338:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"key":"11_CR23","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, STOC 1984, pp. 135\u2013143. ACM, New York (1984)","DOI":"10.1145\/800057.808675"},{"key":"11_CR24","doi-asserted-by":"crossref","unstructured":"Inenaga, S.: Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries. CoRR, abs\/1904.04513 (2019)","DOI":"10.1007\/978-3-030-61792-9_16"},{"key":"11_CR25","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-642-60207-8_30","volume-title":"Jewels are Forever","author":"F Mignosi","year":"1999","unstructured":"Mignosi, F., Restivo, A., Sciortino, M.: Forbidden factors in finite and infinite words. In: Karhum\u00e4ki, J., Maurer, H., P\u01ceun, G., Rozenberg, G. (eds.) Jewels are Forever, pp. 339\u2013350. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/978-3-642-60207-8_30"},{"issue":"6","key":"11_CR26","first-page":"565","volume":"35","author":"F Mignosi","year":"2001","unstructured":"Mignosi, F., Restivo, A., Sciortino, M.: Forbidden factors and fragment assembly. ITA 35(6), 565\u2013577 (2001)","journal-title":"ITA"},{"issue":"1\u20132","key":"11_CR27","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 273(1\u20132), 99\u2013117 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"Ota, T., Morita, H.: On the adaptive antidictionary code using minimal forbidden words with constant lengths. In: Proceedings of the International Symposium on Information Theory and its Applications, ISITA 2010, 17\u201320 October 2010, Taichung, Taiwan, pp. 72\u201377. IEEE (2010)","DOI":"10.1109\/ISITA.2010.5649621"},{"issue":"6","key":"11_CR29","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B Schieber","year":"1988","unstructured":"Schieber, B., Vishkin, U.: On finding lowest common ancestors: simplification and parallelization. SIAM J. Comput. 17(6), 1253\u20131262 (1988)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"11_CR30","first-page":"1061","volume":"E86\u2013A","author":"T Shibuya","year":"2003","unstructured":"Shibuya, T.: Constructing the suffix tree of a tree with a large alphabet. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E86\u2013A(5), 1061\u20131066 (2003)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"issue":"15","key":"11_CR31","doi-asserted-by":"publisher","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"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-32686-9_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,1]],"date-time":"2022-10-01T01:26:56Z","timestamp":1664587616000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-32686-9_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030326852","9783030326869"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-32686-9_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"3 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Segovia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 October 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 October 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/spire19.lbd.org.es\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"59","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}