A linearly computable measure of string complexity

Mostrar todas las versiones(3)

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, V., Heiber, P.A.
Formato:	JOUR
Materias:	Basic properties Computable measures De Bruijn Description complexity Linear time String complexity Sub-strings Computer science
Acceso en línea:	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	todo:paper_03043975_v438_n_p62_Becher
record_format	dspace
spelling	todo:paper_03043975_v438_n_p62_Becher2023-10-03T15:20:27Z A linearly computable measure of string complexity Becher, V. Heiber, P.A. 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. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, 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	JOUR
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
url	http://hdl.handle.net/20.500.12110/paper_03043975_v438_n_p62_Becher
work_keys_str_mv	AT becherv alinearlycomputablemeasureofstringcomplexity AT heiberpa alinearlycomputablemeasureofstringcomplexity AT becherv linearlycomputablemeasureofstringcomplexity AT heiberpa linearlycomputablemeasureofstringcomplexity
_version_	1807321287946665984

A linearly computable measure of string complexity

Ejemplares similares