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...

Descripción completa

Detalles Bibliográficos
Autores principales: Becher, Verónica Andrea, Heiber, Pablo Ariel
Publicado: 2012
Materias:
Basic properties
Computable measures
De Bruijn
Description complexity
Linear time
String complexity
Sub-strings
Computer science
Acceso en línea:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v438_n_p62_Becher
http://hdl.handle.net/20.500.12110/paper_03043975_v438_n_p62_Becher
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id paper:paper_03043975_v438_n_p62_Becher
record_format dspace
spelling paper:paper_03043975_v438_n_p62_Becher2023-06-08T15:29:38Z A linearly computable measure of string complexity Becher, Verónica Andrea Heiber, Pablo Ariel Basic properties Computable measures De Bruijn Description complexity Linear time String complexity Sub-strings Computer science 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. 2012 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v438_n_p62_Becher http://hdl.handle.net/20.500.12110/paper_03043975_v438_n_p62_Becher
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (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, Verónica Andrea
Heiber, Pablo Ariel
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.
author Becher, Verónica Andrea
Heiber, Pablo Ariel
author_facet Becher, Verónica Andrea
Heiber, Pablo Ariel
author_sort Becher, Verónica Andrea
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 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03043975_v438_n_p62_Becher
http://hdl.handle.net/20.500.12110/paper_03043975_v438_n_p62_Becher
work_keys_str_mv AT becherveronicaandrea alinearlycomputablemeasureofstringcomplexity
AT heiberpabloariel alinearlycomputablemeasureofstringcomplexity
AT becherveronicaandrea linearlycomputablemeasureofstringcomplexity
AT heiberpabloariel linearlycomputablemeasureofstringcomplexity
_version_ 1768544819757449216

Ejemplares similares