articleTop 10% cited

On the Complexity of Finite Sequences

IEEE Transactions on Information Theory · 1976 · Vol. 22(1) · pp. 75–81

A. Lempel✉(RAND Corporation)J. Ziv(Technion – Israel Institute of Technology)

Abstract

A new approach to the problem of evaluating the complexity ("randomness") of finite sequences is presented. The proposed complexity measure is related to the number of steps in a self-delimiting production process by which a given sequence is presumed to be generated. It is further related to the number of distinct substrings and the rate of their occurrence along the sequence. The derived properties of the proposed measure are discussed and motivated in conjunction with other well-established complexity criteria.

Computability, Logic, AI Algorithms semigroups and automata theory Cellular Automata and ApplicationsSubstringRandomnessSequence (biology)Measure (data warehouse)Computational complexity theoryConjunction (astronomy)MathematicsTheoretical computer scienceAlgorithmComputer science

Citations

2,712

FWCI

4.70

field-weighted impact

References

Percentile

95%

vs. same field & year

Citations per year

Cited by

A Theoretically Based Index of Consciousness Independent of Sensory Processing and Behavior