{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T02:40:00Z","timestamp":1648521600061},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1996,3]]},"abstract":"<jats:p> A nonempty circular string C(x) of length n is said to be covered by a set U<jats:sub>k<\/jats:sub> of strings each of fixed length k\u2264n iff every position in C(x) lies within an occurrence of some string u\u2208U<jats:sub>k<\/jats:sub>. In this paper we consider the problem of determining the minimum cardinality of a set U<jats:sub>k<\/jats:sub> which guarantees that every circular string C(x) of length n\u2265k can be covered. In particular, we show how, for any positive integer m, to choose the elements of U<jats:sub>k<\/jats:sub> so that, for sufficiently large k, u<jats:sub>k<\/jats:sub>\u2248\u03c3<jats:sup>k\u2013m<\/jats:sup>, where u<jats:sub>k<\/jats:sub>=|U<jats:sub>k<\/jats:sub>| and \u03c3 is the size of the alphabet on which the strings are defined. The problem has application to DNA sequencing by hybridization using oligonucleotide probes. <\/jats:p>","DOI":"10.1142\/s0129054196000075","type":"journal-article","created":{"date-parts":[[2004,9,6]],"date-time":"2004-09-06T11:50:09Z","timestamp":1094471409000},"page":"87-93","source":"Crossref","is-referenced-by-count":2,"title":["COVERING A CIRCULAR STRING WITH SUBSTRINGS OF FIXED LENGTH"],"prefix":"10.1142","volume":"07","author":[{"given":"ART M.","family":"DUVAL","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, University of Texas at El Paso El Paso, Texas 79968\u20130514, U.S.A."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"W.F.","family":"SMYTH","sequence":"additional","affiliation":[{"name":"Department of Computer Science &amp; Systems, McMaster University, Hamilton, Ontario L8S 4K1, Canada"},{"name":"School of Computing, Curtin University GPO Box U-1987, Perth WA 6001, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054196000075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:43:11Z","timestamp":1565138591000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054196000075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,3]]},"references-count":0,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1996,3]]}},"alternative-id":["10.1142\/S0129054196000075"],"URL":"https:\/\/doi.org\/10.1142\/s0129054196000075","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,3]]}}}