id: 06064143
dt: j
an: 06064143
au: Becher, Verónica; Heiber, Pablo Ariel
ti: A linearly computable measure of string complexity.
so: Theor. Comput. Sci. 438, 62-73 (2012).
py: 2012
pu: Elsevier Science Publishers, Amsterdam
la: EN
cc: 
ut: 
ci: 
li: doi:10.1016/j.tcs.2012.03.007
ab: Summary: We present a measure of string complexity, called I-complexity,
    computable in linear time and space. It counts the number of different
    substrings in a given string. The least complex strings are the runs of
    a single symbol, the most complex are the de Bruijn strings. Although
    the I-complexity of a string is not the length of any minimal
    description of the string, it satisfies many basic properties of
    classical description complexity. In particular, the number of strings
    with I-complexity up to a given value is bounded, and most strings of
    each length have high I-complexity.
rv: