Pushdown and Lempel-Ziv depth
From MaRDI portal
Publication:6040660
DOI10.1016/j.ic.2023.105025arXiv2009.04821OpenAlexW3084253194MaRDI QIDQ6040660
Publication date: 19 May 2023
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2009.04821
algorithmic information theoryKolmogorov complexityLempel-Ziv algorithmlogical depthpushdown compressionfinite-state complexity
Cites Work
- Finite state incompressible infinite sequences
- Polylog space compression, pushdown compression, and Lempel-Ziv are incomparable
- Finite state complexity
- Lowness and logical depth
- Recursive computational depth.
- Finite-state dimension
- On the polynomial depth of various sets of random strings
- Normal numbers and finite automata
- Polylog depth, highness and lowness for E
- Computational depth: Concept and applications
- Endliche Automaten und Zufallsfolgen
- Automatic Kolmogorov complexity, normality, and finite-state dimension revisited
- Algorithmic Randomness and Complexity
- On the Difference Between Finite-State and Pushdown Depth
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- Feasible Depth
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item