\input zb-basic
\input zb-ioport
\iteman{io-port 06064143}
\itemau{Becher, Ver\'onica; Heiber, Pablo Ariel}
\itemti{A linearly computable measure of string complexity.}
\itemso{Theor. Comput. Sci. 438, 62-73 (2012).}
\itemab
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.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1016/j.tcs.2012.03.007}
\end