Pushdown and Lempel-Ziv depth

DOI10.1016/j.ic.2023.105025arXiv2009.04821OpenAlexW3084253194MaRDI QIDQ6040660

Liam Jordon, Philippe Moser

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

zbMATH Keywords

algorithmic information theoryKolmogorov complexityLempel-Ziv algorithmlogical depthpushdown compressionfinite-state complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

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