{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T05:24:51Z","timestamp":1743053091140,"version":"3.40.3"},"publisher-location":"Cham","reference-count":36,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030592110"},{"type":"electronic","value":"9783030592127"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","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":[[2020]]},"DOI":"10.1007\/978-3-030-59212-7_8","type":"book-chapter","created":{"date-parts":[[2020,9,16]],"date-time":"2020-09-16T10:05:34Z","timestamp":1600250734000},"page":"99-114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximating the Anticover of a String"],"prefix":"10.1007","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Itai","family":"Boneh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eitan","family":"Kondratovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,17]]},"reference":[{"key":"8_CR1","unstructured":"Alamro, H., Badkobeh, G., Belazzougui, D., Iliopoulos, C.S., Puglisi, S.J.: Computing the antiperiod(s) of a string. In: Pisanti, N., Pissis, S.P. (eds.) Proceedings of 30th Combinatorial Pattern Matching, (CPM), LIPIcs, vol. 128, pp. 32:1\u201332:11. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"8_CR2","unstructured":"Alzamel, A., et al.: Finding the anticover of a string. In: Proceedings of 31st Combinatorial Pattern Matching (CPM), LIPIcs (2020, to appear)"},{"key":"8_CR3","unstructured":"Amir, A., Levy, A., Lewenstein, M., Lubin, R., Porat, B.: Can we recover the cover? In: Proceedings of 28st Annual Symposium on Combinatorial Pattern Matching (CPM), LIPICS (2017)"},{"key":"8_CR4","unstructured":"Antoniou, P., Crochemore, M., Iliopoulos, C.S., Jayasekera, I., Landau, G.M.: Conservative string covering of indeterminate strings. In: Proceedings of Prague Stringology Conference, pp. 108\u2013115 (2008)"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1007\/3-540-63246-8_14","volume-title":"Structures in Logic and Computer Science","author":"A Apostolico","year":"1997","unstructured":"Apostolico, A., Breslauer, D.: Of periods, quasiperiods, repetitions and covers. In: Mycielski, J., Rozenberg, G., Salomaa, A. (eds.) Structures in Logic and Computer Science. LNCS, vol. 1261, pp. 236\u2013248. Springer, Heidelberg (1997). \nhttps:\/\/doi.org\/10.1007\/3-540-63246-8_14"},{"issue":"2","key":"8_CR6","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0304-3975(93)90159-Q","volume":"119","author":"A Apostolico","year":"1993","unstructured":"Apostolico, A., Ehrenfeucht, A.: Efficient detection of quasiperiodicities in strings. Theoret. Comput. Sci. 119(2), 247\u2013265 (1993)","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1016\/0020-0190(91)90056-N","volume":"39","author":"A Apostolico","year":"1991","unstructured":"Apostolico, A., Iliopoulos, C., Farach, M.: Optimal superprimitivity testing for strings. Inf. Process. Lett. 39, 17\u201320 (1991)","journal-title":"Inf. Process. Lett."},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.ipl.2018.05.003","volume":"137","author":"G Badkobeh","year":"2018","unstructured":"Badkobeh, G., Fici, G., Puglisi, S.J.: Algorithms for anti-powers in strings. Inf. Process. Lett. 137, 57\u201360 (2018)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"8_CR9","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s00446-002-0085-1","volume":"15","author":"A Bar-Noy","year":"2002","unstructured":"Bar-Noy, A., Nisgav, A., Patt-Shamir, B.: Nearly optimal perfectly periodic schedules. Distrib. Comput. 15(4), 207\u2013220 (2002). \nhttps:\/\/doi.org\/10.1007\/s00446-002-0085-1","journal-title":"Distrib. Comput."},{"issue":"2","key":"8_CR10","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1093\/nar\/27.2.573","volume":"27","author":"G Benson","year":"1999","unstructured":"Benson, G.: Tandem repeats finder: a program to analyze DNA sequence. Nucleic Acids Res. 27(2), 573\u2013580 (1999)","journal-title":"Nucleic Acids Res."},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0020-0190(92)90111-8","volume":"44","author":"D Breslauer","year":"1992","unstructured":"Breslauer, D.: An on-line string superprimitivity test. Inf. Process. Lett. 44, 345\u2013347 (1992)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"8_CR12","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0020-0190(94)90060-4","volume":"49","author":"D Breslauer","year":"1994","unstructured":"Breslauer, D.: Testing string superprimitivity in parallel. Inf. Process. Lett. 49(5), 235\u2013241 (1994)","journal-title":"Inf. Process. Lett."},{"key":"8_CR13","first-page":"609","volume":"10","author":"M Christodoulakis","year":"2005","unstructured":"Christodoulakis, M., Iliopoulos, C.S., Park, K., Sim, J.S.: Approximate seeds of strings. J. Automata, Lang. Comb. 10, 609\u2013626 (2005)","journal-title":"J. Automata, Lang. Comb."},{"key":"8_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-642-13509-5_23","volume-title":"Combinatorial Pattern Matching","author":"M Crochemore","year":"2010","unstructured":"Crochemore, M., Iliopoulos, C.S., Pissis, S.P., Tischler, G.: Cover array string reconstruction. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 251\u2013259. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-13509-5_23"},{"key":"8_CR15","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.jcta.2018.02.009","volume":"157","author":"G Fici","year":"2018","unstructured":"Fici, G., Restivo, A., Silva, M., Zamboni, L.Q.: Anti-powers in infinite words. J. Comb. Theory Ser. A 157, 109\u2013119 (2018)","journal-title":"J. Comb. Theory Ser. A"},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.tcs.2013.08.013","volume":"506","author":"T Flouri","year":"2013","unstructured":"Flouri, T., et al.: Enhanced string covering. Theoret. Comput. Sci. 506, 102\u2013114 (2013)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"8_CR17","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1016\/j.bbrc.2003.09.014","volume":"310","author":"A Fuglsang","year":"2003","unstructured":"Fuglsang, A.: Distribution of potential type ii restriction sites (palindromes) in prokaryotes. Biochem. Biophys. Res. Commun. 310(2), 280\u2013285 (2003)","journal-title":"Biochem. Biophys. Res. Commun."},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"2430","DOI":"10.1093\/nar\/25.12.2430","volume":"25","author":"MS Gelfand","year":"1997","unstructured":"Gelfand, M.S., Koonin, E.V.: Avoidance of palindromic words in bacterial and archaeal genomes: a close connection with restriction enzymes. Nucleic Acids Res. 25, 2430\u20132439 (1997)","journal-title":"Nucleic Acids Res."},{"key":"8_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/978-3-642-22300-6_39","volume-title":"Algorithms and Data Structures","author":"B Gfeller","year":"2011","unstructured":"Gfeller, B.: Finding longest approximate periodic patterns. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 463\u2013474. Springer, Heidelberg (2011). \nhttps:\/\/doi.org\/10.1007\/978-3-642-22300-6_39"},{"key":"8_CR20","unstructured":"Han, J., Dong, G., Yin, Y.: Efficient mining of partial periodic patterns in time series database. In: Proceedings of 15th International Conference on Data Engineering (ICDE), pp. 106\u2013115 (1999)"},{"issue":"1","key":"8_CR21","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0304-3975(98)00260-6","volume":"218","author":"CS Iliopoulos","year":"1999","unstructured":"Iliopoulos, C.S., Mouchard, L.: Quasiperiodicity and string covering. Theoret. Comput. Sci. 218(1), 205\u2013216 (1999)","journal-title":"Theoret. Comput. Sci."},{"key":"8_CR22","unstructured":"Iliopoulos, C.S., Smyth, W.F.: An on-line algorithm of computing a minimum set of $$k$$-covers of a string. In: Proceedings of 9th Australian Workshop on Combinatorial Algorithms (AWOCA), pp. 97\u2013106 (1998)"},{"issue":"3","key":"8_CR23","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/BF01955677","volume":"16","author":"CS Iliopoulus","year":"1996","unstructured":"Iliopoulus, C.S., Moore, D.W.G., Park, K.: Covering a string. Algorithmica 16(3), 288\u2013297 (1996). \nhttps:\/\/doi.org\/10.1007\/BF01955677","journal-title":"Algorithmica"},{"key":"8_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-38905-4_18","volume-title":"Combinatorial Pattern Matching","author":"T Kociumaka","year":"2013","unstructured":"Kociumaka, T., Pissis, S.P., Radoszewski, J., Rytter, W., Wale\u0144, T.: Fast algorithm for partial covers in words. In: Fischer, J., Sanders, P. (eds.) CPM 2013. LNCS, vol. 7922, pp. 177\u2013188. Springer, Heidelberg (2013). \nhttps:\/\/doi.org\/10.1007\/978-3-642-38905-4_18"},{"issue":"1","key":"8_CR25","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s00453-001-0062-2","volume":"32","author":"Y Li","year":"2002","unstructured":"Li, Y., Smyth, W.F.: Computing the cover array in linear time. Algorithmica 32(1), 95\u2013106 (2002). \nhttps:\/\/doi.org\/10.1007\/s00453-001-0062-2","journal-title":"Algorithmica"},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00294-005-0573-5","volume":"47","author":"B Lisnic","year":"2005","unstructured":"Lisnic, B., Svetec, I.K., Saric, H., Nikolic, I., Zgaga, Z.: Palindrome content of the yeast Saccharomyces cerevisiae genome. Curr. Genet. 47, 289\u2013297 (2005). \nhttps:\/\/doi.org\/10.1007\/s00294-005-0573-5","journal-title":"Curr. Genet."},{"key":"8_CR27","volume-title":"Combinatorics on Words","year":"1997","unstructured":"Lothaire, M. (ed.): Combinatorics on Words, 2nd edn. Cambridge University Press, Cambridge (1997)","edition":"2"},{"key":"8_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-319-59575-7_13","volume-title":"Bioinformatics Research and Applications","author":"J Loving","year":"2017","unstructured":"Loving, J., Scaduto, J.P., Benson, G.: An SIMD algorithm for wraparound tandem alignment. In: Cai, Z., Daescu, O., Li, M. (eds.) ISBRA 2017. LNCS, vol. 10330, pp. 140\u2013149. Springer, Cham (2017). \nhttps:\/\/doi.org\/10.1007\/978-3-319-59575-7_13"},{"issue":"5","key":"8_CR29","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0020-0190(94)00045-X","volume":"50","author":"D Moore","year":"1994","unstructured":"Moore, D., Smyth, W.F.: An optimal algorithm to compute all the covers of a string. Inf. Process. Lett. 50(5), 239\u2013246 (1994)","journal-title":"Inf. Process. Lett."},{"key":"8_CR30","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1016\/0020-0190(94)00235-Q","volume":"54","author":"D Moore","year":"1995","unstructured":"Moore, D., Smyth, W.F.: A correction to: an optimal algorithm to compute all the covers of a string. Inf. Process. Lett. 54, 101\u2013103 (1995)","journal-title":"Inf. Process. Lett."},{"issue":"12","key":"8_CR31","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1093\/bioinformatics\/btq209","volume":"26","author":"M Pellegrini","year":"2010","unstructured":"Pellegrini, M., Renda, M.E., Vecchio, A.: TRStalker: an efficient heuristic for finding fuzzy tandem repeats. Bioinformatics [ISMB] 26(12), 358\u2013366 (2010)","journal-title":"Bioinformatics [ISMB]"},{"issue":"2","key":"8_CR32","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/S0304-3975(00)00067-0","volume":"249","author":"WF Smyth","year":"2000","unstructured":"Smyth, W.F.: Repetitive perhaps, but certainly not boring. Theoret. Comput. Sci. 249(2), 343\u2013355 (2000)","journal-title":"Theoret. Comput. Sci."},{"issue":"12","key":"8_CR33","doi-asserted-by":"publisher","first-page":"e52250","DOI":"10.1371\/journal.pone.0052250","volume":"7","author":"SK Srivastava","year":"2012","unstructured":"Srivastava, S.K., Robins, H.S.: Palindromic nucleotide analysis in human T cell receptor rearrangements. PLoS ONE 7(12), e52250 (2012)","journal-title":"PLoS ONE"},{"key":"8_CR34","doi-asserted-by":"crossref","unstructured":"Wexler, Y., Yakhini, Z., Kashi, Y., Geiger, D.: Finding approximate tandem repeats in genomic sequences. In: RECOMB, pp. 223\u2013232 (2004)","DOI":"10.1145\/974614.974644"},{"issue":"1","key":"8_CR35","first-page":"33","volume":"84","author":"H Zhang","year":"2008","unstructured":"Zhang, H., Guo, Q., Iliopoulos, C.S.: Algorithms for computing the lambda-regularities in strings. Fundamenta Informaticae 84(1), 33\u201349 (2008)","journal-title":"Fundamenta Informaticae"},{"key":"8_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/978-3-642-14355-7_28","volume-title":"Algorithmic Aspects in Information and Management","author":"H Zhang","year":"2010","unstructured":"Zhang, H., Guo, Q., Iliopoulos, C.S.: Varieties of regularities in weighted sequences. In: Chen, B. (ed.) AAIM 2010. LNCS, vol. 6124, pp. 271\u2013280. Springer, Heidelberg (2010). \nhttps:\/\/doi.org\/10.1007\/978-3-642-14355-7_28"}],"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-59212-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,16]],"date-time":"2020-09-16T10:08:08Z","timestamp":1600250888000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-59212-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030592110","9783030592127"],"references-count":36,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-59212-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"17 September 2020","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":"Orlando, FL","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 October 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 October 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"27","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.cs.ucf.edu\/spire2020\/","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":"32","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":"17","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":"4","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":"53% - 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":"4","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":"2","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)"}}]}}