A linearly computable measure of string complexity
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 s...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Artículo publishedVersion |
| Publicado: |
2012
|
| Materias: | |
| Acceso en línea: | http://hdl.handle.net/20.500.12110/paper_03043975_v438_n_p62_Becher http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v438_n_p62_Becher_oai |
| Aporte de: |
| id |
I28-R145-paper_03043975_v438_n_p62_Becher_oai |
|---|---|
| record_format |
dspace |
| spelling |
I28-R145-paper_03043975_v438_n_p62_Becher_oai2020-10-19 Becher, V. Heiber, P.A. 2012 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. Fil:Becher, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Heiber, P.A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf http://hdl.handle.net/20.500.12110/paper_03043975_v438_n_p62_Becher info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar Theor Comput Sci 2012;438:62-73 Basic properties Computable measures De Bruijn Description complexity Linear time String complexity Sub-strings Computer science A linearly computable measure of string complexity info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v438_n_p62_Becher_oai |
| institution |
Universidad de Buenos Aires |
| institution_str |
I-28 |
| repository_str |
R-145 |
| collection |
Repositorio Digital de la Universidad de Buenos Aires (UBA) |
| topic |
Basic properties Computable measures De Bruijn Description complexity Linear time String complexity Sub-strings Computer science |
| spellingShingle |
Basic properties Computable measures De Bruijn Description complexity Linear time String complexity Sub-strings Computer science Becher, V. Heiber, P.A. A linearly computable measure of string complexity |
| topic_facet |
Basic properties Computable measures De Bruijn Description complexity Linear time String complexity Sub-strings Computer science |
| description |
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. |
| format |
Artículo Artículo publishedVersion |
| author |
Becher, V. Heiber, P.A. |
| author_facet |
Becher, V. Heiber, P.A. |
| author_sort |
Becher, V. |
| title |
A linearly computable measure of string complexity |
| title_short |
A linearly computable measure of string complexity |
| title_full |
A linearly computable measure of string complexity |
| title_fullStr |
A linearly computable measure of string complexity |
| title_full_unstemmed |
A linearly computable measure of string complexity |
| title_sort |
linearly computable measure of string complexity |
| publishDate |
2012 |
| url |
http://hdl.handle.net/20.500.12110/paper_03043975_v438_n_p62_Becher http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=artiaex&d=paper_03043975_v438_n_p62_Becher_oai |
| work_keys_str_mv |
AT becherv alinearlycomputablemeasureofstringcomplexity AT heiberpa alinearlycomputablemeasureofstringcomplexity AT becherv linearlycomputablemeasureofstringcomplexity AT heiberpa linearlycomputablemeasureofstringcomplexity |
| _version_ |
1766026690892398592 |