A linearly computable measure of string complexity (Q441859): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 5 users not shown) | |||
Property / review text | |||
In this very interesting paper, the authors introduce the notion of the \(I\)-complexity of a given string, which counts the number of distinct substrings in it, and investigate its properties. They prove that this measure of string complexity is computable in linear time and space from the well-known longest common prefix array (LCP array), the companion data structure of the suffix array. They also introduce the repetitions array, which is a permutation of the LCP array, and develop its properties. It is shown that the number of strings with \(I\)-complexity up to a given value is bounded and a large family of strings with almost maximal complexity is presented. The authors prove that most strings have high \(I\)-complexity. Their measure of complexity is compared with the Lempel-Ziv complexity, their main differences are discussed, and it is shown that in spite of their very distinct behavior on infinitely many strings, their values are close. Finally, the authors discuss a number of open problems and ongoing research on \(I\)-complexity. | |||
Property / review text: In this very interesting paper, the authors introduce the notion of the \(I\)-complexity of a given string, which counts the number of distinct substrings in it, and investigate its properties. They prove that this measure of string complexity is computable in linear time and space from the well-known longest common prefix array (LCP array), the companion data structure of the suffix array. They also introduce the repetitions array, which is a permutation of the LCP array, and develop its properties. It is shown that the number of strings with \(I\)-complexity up to a given value is bounded and a large family of strings with almost maximal complexity is presented. The authors prove that most strings have high \(I\)-complexity. Their measure of complexity is compared with the Lempel-Ziv complexity, their main differences are discussed, and it is shown that in spite of their very distinct behavior on infinitely many strings, their values are close. Finally, the authors discuss a number of open problems and ongoing research on \(I\)-complexity. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Francine Blanchet-Sadri / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68R15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68W32 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6064143 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
string complexity | |||
Property / zbMATH Keywords: string complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
description complexity | |||
Property / zbMATH Keywords: description complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Lempel-Ziv complexity | |||
Property / zbMATH Keywords: Lempel-Ziv complexity / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.007 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2078711260 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q61927022 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Volume and Entropy of Regular Timed Languages: Analytic Approach / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Volume and Entropy of Regular Timed Languages: Discretization Approach / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On extending de Bruijn sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5834367 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Resource-Bounded Kolmogorov Complexity Revisited / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4964008 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Theory of Program Size Formally Identical to Information Theory / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Clustering by Compression / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Pseudorandom Sequence--How Random Is It? / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4547749 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3214803 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Complexity of Finite Sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lempel-Ziv Dimension for Lempel-Ziv Compression / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Suffix Arrays: A New Method for On-Line String Searches / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Process complexity and effective random tests / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4531381 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Mathematical Theory of Communication / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Relations between varieties of kolmogorov complexities / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4337021 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Compression of individual sequences via variable-rate coding / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 13:34, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A linearly computable measure of string complexity |
scientific article |
Statements
A linearly computable measure of string complexity (English)
0 references
8 August 2012
0 references
In this very interesting paper, the authors introduce the notion of the \(I\)-complexity of a given string, which counts the number of distinct substrings in it, and investigate its properties. They prove that this measure of string complexity is computable in linear time and space from the well-known longest common prefix array (LCP array), the companion data structure of the suffix array. They also introduce the repetitions array, which is a permutation of the LCP array, and develop its properties. It is shown that the number of strings with \(I\)-complexity up to a given value is bounded and a large family of strings with almost maximal complexity is presented. The authors prove that most strings have high \(I\)-complexity. Their measure of complexity is compared with the Lempel-Ziv complexity, their main differences are discussed, and it is shown that in spite of their very distinct behavior on infinitely many strings, their values are close. Finally, the authors discuss a number of open problems and ongoing research on \(I\)-complexity.
0 references
string complexity
0 references
description complexity
0 references
Lempel-Ziv complexity
0 references