{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T11:10:04Z","timestamp":1751368204753,"version":"3.41.0"},"reference-count":0,"publisher":"SAGE Publications","issue":"3-4","license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Fundamenta Informaticae"],"published-print":{"date-parts":[[2014,6]]},"abstract":"<jats:p>\n            We derive quantitative results regarding sets of n-bit strings that have different dependency or independency properties. Let C(x) be the Kolmogorov complexity of the string x. A string y has \u03b1 dependency with a string x if C(y) \u2212 C(y | x) \u2265 \u03b1. A set of strings {x\n            <jats:sub>1<\/jats:sub>\n            , . . . , x\n            <jats:sub>t<\/jats:sub>\n            } is pairwise \u03b1-independent if for all i \u2260 j, C(x\n            <jats:sub>i<\/jats:sub>\n            ) \u2212 C(x\n            <jats:sub>i<\/jats:sub>\n            | x\n            <jats:sub>j<\/jats:sub>\n            ) &lt; \u03b1. A tuple of strings (x\n            <jats:sub>1<\/jats:sub>\n            , . . . , x\n            <jats:sub>t<\/jats:sub>\n            ) is mutually \u03b1-independent if C(x\n            <jats:sub>\u03c0(1)<\/jats:sub>\n            . . . x\n            <jats:sub>\u03c0(t)<\/jats:sub>\n            ) &gt; C(x\n            <jats:sub>1<\/jats:sub>\n            )+. . .+C(x\n            <jats:sub>t<\/jats:sub>\n            ) \u2212 \u03b1, for every permutation \u03c0 of [t]. We show that: \u2022 For every n-bit string x with complexity C(x) \u2265 \u03b1 + 7 log n, the set of n-bit strings that have \u03b1 dependency with x has size at least (1\/poly(n))2\n            <jats:sup>n\u2212\u03b1<\/jats:sup>\n            . In case \u03b1 is computable from n and C(x) \u2265 \u03b1 + 12 log n, the size of the same set is at least (1\/C)2\n            <jats:sup>n\u2212\u03b1<\/jats:sup>\n            \u2212 poly(n)2\n            <jats:sup>\u03b1<\/jats:sup>\n            , for some positive constant C. \u2022 There exists a set of n-bit strings A of size poly(n)2\n            <jats:sup>\u03b1<\/jats:sup>\n            such that any n-bit string has \u03b1-dependency with some string in A. \u2022 If the set of n-bit strings {x\n            <jats:sub>1<\/jats:sub>\n            , . . . , x\n            <jats:sub>t<\/jats:sub>\n            } is pairwise \u03b1-independent, then t \u2264 poly(n)2\n            <jats:sup>\u03b1<\/jats:sup>\n            . This bound is tight within a poly(n) factor, because, for every n, there exists a set of n-bit strings {x\n            <jats:sub>1<\/jats:sub>\n            , . . . , x\n            <jats:sub>t<\/jats:sub>\n            } that is pairwise \u03b1-dependent with t = (1\/poly(n)) \u00b7 2\n            <jats:sup>\u03b1<\/jats:sup>\n            (for all \u03b1 \u2265 5 log n). \u2022 If the tuple of n-bit strings (x\n            <jats:sub>1<\/jats:sub>\n            , . . . , x\n            <jats:sub>t<\/jats:sub>\n            ) is mutually \u03b1-independent, then t \u2264 poly(n)2\n            <jats:sup>\u03b1<\/jats:sup>\n            (for all \u03b1 \u2265 7 log n + 6).\n          <\/jats:p>","DOI":"10.3233\/fi-2014-1027","type":"journal-article","created":{"date-parts":[[2019,12,3]],"date-time":"2019-12-03T05:55:47Z","timestamp":1575352547000},"page":"485-497","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":0,"title":["Counting Dependent and Independent Strings"],"prefix":"10.1177","volume":"131","author":[{"given":"Marius","family":"Zimand","sequence":"first","affiliation":[{"name":"Department of Computer and Information Sciences, Towson University, Baltimore, MD, USA. mzimand@towson.edu"}]}],"member":"179","published-online":{"date-parts":[[2014,1]]},"container-title":["Fundamenta Informaticae"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2014-1027","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/FI-2014-1027","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T10:50:00Z","timestamp":1751367000000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.3233\/FI-2014-1027"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":0,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["10.3233\/FI-2014-1027"],"URL":"https:\/\/doi.org\/10.3233\/fi-2014-1027","relation":{},"ISSN":["0169-2968","1875-8681"],"issn-type":[{"type":"print","value":"0169-2968"},{"type":"electronic","value":"1875-8681"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}