The DOI matches its Crossref record.
On the Complexity of Finite Sequences
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cited by
Handbook of applied cryptography
(1997) · Choice Reviews Online · doi:10.5860/choice.34-4512 · Cited by 10,357
A universal algorithm for sequential data compression
Ziv, J., & Lempel, A. (1977) · IEEE Transactions on Information Theory · doi:10.1109/tit.1977.1055714 · Cited by 5,456
Self-citationCompression of individual sequences via variable-rate coding
Ziv, J., & Lempel, A. (1978) · IEEE Transactions on Information Theory · doi:10.1109/tit.1978.1055934 · Cited by 3,432
Self-citationA theoretically based index of consciousness independent of sensory processing and behavior
Casali, A. G., Gosseries, O., Rosanova, M., Boly, M., Sarasso, S., Casali, K. R., Casarotto, S., Bruno, M.-A., Laureys, S., Tononi, G., et al. (2013) · Science Translational Medicine · doi:10.1126/scitranslmed.3006294 · Cited by 1,246
A Statistical Measure of Complexity
López-Ruiz, R., Mancini, H. L., & Calbet, X. (1995) · Physics Letters A · doi:10.1016/0375-9601(95)00867-5 · Cited by 920
Navarro, G., & Mäkinen, V. (2007) · ACM Computing Surveys · doi:10.1145/1216370.1216372 · Cited by 735
Computational Mechanics: Pattern and Prediction, Structure and Simplicity
Shalizi, C. R., & Crutchfield, J. P. (2001) · Journal of Statistical Physics · doi:10.1023/a:1010388907793 · Cited by 471
Increased spontaneous MEG signal diversity for psychoactive doses of ketamine, LSD and psilocybin
Schartner, M. M., Carhart-Harris, R. L., Barrett, A. B., Seth, A. K., & Muthukumaraswamy, S. D. (2017) · Scientific Reports · doi:10.1038/srep46421 · Cited by 410
Universal prediction of individual sequences
Feder, M., Merhav, N., & Gutman, M. (1992) · IEEE Transactions on Information Theory · doi:10.1109/18.144706 · Cited by 373
Schartner, M., Seth, A., Noirhomme, Q., Boly, M., Bruno, M.-A., Laureys, S., & Barrett, A. (2015) · PLOS ONE · doi:10.1371/journal.pone.0133532 · Cited by 287
“A simple measure of complexity based on the (lack of) compressibility of the EEG response, as quantified by the Lempel-Ziv algorithm [23], was developed for these data: the Perturbational Complexity Index (PCI) [21].”
MethodA novel multiscale nonlinear ensemble leaning paradigm for carbon price forecasting
Zhu, B., Ye, S., Wang, P., He, K., Zhang, T., & Wei, Y.-M. (2018) · Energy Economics · doi:10.1016/j.eneco.2017.12.030 · Cited by 236
Sequential Variety in Work Processes
Pentland, B. T. (2003) · Organization Science · doi:10.1287/orsc.14.5.528.16760 · Cited by 152
Levy, J., Álvarez, D., Rosenberg, A. A., Alexandrovich, A., del Campo, F., & Behar, J. A. (2021) · npj Digital Medicine · doi:10.1038/s41746-020-00373-5 · Cited by 125
Deep learning generalizes because the parameter-function map is biased towards simple functions
Valle-Pérez, G., Camargo, C. Q., & Louis, A. A. (2018) · arXiv · doi:10.48550/arxiv.1805.08522 · Cited by 105
A computer package for measuring the strength of encryption algorithms
Gustafson, H., Dawson, E., Nielsen, L., & Caelli, W. (1994) · Computers & Security · doi:10.1016/0167-4048(94)90051-5 · Cited by 104
Pal, D., Li, D., Dean, J. G., Brito, M. A., Liu, T., Fryzel, A. M., Hudetz, A. G., & Mashour, G. A. (2020) · The Journal of Neuroscience · doi:10.1523/jneurosci.1910-19.2019 · Cited by 80
A comparative analysis of swallowing accelerometry and sounds during saliva swallows
Dudik, J. M., Jestrović, I., Luan, B., Coyle, J. L., & Sejdić, E. (2015) · BioMedical Engineering OnLine · doi:10.1186/1475-925x-14-3 · Cited by 72
Effects of liquid stimuli on dual-axis swallowing accelerometry signals in a healthy population
Lee, J., Sejdić, E., Steele, C. M., & Chau, T. (2010) · BioMedical Engineering OnLine · doi:10.1186/1475-925x-9-7 · Cited by 68
Landauer, M., Skopik, F., & Wurzenberger, M. (2024) · Proceedings of the ACM on Software Engineering · doi:10.1145/3660768 · Cited by 61
A method of identifying chronic stress by EEG
Peng, H., Hu, B., Zheng, F., Fan, D., Zhao, W., Chen, X., Yang, Y., & Cai, Q. (2013) · Personal and Ubiquitous Computing · doi:10.1007/s00779-012-0593-3 · Cited by 55
Neural Correlates of the Shamanic State of Consciousness
Huels, E. R., Kim, H., Lee, U., Bel-Bahar, T., Colmenero, A. V., Nelson, A., Blain-Moraes, S., Mashour, G. A., & Harris, R. E. (2021) · Frontiers in Human Neuroscience · doi:10.3389/fnhum.2021.610466 · Cited by 52
Lucid dreaming occurs in activated rapid eye movement sleep, not a mixture of sleep and wakefulness
Baird, B., Tononi, G., & LaBerge, S. (2022) · Sleep · doi:10.1093/sleep/zsab294 · Cited by 41
Digital Search Trees Again Revisited: The Internal Path Length Perspective
Kirschenhofer, P., Prodinger, H., & Szpankowski, W. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539790189368 · Cited by 43
Integrated information and state differentiation
Marshall, W., Gomez-Ramirez, J., & Tononi, G. (2016) · Frontiers in Psychology · doi:10.3389/fpsyg.2016.00926 · Cited by 36
An Accuracy Metric: Percentages, Randomness, and Probabilities
Fisher, C. W., Lauria, E. J. M., & Matheus, C. C. (2009) · Journal of Data and Information Quality · doi:10.1145/1659225.1659229 · Cited by 40
EEG Lempel-Ziv complexity varies with sleep stage, but does not seem to track dream experience
Aamodt, A., Sevenius Nilsen, A., Markhus, R., Kusztor, A., HasanzadehMoghadam, F., Kauppi, N., Thürer, B., Storm, J. F., & Juel, B. E. (2023) · Frontiers in Human Neuroscience · doi:10.3389/fnhum.2022.987714 · Cited by 30
Leveraging Nonhuman Primate Multisensory Neurons and Circuits in Assessing Consciousness Theory
Noel, J.-P., Ishizawa, Y., Patel, S. R., Eskandar, E. N., & Wallace, M. T. (2019) · The Journal of Neuroscience · doi:10.1523/jneurosci.0934-19.2019 · Cited by 30
Wiese, W., & Friston, K. J. (2021) · Philosophy and the Mind Sciences · doi:10.33735/phimisci.2021.81 · Cited by 27
Complexity and Entropy in Legal Language
Friedrich, R. (2021) · Frontiers in Physics · doi:10.3389/fphy.2021.671882 · Cited by 19
Chang, J.-Y., Fecchio, M., Pigorini, A., Massimini, M., Tononi, G., & Van Veen, B. D. (2019) · Journal of Neuroscience Methods · doi:10.1016/j.jneumeth.2018.11.006 · Cited by 13
Predicting phenotype transition probabilities via conditional algorithmic probability approximations
Dingle, K., Novev, J. K., Ahnert, S. E., & Louis, A. A. (2022) · Journal of the Royal Society Interface · doi:10.1098/rsif.2022.0694 · Cited by 13
Non-random structures in universal compression and the Fermi paradox
Gurzadyan, A. V., & Allahverdyan, A. E. (2016) · The European Physical Journal Plus · doi:10.1140/epjp/i2016-16026-6 · Cited by 2
Adama, S., & Bogdan, M. (2026) · Frontiers in Computational Neuroscience · doi:10.3389/fncom.2026.1797090 · Cited by 1
Metadata
- Authors
- Lempel, A., & Ziv, J.
- Venue
- IEEE Transactions on Information Theory
- Published
- 1976-01
- Volume
- 22
- Issue
- 1
- Pages
- 75-81
- ISSN
- 0018-9448 (ISSN-L)
- 1557-9654
- OpenAlex
- W2077770566
- Cited by
- 2,717
- References
- 0
- FWCI
- 4.29
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
