On the Complexity of Finite Sequences

DOI10.1109/TIT.1976.1055501zbMath0337.94013MaRDI QIDQ4105595

Jacob Ziv, Abraham Lempel

Publication date: 1976

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Computability and recursion theory (03D99)

Related Items (only showing first 100 items - show all)

Temporal Variabilities Provide Additional Category-Related Information in Object Category Decoding: A Systematic Comparison of Informative EEG Features ⋮ Entropy estimation of symbol sequences ⋮ Average case analysis for tree labelling schemes ⋮ Fast gapped variants for Lempel-Ziv-Welch compression ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Efficient algorithms for Lempel-Ziv encoding ⋮ Improving the prediction accuracy of protein structural class: approached with alternating word frequency and normalized Lempel-Ziv complexity ⋮ A two-stage SVM method to predict membrane protein types by incorporating amino acid classifications and physicochemical properties into a general form of Chou's PseAAC ⋮ A NEW TWO-DIMENSIONAL COMPLEXITY MEASURE ⋮ Pattern-matching problems for 2-dimensional images described by finite automata ⋮ A test for randomness based on a complexity measure ⋮ Structural equivalence of s-tuples in random discrete sequences ⋮ On universal prediction and Bayesian confirmation ⋮ Estimating the Entropy Rate of Spike Trains via Lempel-Ziv Complexity ⋮ Algorithmic complexity of points in dynamical systems ⋮ ZIV-LEMPEL AND CROCHEMORE FACTORIZATIONS OF THE GENERALIZED PERIOD-DOUBLING WORD ⋮ Grammar compressed sequences with rank/select support ⋮ Phenomenology of coupled nonlinear oscillators ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ A statistical complexity measure with nonextensive entropy and quasi-multiplicativity ⋮ A simple and fast representation space for classifying complex time series ⋮ Composite Repetition-Aware Data Structures ⋮ Faster Lightweight Lempel-Ziv Parsing ⋮ Faster repetition-aware compressed suffix trees based on block trees ⋮ LZRR: LZ77 parsing with right reference ⋮ The combinatorial complexity of a finite string ⋮ Topological invariants for words of linear factor complexity ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Unraveling chaotic attractors by complex networks and measurements of stock market complexity ⋮ Lempel-Ziv complexity analysis of one dimensional cellular automata ⋮ Large-scale detection of repetitions ⋮ String attractors and infinite words ⋮ Balancing run-length straight-line programs ⋮ Substring complexities on run-length compressed strings ⋮ A new algorithm for compression of partially commutative alphabets ⋮ Stronger Lempel-Ziv based compressed text indexing ⋮ Comment on the Shiner-Davison-Landsberg measure ⋮ EVIDENCE CONSISTENT WITH DETERMINISTIC CHAOS IN HUMAN CARDIAC DATA: SURROGATE AND NONLINEAR DYNAMICAL MODELING ⋮ Speeding up the detection of tandem repeats over the edit distance ⋮ Ergodic behavior of graph entropy ⋮ Computational capabilities at the edge of chaos for one dimensional systems undergoing continuous transitions ⋮ Variance estimators for the Lempel-Ziv entropy rate estimator ⋮ Face Representations via Tensorfaces of Various Complexities ⋮ Response of the parameters of a neural network to pseudoperiodic time series ⋮ WORD COMPLEXITY AND REPETITIONS IN WORDS ⋮ Homoclinic chaos in the Rössler model ⋮ An axiomatic approach to network complexity ⋮ Algorithms for Indexing Highly Similar DNA Sequences ⋮ Greedy Palindromic Lengths ⋮ COMPLEXITY MEASURE: A QUANTUM INFORMATION APPROACH ⋮ Complex Similarity and Fluctuation Dynamics of Financial Markets on Voter Interacting Dynamic System ⋮ On-line construction of two-dimensional suffix trees ⋮ SYSTEM IDENTIFICATION, APPROXIMATION AND COMPLEXITY ⋮ Estimating Entropy Rates with Bayesian Confidence Intervals ⋮ HIGHER ORDER COMPLEXITY OF TIME SERIES ⋮ Shannon entropy: a rigorous notion at the crossroads between probability, information theory, dynamical systems and statistical physics ⋮ A generalized statistical complexity measure: Applications to quantum systems ⋮ Forty Years of Text Indexing ⋮ CAN WE MEASURE CONSCIOUSNESS WITH EEG COMPLEXITIES? ⋮ Parallelism and dictionary based data compression ⋮ Optimal encoding of non-stationary sources ⋮ \(LZ\)-based image compression ⋮ Predictability: a way to characterize complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Binary Pseudo-Random Sequences Theory ⋮ Regression Estimation from an Individual Stable Sequence ⋮ On the non-randomness of maximum Lempel Ziv complexity sequences of finite size ⋮ Upper bounds for the complexity of sequences generated by symmetric Boolean functions ⋮ Chaotic Dynamics in Brain Activity: An Approach Based on Cross-Prediction Errors for Nonstationary Signals ⋮ Statistical complexity of the time dependent damped L84 model ⋮ A DISCRIMINATION MEASURE FOR PHYLOGENETIC TREE CONSTRUCTION ⋮ The permutation entropy rate equals the metric entropy rate for ergodic information sources and ergodic dynamical systems ⋮ Estimating Information Rates with Confidence Intervals in Neural Spike Trains ⋮ APPROXIMATE, NON-DETERMINISTIC MODELLING OF BEHAVIOUR SEQUENCES ⋮ Dynamic index and LZ factorization in compressed space ⋮ Shiner–Davison–Landsberg complexity revisited ⋮ Artificial sequences and complexity measures ⋮ QUANTITATIVE CHARACTERIZATION OF THE COMPLEXITY OF MULTICHANNEL HUMAN EEGS ⋮ Range LCP ⋮ Quasi-distinct Parsing and Optimal Compression Methods ⋮ Optimal rank and select queries on dictionary-compressed text ⋮ CONVERGENCE OF C₀ COMPLEXITY ⋮ PARTITION-BASED ENTROPIES OF DETERMINISTIC AND STOCHASTIC MAPS ⋮ Unnamed Item ⋮ Information processing in the LGN: a comparison of neural codes and cell types ⋮ Randomness measures related to subset occurrence ⋮ Fast Exponentiation Using Data Compression ⋮ NONLINEAR SIGNAL CLASSIFICATION ⋮ Statistical complexity of the quasiperiodical damped systems ⋮ Mathematical Models of Textual Data: A Short Review ⋮ Complexity Invariance by Replication in the Quantum Square Well ⋮ Multiscale dynamic analysis of blast furnace system based on intensive signal processing ⋮ Hierarchical approach to complexity with applications to dynamical systems ⋮ Random Access to Grammar-Compressed Strings and Trees ⋮ Ordered intricacy of Shilnikov saddle-focus homoclinics in symmetric systems ⋮ Bridging Lossy and Lossless Compression by Motif Pattern Discovery ⋮ A Layered Broadcast Cryptographic System ⋮ Near-optimal search time in \(\delta \)-optimal space, and vice versa

This page was built for publication: On the Complexity of Finite Sequences