A linearly computable measure of string complexity | ||
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.contributor.author | Becher, Veronica Andrea | |
| dc.contributor.author | Heiber, Pablo Ariel | |
| dc.date.issued | 2012-01 | |
| dc.description.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. | es |
| dc.description.fil | Fil: Becher, Veronica Andrea. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.description.fil | Fil: Heiber, Pablo Ariel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina | |
| dc.format | application/pdf | es |
| dc.identifier.citation | Becher, Veronica Andrea; Heiber, Pablo Ariel; A linearly computable measure of string complexity; Elsevier Science; Theoretical Computer Science; 438; 1-2012; 62-73 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0304-3975 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/190842 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.pagination | 62-73 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Theoretical Computer Science | es |
| dc.journal.volume | 438 | es |
| dc.language.iso | eng | es |
| dc.publisher | Elsevier Science | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.tcs.2012.03.007 | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0304397512002277 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-sa/2.5/ar/ | * |
| dc.subject | KOLMOGOROV COMPLEXITY | es |
| dc.subject | STRINGOLOGY | es |
| dc.subject | DE BRUIJN STRINGS | es |
| dc.subject | COMBINATORIAL PROPERTIES OF STRINGS | es |
| dc.subject.classification | Ciencias de la Computación | es |
| dc.subject.classification | Ciencias de la Computación e Información | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | A linearly computable measure of string complexity | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.a48e02fd-baaa-4ff9-8b10-5f5c4821f12b_B.pdf
- Tamaño:
- 638.23 KB
- Formato:
- Adobe Portable Document Format