Navegar

Colección

Datos Estadísticas

Artículo

Este artículo es de Acceso Abierto y puede ser descargado en su versión final desde nuestro repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

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.

Registro:

Documento: Artículo
Título:A linearly computable measure of string complexity
Autor:Becher, V.; Heiber, P.A.
Filiación:Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
Palabras clave:Basic properties; Computable measures; De Bruijn; Description complexity; Linear time; String complexity; Sub-strings; Computer science
Año:2012
Volumen:438
Página de inicio:62
Página de fin:73
DOI: http://dx.doi.org/10.1016/j.tcs.2012.03.007
Título revista:Theoretical Computer Science
Título revista abreviado:Theor Comput Sci
ISSN:03043975
CODEN:TCSCD
PDF:https://bibliotecadigital.exactas.uba.ar/download/paper/paper_03043975_v438_n_p62_Becher.pdf
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v438_n_p62_Becher

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