کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4655635 | 1343394 | 2012 | 6 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: The existence of k-radius sequences The existence of k-radius sequences](/preview/png/4655635.png)
Let n and k be positive integers, and let F be an alphabet of size n. A sequence over F of length m is a k-radius sequence if any two distinct elements of F occur within distance k of each other somewhere in the sequence. These sequences were introduced by Jaromczyk and Lonc in 2004, in order to produce an efficient caching strategy when computing certain functions on large data sets such as medical images.Let fk(n)fk(n) be the length of the shortest n-ary k-radius sequence. The paper shows, using a probabilistic argument, that whenever k is fixed and n→∞n→∞fk(n)∼1k(n2). The paper observes that the same argument generalises to the situation when we require the following stronger property for some integer t such that 2⩽t⩽k+12⩽t⩽k+1: any t distinct elements of F must simultaneously occur within a distance k of each other somewhere in the sequence.
Journal: Journal of Combinatorial Theory, Series A - Volume 119, Issue 1, January 2012, Pages 212–217