{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T07:16:39Z","timestamp":1649142999868},"reference-count":1,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2010,6]]},"abstract":"<jats:p> A bit string is random (in the sense of algorithmic information theory) if it is incompressible, i.e., its Kolmogorov complexity is close to its length. Two random strings are independent if knowing one of them does not simplify the description of the other, i.e., the conditional complexity of each string (using the other as a condition) is close to its length. We may define independence of a k-tuple of strings in the same way. <\/jats:p><jats:p> In this paper we address the following question: what is that maximal cardinality of a set of n-bit strings if any k elements of this set are independent (up to a certain constant)? Lower and upper bounds that match each other (with logarithmic precision) are provided. <\/jats:p>","DOI":"10.1142\/s0129054110007271","type":"journal-article","created":{"date-parts":[[2010,6,7]],"date-time":"2010-06-07T10:40:55Z","timestamp":1275907255000},"page":"321-327","source":"Crossref","is-referenced-by-count":2,"title":["SETS OF K-INDEPENDENT STRINGS"],"prefix":"10.1142","volume":"21","author":[{"given":"YEN-WU","family":"TI","sequence":"first","affiliation":[{"name":"Dept. Computer Science Information and Engineering, Hwa Hsia Institute of Technology, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHING-LUEH","family":"CHANG","sequence":"additional","affiliation":[{"name":"Dept. Computer Science and Information Engineering, National Taiwan University, Taipei, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YUH-DAUH","family":"LYUU","sequence":"additional","affiliation":[{"name":"Dept. Computer Science and Information Engineering, National Taiwan University, No.1, Sec. 4, Roosevelt Road, Taipei, Taiwan 106, Taiwan"},{"name":"Dept. Finance, National Taiwan University, No.1, Sec. 4, Roosevelt Road, Taipei, Taiwan 106, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEXANDER","family":"SHEN","sequence":"additional","affiliation":[{"name":"Laboratoire Informatique Fondamentale, Marseille, France"},{"name":"CNRS &amp; Univ. Aix\u2013Marseille, On leave from IITP RAS, Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2606-0"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054110007271","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:22:47Z","timestamp":1565191367000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054110007271"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":1,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1142\/S0129054110007271"],"URL":"https:\/\/doi.org\/10.1142\/s0129054110007271","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6]]}}}