Abstract:
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. © 2012 Elsevier B.V. All rights reserved.
Referencias:
- Adjeroh, D., Bell, T., Mukherjee, A., (2008) The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching, , Springer
- Asarin, E., Degorre, A., Volume and entropy of regular timed languages: Analytic approach (2009) FORMATS'09, 5813, pp. 13-27. , LNCS Springer-Verlag
- Asarin, E., Degorre, A., Volume and entropy of regular timed languages: Discretization approach (2009) CONCUR'09, 5710, pp. 69-83. , LNCS Springer-Verlag
- Becher, V., Heiber, P.A., On extending de Bruijn sequences (2011) Information Processing Letters, 111, pp. 930-932
- Bruijn, N.G., A combinatorial problem (1946) Koninklijke Nederlandse Akademie V. Wetenschappen, 49, pp. 758-764
- Buhrman, H., Fortnow, L., Resource-bounded kolmogorov complexity revisited (1997) Lecture Notes In Computer Science, (1200), pp. 105-116. , STACS 97
- Calude, C., Salomaa, K., Roblot, T., Finite-state complexity and the size of transducers (2010) Proceedings of Descriptional Complexity of Formal Systems (DCFS), pp. 38-47
- Chaitin, G.J., A theory of program size formally identical to information theory (1975) Journal of the ACM, 22, pp. 329-340
- Cilibrasi, R., Vitanyi, P.M.B., Clustering by compression (2005) IEEE Transactions on Information Theory, 51 (4), pp. 1523-1545. , DOI 10.1109/TIT.2005.844059
- Ehrenfeucht, A., Mycielski, J., A pseudorandom sequence: How random is it? in Richard K. Guy, Unsolved problems (1992) American Mathematical Monthly, pp. 373-375
- Kasai, T., Lee, G., Arimura, H., Arikawa, S., Park, K., Linear-time longest-common-prefix computation in suffix arrays and its applications (2001) Lecture Notes In Computer Science, (2089), pp. 181-192. , Combinatorial Pattern Matching
- Kolmogorov, A.N., Three approaches to the quantitative definition of information (1965) Problems of Information Transmission, 1 (1), pp. 1-7
- Lempel, A., Ziv, J., On the complexity of finite sequences (1976) IEEE Transactions on Information Theory, 22 (1), pp. 75-81
- María López-Valdés, Lempel-Ziv dimension for Lempel-Ziv compression (2006) MFCS, pp. 693-703
- Manber, U., Myers, G., Suffix arrays: A new method for on-line string searches (1993) SIAM Journal on Computing, 22 (5), pp. 935-948
- Schnorr, C.P., Process complexity and effective random tests (1973) Journal of Computer Systems Science, 7, pp. 376-388
- Shallit, J., Wang, M.-W., Automatic complexity of strings (2001) Journal of Automata, Languages and Combinatorics, 6 (4), pp. 537-554
- Shannon, C.E., A mathematical theory of communication (1948) Bell System Technical Journal, 27, pp. 379-423. , 623-656
- Uspensky, V.A., Shen, A.Kh., Relations between varieties of Kolmogorov complexities (1996) Mathematics Systems Theory, 29, pp. 271-292
- Vitányi, P., Li, M., (1997) An Introduction to Kolmogorov Complexity and Its Applications, , 2nd edition Springer
- Ziv Jacob, Lempel Abraham, Compression of individual sequences via variable-rate coding (1978) IEEE Transactions on Information Theory, IT-24 (5), pp. 530-536
- Zvonkin, A.K., Levin, L.A., The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms (1970) Russian Mathematical Surveys, 25, pp. 83-124
Citas:
---------- APA ----------
Becher, V. & Heiber, P.A.
(2012)
. A linearly computable measure of string complexity. Theoretical Computer Science, 438, 62-73.
http://dx.doi.org/10.1016/j.tcs.2012.03.007---------- CHICAGO ----------
Becher, V., Heiber, P.A.
"A linearly computable measure of string complexity"
. Theoretical Computer Science 438
(2012) : 62-73.
http://dx.doi.org/10.1016/j.tcs.2012.03.007---------- MLA ----------
Becher, V., Heiber, P.A.
"A linearly computable measure of string complexity"
. Theoretical Computer Science, vol. 438, 2012, pp. 62-73.
http://dx.doi.org/10.1016/j.tcs.2012.03.007---------- VANCOUVER ----------
Becher, V., Heiber, P.A. A linearly computable measure of string complexity. Theor Comput Sci. 2012;438:62-73.
http://dx.doi.org/10.1016/j.tcs.2012.03.007